半定规划的弱尖锐性及其在自组无线传感器网络节点定位问题中的应用

Recently, Zheng, Ye and Boyd(SIAM J. Optim.,19(2):655-673,2008) proposed a futher relaxation of the semidefinite programming(SDP) relaxation of the SDP relaxation of the Ad Hoc wireless sensor networks localization problem(AHWSNs), named edge-based SDP(ESDP). In simulation, the ESDP is solved much faster than by interior-point method than SDP relaxation, and the solutions found are better in approximation accuracy. Unfortunately, the feasible regions of the ESDP relaxation problems for some specific AHWSNs are empty because of limited transmission power of the sensors and the interfence of the environmental issues , say, noise. Thus, the interior-point method cannot be applied. For overcoming this shortcoming, this subject is to propose a new approach to handle these ill-posed (with empty feasible set) ESDP by introducing the notion of weak sharp minima. We propose a noncanonical lower-oder penalty function method to sove these ill-posed ESDP directly and apply this method for positioning and tracking in real time. Firstly, we introduce the notion of weak sharp minima for the general SDP, via subgradients to describe the sufficient conditions,necessary conditions and necessary and sufficient conditions for SDP with weak sharp minima. Secondly, we introduce a noncanonical lower order penalty function method for solving these ill-posed ESDP,and prove the exact penalty property hold true. At last, we analyse the algorithms''s sensitivity,consider the algorithm''s numerical simulation.

Wang,Zheng,Ye和Boyd(SIAM J. Optim.,19（2）：655-673，2008)将自组无线传感器网络的节点定位问题（AHWSN）松弛为一组基于边界的半定规划问题（ESDP）并用内点法进行求解。但若同时考虑传感器的传送功率和噪声等环境因素的影响，AHWSN松弛后的ESDP的可行域可能为空集，从而阻碍了算法的可行性。为了推广这种定位算法的适用范围，本项目将以弱尖锐性为工具，引入一种非传统的低阶罚函数方法直接求解这类病态的（可行域可能为空）ESDP，并将此算法应用于求解实时追踪和定位问题。首先，本项目将对一般的半定规划问题（SDP）引入弱尖锐性的概念，利用次梯度等工具刻画SDP具有弱尖锐性的一些充分条件、必要条件和充分必要条件。然后，对松弛后的病态的ESPD引入一种非传统的低阶罚函数法，应用弱尖锐性证明其具有精确罚性质。最后，考察算法的灵敏度和数值实现情况。

(1) 我们为带锥约束的凸优化问题提出了广义弱尖锐性的概念，分别在巴拿赫空间和希尔伯特空间中研究了其性质；作为广义弱尖锐性的应用，我们为希尔伯特空间中的带锥约束的凸优化问题给出了一种新的求解算法，并考察该算法的收敛性。.(2) 在广义弱尖锐性的研究基础上，我们进一步研究了带锥约束的凸优化问题，提出了广义I 型弱尖锐性的概念，建立了弱尖锐性、广义弱尖锐性和广义I型弱尖锐性之间的关系，研究了广义I 型弱尖锐性的性质，分析了广义I型弱尖锐性和拉格朗日乘子的存在性之间的密切联系；作为广义I型弱尖锐性的应用，分析了一类非退化的可微凸包含问题的局部误差界。