一种新的凸二次规划的Mehrotra型预估–校正算法(英文)  

A New Mehrotra-type Predictor-corrector Algorithm for Convex Quadratic Optimization

作　　者：李卫滑[1] 张明望[1] 陈东海[1] 

机构地区：[1]三峡大学理学院,宜昌443002

出　　处：《工程数学学报》2011年第6期736-746,共11页Chinese Journal of Engineering Mathematics

基　　金：The Natural Science Foundation of Hubei Province(2008CDZ047)

摘　　要：Mehrotra型预估–校正算法是众多基于内点算法的优化软件包的核心算法.最近,Salahi等人对线性规划提出一种新的Mehrotra型预估–校正算法.该算法不仅有多项式复杂性还具有良好的实际计算效果.本文将其算法推广至凸二次规划,这种算法在预估步最大可行步长高于某一阈值时将其削减,若首次削减仍没得到合适的校正步长,则将预估步长进行再削减,从而保证校正步步长有合适下界.算法在最坏情况下的迭代复杂性为O(n3/2 logn/ε).最后,Matlab仿真实验验证了算法的可行性.Mehrotra-type predictor-corrector algorithms are the core of most interior point methods. Salahi et al recently proposed a new Mehrotra-type predictor-corrector algorithm for linear optimization, which is a polynomial time algorithm, their algorithm maintains its efficiency in practice. This algorithm is extended in this paper to convex quadratic optimization problems. The new algorithm cuts the maximum step size in the predictor step when it is above a certain threshold. If this cut doesn’t provide a desirable step size, we cut it again and deduce a lower bound for the step size in the corrector step. It is shown that the iteration complexity of the algorithm is O（n 3/2 log （x0）T s0/ ε ）, where （x0, s0） is the initial point and ε is the tolerance. Furthermore, the numerical example indicates that our algorithm is efficient.

关 键 词：凸二次规划 内点算法 Mehrotra型预估–校正算法 多项式复杂性 

分 类 号：O221.2[理学—运筹学与控制论]