[發明專利]基于到達時間的多目標定位外部逼近近似凸優化算法

有效

• 申請號: 201710720839.6
• 申請日: 2017-08-22
• 公開（公告）號: CN107271958B
• 公開（公告）日: 2019-07-12
• 發明（設計）人: 羅文洲;蘇文藻
• 申請（專利權）人: 四川航天系統工程研究所
• 主分類號: G01S5/06
• 分類號: G01S5/06;G01S5/00;G06F17/50
• 代理公司: 四川省成都市天策商標專利事務所 51213
• 代理人: 劉興亮

1.一種基于到達時間的多目標定位外部逼近近似凸優化算法，包括通過半正定松弛，二次錐松弛、泰勒松弛和添加SDP強約束條件后，根據最大似然估計MLE模型得到一個混合整數凸優化問題，根據外部逼近近似算法得到精確的多目標坐標，其特征在于具體包括以下步驟：

a)通過TOA定義，使用最大似然估計構造了一個混合整數、非凸的原始問題模型；

b)通過采用半正定松弛、泰勒松弛和二次錐松弛的松弛方法以及添加SDP約束條件，將原問題松弛為一個混合整數凸優化問題模型；

c)通過解外部逼近近似算法子模型得到一個整數部分的解P，對應的最優函數值作為整個算法的下界LB；

d)固定整數解部分，b)對應的混合整數凸優化問題模型變為一個連續凸優化問題模型，通過解該連續凸優化問題模型得到連續部分解，及對應的函數值,對應函數值中的最小值為整個算法的上界UB；

e)判斷連續凸優化問題模型得到的解是否是原問題的最優解：

ⅰ.If UB>LB+constant，d)中的連續解以及與他相對應的整數解不是原問題的最優解，迭代升級b)中的外部逼近近似算法子模型的約束條件，確保已經出現過的整數解不會再次出現，繼續執行b)-d)直至得到最優解或者迭代次數超過預設的上限；

ⅱ.If UB<＝LB+constant,d)中的連續解以及與他相對應的整數解為原問題的最優解，停止程序。

2.根據權利要求1所述基于到達時間的多目標定位外部逼近近似凸優化算法，其特征在于：

步驟a)包括：

ⅰ.TOA定義，假設有K個待定位目標，x為待定位目標的位置矩陣，其對應一個L×K矩陣，M個基站，s為基站的位置矩陣，其對應一個L×M矩陣，其中基站的位置矩陣s已知，到達時間對應的K×M矩陣d已知，待定位目標的位置矩陣x未知；根據TOA定義可知，第k個目標到第i個基站的到達時間如下所示：

其中，最后一項為噪音，不失一般性的，我們假設每個噪聲都服從高斯分布，并且獨立同分布；多目標定位中，假設對于每一個基站不能識別他獲得的信號來自于哪一個目標，表示為為了識別每一個目標，我們為每一個基站引入了一個置換矩陣以識別每一個目標，對于第i個基站，識別來自第k個目標的TOA值，方法如下：

ⅱ.通過最大似然估計，去最小化噪聲的絕對值，基于此構造了如下多目標定位模型，即原始問題模型：

Z_k，i≥0，Pⁱ∈π，

其中，Pⁱ表示第i個基站對應的置換矩陣；為第i個基站接收的TOA數據；Z_k,i表示第k個目標與第i個基站的實際TOA數據與估計數據的差異的平方；為待計算的第k個目標與第i個基站的真實TOA值；第二個約束是TOA的物理定義。

3.根據權利要求1所述基于到達時間的多目標定位外部逼近近似凸優化算法，其特征在于：

步驟b)包括：

ⅰ.根據所述TOA數據和基站的位置信息來計算多個目標的位置；

ⅱ.對原始問題進行包括但不限于半正定松弛、二次錐松弛、泰勒松弛和添加SDP約束條件以使得原問題變為凸問題以及降低計算復雜度。

4.根據權利要求1所述基于到達時間的多目標定位外部逼近近似凸優化算法，其特征在于：

所述步驟c)包括：

ⅰ.松弛掉SDP約束的半正定的約束條件，得到外部逼近近似算法子模型；

ⅱ.外部逼近近似算法子模型是一個混合整數-二次錐凸優化問題；

ⅲ.松弛后的外部逼近近似算法子模型，可以使用包括但不限于分支定界算法、內點法、固定步長梯度下降法、變步長梯度下降法和牛頓法來得到子問題的最優解和最優函數值；

ⅳ.保存最優解的整數部分，最優函數值被定義為原問題的下界LB，進入步驟c)。