一个关于二次规划问题的分段线性同伦算法

A PIECEWISE-LINEAR HOMOTOPY ALGORITHM FOR QUADRATIC PROGRAMMING

本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的，在某些条件下可能是多项式时间算法。

In this paper a piecewise-linear homotopy algorithm for quadratic programming is developed.This algorithm may be regarded as a variant of exterior point penalty function methods.For the quadratic programming problem which can be solved by means of exterior point SUMT,a stationary point of the Lagrangian of the problem can be obtained by this algorithm with finite pivoting operations.Some numerical results for a large number of random convex quadratic programming problems show that the new algorithm is efficient and might be a polynomial-time algorithm under some conditions.