【《半正定规划模型概述》1300字】

V半正定规划模型概述目录TOC\o"1-3"\h\u18866半正定规划模型概述 1101241.1半正定规划概述 113871.2半正定规划形式 210151.3半正定规划模型的建立 21.1半正定规划概述半正定规划（Semi-positiveDefiniteProgramming,简称SDP)问题其实是凸优化问题的一种特殊形式，它具有线性目标函数，约束条件之一是对称矩阵的仿射组合半正定，目的是对线性目标函数的极值进行求解。这个约束条件是凸的，非线性的。二十世纪六十年代，半正定规划的研究就已经开始了，Fan和Belman[38]两人在1963年第一次提出一个半正定规划问题，后来又有学者将半正定规划与控制论联系起来进行分析研究，二十世纪七十年代初期，Wolf,Donath和Cullumn[39]等人利用半正定规划对图划分算法进行研究，使得原来复杂的问题变得简单起来。而让半正定规划成为求解组合优化问题的重要工具的标志，是Shor[40]解决组合优化问题时提出利用半正定规划松弛。二十世纪九十年代，多项式时间内点算法理论由Nesterov[41]和Nemirovski[42]提出，这对于一般凸优化问题的求解是很好的。时间到达二十一世纪，也就是近些年，YinyuYe[43]将线性规划内点算法推广到半正定规划，使得半正定规划的发展再上新台阶。其相关文献中，有关传感器定位问题对应的特殊半正定规划模型可以表示为：mins.t.（2-2）如果是一个关于Z的凸函数，那么上述模型就成为一个凸优化问题，特殊情况下，如果是关于Z的线性函数，并且是一个凸集，则上述模型是一个半正定规划模型。半正定规划是一种定义在实数域上的半正定矩阵锥上的规划，它也是线性规划的一种推广。半正定线性规划的目标函数及其可行域都为线性，半正定非线性规划则容易知道，是目标函数为非线性或者其可行域为非线性[44]。半正定规划这一算法自提出至今，广泛应用于各种优化问题当中，对解决优化方面相关问题起着重要的积极作用。也正因为它是一种相当有效的算法，能够解决很多优化问题，因而本论文使用半正定规划算法作为相关定位的算法来进行定位计算。1.2半正定规划形式半正定规划算法的标准形式可如下：mins.t.（2-3）其中，、是实数矩阵，，是已知数据。一般来说，半正定规划问题的解为一个矩阵,且矩阵，如果矩阵满足所有的约束条件并且，那么求得的解叫做内部可行解或者严格可行解。在一些情况中也会用到SDP的对偶形式去解决相关问题，SDP的对偶形式可如下：maxs.t.（2-4）其中,,求得的解满足所有的约束条件，则称其为对偶内点内部可行解。1.3半正定规划模型的建立假设在一个d维空间中，有m个已知锚点（），n个未知节点(）。任意两个未知节点i和j之间的距离数据可以测量出来，也就是已知，记为，任意两个已知节点k与未知节点j之间的距离也可以通过测量知晓，记为，且任意两点距离的下界为R。由于任意节点之间传递信息过程中，信号穿过不同介质速度不一样，导致信号接收时间偏长，测量距离偏大。因此，定位问题可以描述为一个混合等式和不等式的误差最小化问题,问题模型如下：mins.t.（2-5）令为需要确定的矩阵，为第个位置为1，其余位置为0的向量，为第个位置为1，第个位置为-1，其余位置为0的向量。令,将变量松弛，并且引入松弛变量Z,则：,（2-6）原问题即可松弛为半正定规划问题，如下：mins.t.（2-7）可知矩阵有个未知变量。如果全部的测量结果都是准确无误的并且其他距离边界是可行的，即误差项和为0，那么式（2-7）即有唯一取得最小值解:（2-