多维标度模型的数值求解方法及其在无线传感器网络定位中的应用

Multidimensional scaling (MDS) is a kind of method in Multivariate Statistical Analysis. It has a wide range of applications. In recent years, MDS has been successfully applied to the wireless sensor network (WSN) localization in particular. The core issue of the MDS method is to solve a non-convex optimization problem. This project aims to design efficient and quick global optimization algorithms for solving MDS model and analyze their properties; then applies research results to solve WSN localization problem according to its specific needs. The following are major contents:(1)equivalently transform non-convex MDS model to a matrix rank minimization problem; and considering the specific form of the problem, using the research achievements of the matrix rank minimization problem in the optimization field, design quick global optimization algorithms;(2)apply SDP relaxation to the non-convex MDS model, discuss conditions of deriving an accurate solution and design algorithms to solve it;(3)using the Lagrange dual method, design quick global optimization algorithms;(4)according to the feature that there are many local minimizers for the non-convex MDS model, design smoothing global optimization algorithms and do some numerical experiments;(5)based on the above study, according to characteristics of moving codes; making full use of network connectivity to design MDS moving localization algorithm, and do the simulation analysis.

多维标(尺)度法(MDS)是一类多元统计分析方法，有着广泛的应用，尤其近年来已被成功应用到无线传感器网络（WSN）定位上。MDS的核心问题是求解一个非凸优化问题。本项目旨在设计求解MDS模型的高效快速的全局优化算法，进行算法理论分析，并将研究结果应用到求解WSN定位中。主要内容如下(1)将MDS中的非凸问题等价转化为矩阵极小秩问题，结合问题的具体形式，利用目前优化领域对于矩阵极小秩问题的研究结果，设计快速的全局优化算法;(2)对MDS中的非凸问题进行SDP松弛，讨论松弛问题取到原问题解的条件，设计算法进行求解;(3)利用Lagrange对偶方法，设计快速的全局优化算法;(4)根据MDS非凸问题局部极小解很多的特点，设计光滑化全局优化算法，进行数值试验;(5)在以上所得研究成果基础上，根据节点移动的特点，结合MDS充分利用网络连通性的优势，设计MDS移动定位全局优化算法，并进行仿真试验。

多维标(尺)度法(MDS)作为一类经典的多元统计分析方法，其核心问题是求解一个非凸优化问题。本项目的研究工作主要为几个方面：(1)将MDS 中的非凸问题等价转化为矩阵极小秩问题，分析了距离度量矩阵这一类负半定矩阵锥投影的性质，并提出了一个在一定条件下具有全局收敛性的交替方向法。（2）引入Langrange对偶算法求解MDS，应用到无线传感器定位问题。采用二阶段的思想设计Lagrange对偶算法求解大规模MDS的快速算法，在此基础上，采用分簇的思想对无线传感器定位问题进行了仿真实验。（3）光滑算法研究方面。首先，设计了新的光滑函数，并证明了该光滑函数是原目标函数的一致光滑逼近；其次，设计与优化函数方法相结合的全局光滑化算法，其数值试验结果表明了算法的有效性；进一步研究了光滑算法，将光滑算法应用到一维统计方法校正估计中，证实了算法的有效性。