对称锥互补问题的内点算法及在传感器网络定位中的应用研究

对称锥互补问题是对称锥规划的推广，它是一类重要的均衡优化问题，广泛应用于通信、工程、经济管理等领域，内点算法是求解该问题的有效算法之一. 核函数在内点算法的设计和分析中起着重要的作用，它不仅可以定义新的搜索方向，而且可以度量当前迭代点与中心路径的距离. 本项目将研究新的核函数的构造技术及其基本性质，借助欧几里德若当代数技术，基于新的核函数设计和分析求解对称锥非线性互补问题的内点算法，有效缩减大步校正和小步校正内点算法在理论与实践之间的间隙；基于核函数的局部SC性质，揭示核函数在内点算法的复杂性中的性态；设计和分析求解对称锥线性互补问题的全NT步不可行内点算法；应用对称锥规划或对称锥互补问题松弛方法研究传感器网络定位问题，建模、编写内点算法程序求解.该项目旨在设计和分析求解对称锥非线性互补问题的有效内点算法，为研究线性互补问题、半正定互补问题及二阶锥互补问题提供统一的框架.

对称锥互补问题是一类重要的均衡优化问题，包括经典的线性互补问题、二阶锥互补问题和半定互补问题。尽管它不是优化问题，但却与优化问题密切相关。事实上，对称锥规划的KKT条件可以转化为对称锥互补问题。因而，研究该问题可为一般的非线性规划提供统一的理论分析框架。本项目研究对称锥互补问题的内点算法及在传感器网络定位中的应用。主要成果如下：.1）构造了若干新的Eligible-核函数。它们不仅可以被用来定义新的搜索方向，而且可以用来度量新的迭代点与中心路径之间的偏离距离。同时，研究了核函数及其对应的障碍函数的基本代数性质。.2）利用欧几里德若当代数，用统一的方法设计和分析了求解笛卡尔P*(k)-对称锥线性互补问题的核函数内点算法，得到大步和小步校正核函数内点算法迄今为止最好的理论迭代界，有效缩减了二者在理论与实践之间的间隙。该理论分析包括P*(k)-线性互补问题，笛卡尔P*(k)-二阶锥线性互补问题和笛卡尔P*(k)-半定线性互补问题的情形。而且，基于核函数的局部SC性质，揭示了核函数在内点算法的复杂性中的性态。.3）利用代数等价变换的思想，定义了一类新的搜索方向。基于Roos和Darvay两个特殊的搜索方向分别设计和分析了求解笛卡尔P*(k)-对称锥线性互补问题的全NT步内点算法，得到小步校正内点算法迄今为止最好的理论迭代界。同时，还研究了凸二次对称锥规划的全NT步原始-对偶内点算法，为研究一类优化问题提供统一的理论分析框架。.4）传感器网络定位问题是一个具有挑战性的优化问题。提出了传感器网络定位问题的一个改进的半定规划松弛模型，利用核函数内点算法求解并验证模型的可靠性。另外，研究了各种随机游动策略，特别是多重随机游动。通过分析多重随机游动的首达时，给出了其相应的概率分布和各阶矩的表达式，并证明了多重随机游动首达质点的收敛性。该结果在复杂网络中识别最优路经上具有重要的应用价值。.依托本项目，课题组撰写学术专著1本。在优化领域的权威杂志：Journal of Global Optimization, Journal of Optimization Theory and Application, Optimization Methods and Software等上发表14篇学术论文，其中SCI收录13篇，外文期刊1篇。国际学术会议论文1篇且被EI收录。