论文部分内容阅读
自1984年第一个具有实用性的多项式算法-Karmarkar算法发表以来,在国内外众多优化专家和学者的共同努力下,内点算法的研究已取得了丰硕的成果.内点算法已成为求解线性优化问题非常重要且高效的算法之一,它不仅具有多项式复杂性,而且其实际计算性能也可以与单纯形法相媲美.如今,内点算法已被广泛地应用去求解半定优化(SDO)问题、凸二次SDO问题、对称锥优化等问题. 本文提出了基于新的核函数求解线性优化问题和SDO问题的大步校正原始-对偶内点算法,完成了新算法的多项式复杂性证明,而且通过数值实验验证了提出算法的可行性和有效性. 全文共分五章,第一章介绍了内点算法的基本概念、算法模型、研究现状、以及相关的基本符号约定;第二章提出了线性优化问题基于新的核函数的大步校正原始-对偶内点算法,证明了算法的迭代复杂性阶,并用数值实验验证了算法的实际计算效果;第三章通过采用Nesterov-Todd对称策略将第二章的算法推广到求解SDO问题,给出了算法的迭代复杂性的证明,且通过一个实例验证了算法的实际计算性能;第四章基于Darvay所提出的搜索方向,对凸二次SDO问题提出了一种新的full-Newton步小步校正.原始-对偶内点算法,并证明了算法的迭代复杂性;第五章对全文总结并对后续研究工作进行展望.