半定规划及其在无线传感器网络定位中的应用

论文摘要

半定规划是线性规划的一种推广,是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大（极小）化的问题,这个约束是非线性、非光滑、凸的,因而半定规划是一个非光滑凸优化问题.许多凸规划问题都可以转化为半定规划进行求解,因此半定规划为研究这一系列凸规划问题并构造算法提供了统一的数学框架,并且在控制论、组合优化、系统工程和特征值优化等领域都得到了广泛的应用.本文介绍了半定规划的基础知识、对偶理论和研究现状,然后对半定规划理论和算法及在传感器网络定位中的应用作了研究,主要内容如下:1.通过半定规划的KKT最优化条件的等价转换,得到一个非线性方程组,然而无法求其精确解,故求其近似解,利用牛顿算法求解半定规划问题的γ-近似解,进而给出求解半定规划问题的牛顿法,并对算法进行收敛性分析.2.在无线传感器网络中,其节点定位技术非常重要,本文基于半定规划松弛模型求解节点的近似解给出几种重要的求解模型,结合数值实验评价比较了这些模型的优缺点.

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 半定规划
• 1.3 半定规划与其它凸优化问题的关系
• 1.4 半定规划的对偶理论
• 第二章 半定规划算法
• 2.1 内点算法
• 2.2 半定规划的牛顿方法
• 2.3 半定规划的一阶方法
• 第三章 半定规划在传感器网络定位中的应用
• 3.1 无线传感器网络定位的半定规划松弛模型
• 3.2 半定规划松弛模型的理论分析
• 3.3 半定规划松弛解的高秩性
• 第四章 数值实验
• 第五章 结论与展望
• 参考文献
• 致谢
• 附录 （攻读硕士学位期间已公开发表或待发表的论文）