框式约束凸二次规划问题的内点算法

论文摘要

本文主要研究了框式约束的凸二次规划问题。这类问题出现在很多的应用领域。近年来提出的原始对偶内点方法是一类有效的算法。但是考虑到该问题是不等式约束凸二次规划的一种较简单的形式,即它的可行域X={x|l≤x≤m,x∈R~n}是一个十分简单的超长方体,所以我们给出了一种直接在X上的内点迭代。本文主要分为以下三个部分: 第一部分介绍了本文的研究背景。第二部分给出了求此类问题的一种新的内点算法,该方法通过在内含于超长方体内的一系列超椭球体上求最优解,来逐步逼近于原问题的最优解。并给出了该算法全局收敛性的证明。在第三部分,对于框式约束问题,我们提出了一种势函数下降的内点算法。每次迭代中搜索方向由一个线性方程组解出,并利用Armijio准则进行线搜索,同时使势函数的值减小。并证明了该算法是全局收敛的。

论文目录

• Contents
• Abstract in English
• Abstract in Chinese
• 1 Introduction
• 2 An Interior-point Algorithm for Convex Quadratic Programming with Box Constraints
• 2.1 Introduction
• 2.2 Preliminaries
• 2.3 Our Algorithm
• 2.4 Convergence Analysis
• 2.5 Numerical Results
• 2.6 Conclusions
• 3 A Potential-reduction Algorithm for Convex Quadratic Programming
• 3.1 Introduction
• 3.2 Preliminaries
• 3.3 Our Algorithm
• 3.4 Convergence Analysis
• 3.5 Numerical Results
• 3.6 Conclusions
• Bibliography
• Acknowledgements