求解半定规划的新算法

为了提高求解半定规划问题的运算效率,提出了一种新的求解半定规划的非单调信赖域算法。将半定规划的最优性条件转化为无约束优化问题,并构造无约束优化问题的信赖域子问题,修正信赖域半径的校正条件,当初始搜索点处于峡谷附近时仍能搜索到全局最优解。实验结果表明,对于小规模和中等规模的半定规划问题,该算法的迭代次数都比经典的内点算法少,运行速度快。     

一种求解半定规划的非单调信赖域算法

提出一种求解半定规划的非单调信赖域算法。利用推广至矩阵域的光滑Fischer-Burmeister函数,转化半定规划的最优性条件,改写半定规划的中心路径,得到与其等价的无约束优化问题的非线性可微光滑方程组,在求解信赖域子问题时,利用当前迭代点的一阶梯度信息,给出信赖域半径的选取机制。仿真结果表明,与经典的内点算法相比,对于一般规模(n, m≤30)的半定规划问题,该算法的运行速度较快。对于大规模的半定规划问题(n, m＞30),该算法更适合处理Norm min、Lovasz这2类问题。     

求解二次规划逆问题的非单调信赖域算法

为了提高求解二次规划逆问题的速度,提出了针对求解该问题的非单调信赖域算法.为了降低问题的复杂度,将二次规划逆问题转换为决策变量相对较少的对偶问题,采用增广Lagrange法构造对偶问题的子问题,并通过引入光滑函数将子问题转换为无约束优化问题,利用非单调信赖域算法进行求解.数值实验结果表明,该算法的迭代次数比牛顿算法、Gauss回代交替方向法少,运行速度快.因此,对于大规模二次规划逆问题,该算法更加有效.     

非单调信赖域方法求解无约束非光滑优化问题

提出了非单调信赖域算法求解无约束非光滑优化问题,并和经典的信赖域方法作比较分析。同时,设定了一些条件,在这些假设条件下证明了该算法是整体收敛的。数值实验结果表明,非单调策略对无约束非光滑优化问题的求解是行之有效的,拓展了非单调信赖域算法的应用领域。     

一种求解无约束优化问题的非单调信赖域算法

提出了非单调信赖域算法求解基于锥模型的无约束优化问题,该算法在求解信赖域子问题时充分利用了当前迭代点的一阶梯度信息。提出了一个新的信赖域半径的选取机制,并和经典的信赖域方法作比较分析。设定了一些条件,在这些假设条件下证明了算法是整体收敛的。数值实验结果表明,该算法对基于锥模型的无约束优化问题的求解是行之有效的,拓展了非单调信赖域算法的应用领域。     

基于半定规划的无线传感器网络定位算法性能分析

基于测距的定位方法是无线传感器网络节点定位中一种常见的方法。测距定位方法往往将定位过程转化为数学优化问题。介绍了实现测距定位下的LS-SDR与SAL-SDR两种半定规划定位算法,并同时介绍了LS-LM、SLS-LM、SLS-US与SLS-S等4种定位算法。仿真实验分析和比较了6种不同定位算法的平均RMS定位误差,结果表明相对于其他4种定位算法,LS-SDR和LS-LM算法的定位误差较小。在信标节点数量较少的情况下,LS-LM算法的定位结果有可能发生奇异,造成定位结果的严重失真。而LS-SDR算法对于奇异的发生具有较好的抵抗能力,此时LS-SDR算法的平均RMS定位误差将优于LS-LM算法。     

基于半定规划的恶劣环境下定位修正算法

无线传感网络WSNs(Wireless Sensor Networks)的定位精度严重受到环境的影响,尤其是高噪声电平和非视距连接的恶劣环境,定位精度急剧下降.为此,提出基于半定规划的恶劣环境下定位修正算法,记为ESDP O算法.该修正算法以半定规划ESDP(Edge-Semi-Definite Programming)算法为基础,旨在提高定位精度,并降低算法复杂性,进而减少定位时间.ESDP O算法通过引用抖动矩阵,对ESDP算法进行修改,提高了算法在恶劣环境的健壮性.同时,ESDP O算法通过寻找低秩解,减少高噪声和非视距偏差.仿真结果表明,在高噪声和非视距NLOS(Non Line of Sight)的恶劣环境下,ESDP O算法的定位精度优于基于同类算法,并且降低了定位的复杂度.     

一类新的带记忆模型的非单调信赖域算法

本文就无约束优化问题提出了一个带记忆模型的非单调信赖域算法。与传统的非单调信赖域算法不同,文中的信赖域子问题的逼近模型为记忆模型,该模型使我们可以从更全面的角度来求得信赖域试探步,从而避免了传统非单调信赖域方法中试探步的求取完全依赖于当前点的信息而过于局部化的困难。文中提出了一个带记忆模型的非单调信赖域
域算法,并证明了其全局收敛性。     

基于半定规划的量子状态最优无错区分

对于一般的量子状态最优无错区分问题.很难得到最优量子测量的解析形式.因此,有必要寻求有效实用的数值方法.基于半定规划理论,证明了无错状态区分的最优量子测肇的设计问题可以转化为标准的半定规划问题,以及能直接应用半定规划的最优性条件,从而更简明地推导了.一组无错状态区分的最优性条件;通过求解标准的半定规划问题.可在多项式时间内直接得到最优量子测量的数值解以及成功区分状态的最大概率值.实例仿真表明,方法易于计算机实现,能有效地设计出无错状态区分的最优量子测量算子.     

一种高斯噪声下基于最大分散度的WSN半定规划定位算法

基于最大分散度的概念,本文提出了一种新的高斯噪声下基于半定规划的WSN定位算法——MSDSDP算法。该算法将定位问题建模成一个将最大化网络分散度作为目标函数,由节点测量距离和噪声标准差确定的不等式作为约束条件的最优化问题,并将该最优化问题松弛为半定规划模型进行求解。分析及实验结果表明,该算法能有效地克服fullSDP节点估计位置向锚节点凸包中心汇聚的问题,在计算复杂度相同的情况下明显提高定位精度。将MSDSDP算法的结果作为初始点进行梯度搜索,能进一步提高定位精度。     

移动WSNs中基于半定规划的节点定位算法

针对移动无线传感网络(Wireless Sensor Networks, WSNs)的节点定位问题,提出基于半定规划的节点定位(Semi-Definite Programming Localizattion, SDPL)算法,SDPL算法考虑测移动节点与锚节点间的测距和测速这两项信息,先推导了在准确测距环境下的最大似然(Maximum Likelihood, ML)的位置估计,再利用SDP技术求解非凸优化的定位问题的近似解。同时,将SDPL算法扩展到噪声测速环境。仿真结果表明,移动信息对定位性能有重要的影响。     

一种求解控制理论问题的新工具:LMI凸优化方法

系统和控制理论中许多重要的问题，都可转化为线性矩阵不等式约束的凸优化问题，从而使其在数值上易于求解，在阐述了线性矩阵不等式方法的基本概念和内容后，介绍有关算法及计算软件。     

半定规划支持向量机模型的研究

支持向量机(support vector machines,SVM)的分类精度和泛化能力会受到核函数及其工作参数的影响,传统的核函数参数选择方法缺乏理论支持,花费的时间较多,效果也不一定理想。针对此问题,提出一种基于半定规划的SVM模型,利用半定规划来判别一组给定的核函数工作参数是否有效,并能用有效的核函数工作参数组合计算出更优的核矩阵,提高SVM模型的分类精度。在UCI数据集上的实验结果表明,用此方法判别核函数工作参数是可行的,所组合出的半定规划SVM模型的泛化能力优于传统的SVM模型,并且异构核半定规划SVM模型的泛化能力优于同构核半定规划SVM模型。     

求解互补支持向量机的非单调信赖域算法

求解支持向量机的核心问题是对一个大规模凸二次规划问题进行求解。基于支持向量机的修正模型,得到一个与之等价的互补问题,利用Fischer-Burmeister互补函数,从一个新的角度提出了求解互补支持向量机的非单调信赖域算法。新算法避免了求解Hesse矩阵或矩阵求逆运算,减少了工作量,提高了运算效率。在不需要任何假设的情况下,证明算法具有全局收敛性。数值实验结果表明,对于大规模非线性分类问题,该算法的运行速度比LSVM算法和下降法快,为求解SVM优化问题提供了一种新的可行方法。     

一种求解约束优化问题的信赖域微粒群算法

提出了一种改进型信赖域微粒群算法来求解带有不等式约束优化问题。粒子群每一次进化后,对所有粒子执行信赖域搜索,寻找更优个体,从而增加了微粒群算法的局部搜索能力。把算法应用于供应商补货优化,实验结果表明,该方案能够有效地减少供应商的补货成本,具有较好的应用价值。     

半在线调度中约束求解算法研究

很多实际调度问题是半在线的. 尝试运用人工智能方法来求解半在线调度问题, 首先简要介绍了半在线调度问题并对其约束模型进行了分类, 通过引入单调性约束扩展的相关概念, 从约束建模角度形式化描述 了一类动态约束扩展, 并在此基础上设计了一个完备动态约束求解算法, 最后给出该算法在半在线离散资源约束调度求解的应用算例. 测试结果表明, 该算法是可行有效的.     

基于混合式的松弛规划优化的鲁棒定位算法

测距误差以及锚节点位置的不确定性给无线传感网络的节点定位提出挑战。为此,提出基于半定规划SDP （semi‐definite programming）和二阶锥规划SOCP （second order cone programming）的混合式松驰规划求解定位问题的优化方案,记为R＿SOCP＋ SDP。考虑测距误差和锚节点位置的不确定性,根据最大似然估计原则建立定位估计的鲁棒 SOCP （RSOCP）、鲁棒SDP （RSDP）优化函数;分析SOCP与SDP间的关系,充分考虑SOCP的计算复杂度低、SDP的定位精度高的特点,建立R＿SOCP＋SDP凸优化函数;运用凸优理论中的松弛规划技术估计节点的位置。仿真结果表明, R＿SOCP＋SDP有效减少了定位误差,降低了计算复杂度。     

多用户检测问题的半定规划坐标下降算法

1.引言在码分多址(CDMA)系统中,由于多个用户的随机接入,使扩频码集一般并非严格正交,这样非零相关系数会引起各用户间的相互干扰——多址干扰(MAI)。在传统的Rake检测方法中,MAI严重限制了蜂窝容量,并且必须用很强的能量来克服远近问题。     

求解约束优化问题的人工鱼群算法

在利用人工鱼群算法求解约束问题时,处理好约束条件是取得好的优化效果的关键。引入了半可行域的概念,并结合人工鱼群算法(ArtificialFish-SwarmAlgorithm,AFSA)本身的特点,设计了基于竞争选择和惩罚函数的适应度函数,从而得到了一个利用ASFA算法求解约束优化问题的新的进化算法。实验证明了算法的有效性。     

求解非线性规划问题的一种新演化算法

1.引言演化算法是建立在生物进化论基础上的算法,生物体可以通过遗传和变异来适应外界环境,物生其类,传种接代,这是生物的独特本领。各种生物所生的子代基本上像父代,这就是遗传;而所生的子代又不完全像父代,这就是变异。世代相传,使得生物体不断进化。演化算法就是利用了生物进化的思想而发展起来的一种通用的问题求解方法。由于其所具有的本质并行性以及自组织、白适应和自学习等智能特征,目前已广泛用于优化问题,它能克服传统优化方法的不足,寻找全局最优解。该方法是按照生物遗传进化世代繁衍的优生劣汰、演化出优良品种的特点,形成寻优的计算方法。特别是演化算法已成功地应用到那些难以用传统方法进行求解的复杂问题之中,从而成为一个引人注目的研究方向。