求解凸二次规划的一种二阶Mehrotra型预估-校正算法

A second-order Mehrotra-type predictor-corrector algorithm for solving convex quadratic programming

给出了求解凸二次规划的一种二阶Mehrotra型预估-校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O{n3/2log((x0)Ts0)/ε}。

A second-order Mehrotra-type predictor-corrector algorithm for solving convex quadratic programming is presented. Based on the work of Salahi et al., a safe strategy is introduced in the algorithm, which guarantees a positive desirable lower bound for the maximum feasible step in the corrector step and subsequently polynomial complexity. Since the search directions of the algorithm are not orthogonal, the way of computing the barrier parameter, as well as the complexity analysis is different from that in the linear case. Finally, through some technical lemmas, it is shown that the iteration complexity of the algorithm is O（n^3/2log（x^0）^TS^0/ε）in the worst case.