V半正定規(guī)劃模型概述目錄TOC\o"1-3"\h\u18866半正定規(guī)劃模型概述 1101241.1半正定規(guī)劃概述 113871.2半正定規(guī)劃形式 210151.3半正定規(guī)劃模型的建立 21.1半正定規(guī)劃概述半正定規(guī)劃（Semi-positiveDefiniteProgramming,簡稱SDP)問題其實是凸優(yōu)化問題的一種特殊形式，它具有線性目標函數，約束條件之一是對稱矩陣的仿射組合半正定，目的是對線性目標函數的極值進行求解。這個約束條件是凸的，非線性的。二十世紀六十年代，半正定規(guī)劃的研究就已經開始了，Fan和Belman[38]兩人在1963年第一次提出一個半正定規(guī)劃問題，后來又有學者將半正定規(guī)劃與控制論聯系起來進行分析研究，二十世紀七十年代初期，Wolf,Donath和Cullumn[39]等人利用半正定規(guī)劃對圖劃分算法進行研究，使得原來復雜的問題變得簡單起來。而讓半正定規(guī)劃成為求解組合優(yōu)化問題的重要工具的標志，是Shor[40]解決組合優(yōu)化問題時提出利用半正定規(guī)劃松弛。二十世紀九十年代，多項式時間內點算法理論由Nesterov[41]和Nemirovski[42]提出，這對于一般凸優(yōu)化問題的求解是很好的。時間到達二十一世紀，也就是近些年，YinyuYe[43]將線性規(guī)劃內點算法推廣到半正定規(guī)劃，使得半正定規(guī)劃的發(fā)展再上新臺階。其相關文獻中，有關傳感器定位問題對應的特殊半正定規(guī)劃模型可以表示為：mins.t.（2-2）如果是一個關于Z的凸函數，那么上述模型就成為一個凸優(yōu)化問題，特殊情況下，如果是關于Z的線性函數，并且是一個凸集，則上述模型是一個半正定規(guī)劃模型。半正定規(guī)劃是一種定義在實數域上的半正定矩陣錐上的規(guī)劃，它也是線性規(guī)劃的一種推廣。半正定線性規(guī)劃的目標函數及其可行域都為線性，半正定非線性規(guī)劃則容易知道，是目標函數為非線性或者其可行域為非線性[44]。半正定規(guī)劃這一算法自提出至今，廣泛應用于各種優(yōu)化問題當中，對解決優(yōu)化方面相關問題起著重要的積極作用。也正因為它是一種相當有效的算法，能夠解決很多優(yōu)化問題，因而本論文使用半正定規(guī)劃算法作為相關定位的算法來進行定位計算。1.2半正定規(guī)劃形式半正定規(guī)劃算法的標準形式可如下：mins.t.（2-3）其中，、是實數矩陣，，是已知數據。一般來說，半正定規(guī)劃問題的解為一個矩陣,且矩陣，如果矩陣滿足所有的約束條件并且，那么求得的解叫做內部可行解或者嚴格可行解。在一些情況中也會用到SDP的對偶形式去解決相關問題，SDP的對偶形式可如下：maxs.t.（2-4）其中,,求得的解滿足所有的約束條件，則稱其為對偶內點內部可行解。1.3半正定規(guī)劃模型的建立假設在一個d維空間中，有m個已知錨點（），n個未知節(jié)點(）。任意兩個未知節(jié)點i和j之間的距離數據可以測量出來，也就是已知，記為，任意兩個已知節(jié)點k與未知節(jié)點j之間的距離也可以通過測量知曉，記為，且任意兩點距離的下界為R。由于任意節(jié)點之間傳遞信息過程中，信號穿過不同介質速度不一樣，導致信號接收時間偏長，測量距離偏大。因此，定位問題可以描述為一個混合等式和不等式的誤差最小化問題,問題模型如下：mins.t.（2-5）令為需要確定的矩陣，為第個位置為1，其余位置為0的向量，為第個位置為1，第個位置為-1，其余位置為0的向量。令,將變量松弛，并且引入松弛變量Z,則：,（2-6）原問題即可松弛為半正定規(guī)劃問題，如下：mins.t.（2-7）可知矩陣有個未知變量。如果全部的測量結果都是準確無誤的并且其他距離邊界是可行的，即誤差項和為0，那么式（2-7）即有唯一取得最小值解:（2-