凸规划宽邻域原始-对偶势下降内点算法及其扩展

摘要

线性规划与非线性规划是最优化理论的两个重要分支，许多实际问题可以抽象成这两类问题．线性规划是一类特殊的凸规划，而凸规划又是一类简单的非线性规划．可见，凸规划与优化中的两大类规划有着密切联系．因此，对它的研究无论从理论价值还是实际应用方面来讲都是很有意义的．凸二次规划是一类简单的凸规划问题，研究它的算法不仅仅是为了解决凸二次规划本身，更是为了更好地求解其他非线性规划问题，因为一般的非线性函数在其极小点附近可以用一个二次函数很好地近似． 本文着重研究了凸二次规划的几个宽邻域内点算法，并分析了它们的多项式复杂性．全文共分五章，具体内容安排如下： 第一章概述内点算法的产生和研究现状以及相关的预备知识． 第二章是全文重点，主要讨论凸二次规划以及线性约束凸规划的宽邻域原始-对偶势下降内点算法，并给出算法的多项式复杂性证明． 第三章讨论凸二次规划的一个Mehrotra型预估-校正算法及其改进算法，并给出算法的多项式复杂性证明． 第四章给出初步的数值实验，验证本文算法的可行性以及有效性． 第五章对全文进行总结并对后续研究加以展望．