论文部分内容阅读
非线性规划是运筹学的一个重要分支,在实际问题中有着非常广泛的应用.作为非线性规划中一类较简单的凸规划,因其与线性规划存在着某种特殊的联系而受到广大学者的关注。 现有许多线性规划的内点算法,最后也都被成功的扩展到了凸规划。 因而,研究凸规划的理论价值和实际应用的重要性就不言而喻。
本文主要研究了凸规划中一类特殊的凸二次规划问题,将线性规划的宽邻域内点算法拓展到凸二次规划,并利用类似于线性规划的相应算法的分析方法,证明了算法的多项式迭代复杂性。 最后,通过数值实验检验了算法的可行性及有效性。
全文共分四章,其具体内容安排如下:
第一章介绍内点算法的产生背景和国内外研究现状以及一些基本知识。
第二章给出了凸二次规划基于有限核函数的原始-对偶内点算法,证明了算法具有目前最好的大步校正算法的迭代复杂性,即O(√n log n log (n/ε))。
第三章讨论了凸二次规划的二阶Mehrotra型预估-校正算法及其改进算法,证明了算法的多项式复杂性。 由于迭代方向不再正交,算法在罚参数的校正和复杂性的分析上也有别于线性规划的情形。 最后,给出了初步的数值实验,检验算法的可行性及有效性。
第四章是全文的总结和展望。