凸二次规划的一种宽邻域预估-校正算法

Zhao对线性规划提出了一种基于邻近度量函数最小值的宽邻域预估-校正算法, 并证明了算法的多项式复杂性。基于他的思路,将此方法拓展到凸二次规划,设计了一种新的基于邻近度量函数最小值的宽邻域预估-校正算法。由于新算法的迭代方向向量Δx,Δs不再满足正交性,因此算法的收敛性分析不同于线性规划的情形,同时也证明了新算法具有 已知的最好迭代复杂性Onln(x0)Ts0ε,初步数值实验验证了算法的有效性。

A wide-neighborhood predictor-corrector algorithm for convex quadratic programming

Zhao presented a wide-neighborhood predictor-corrector algorithm for linear programming via the least values of proximity measure functions, and he also proved the algorithm has the polynomial iteration complexity. Zhao′s algorithm was extended to convex quadratic programming and a new wide-neighborhood predictor-corrector algorithm was presented based on the minimums of proximity measure functions.　Since the new search direction Δx and Δs are no longer orthogonal, the convergence analysis is different from that of the linear programming. The new algorithm has been proved to retain the so far best known iteration complexity of Onln(x0)Ts0ε iterations. Moreover, a rough numerical experiment shows the feasibility and efficiency of this new algorithm.