Interior-point Method with Polynomial Complexity and Superlinear Convergence for Linear Complementarity Problems.

摘要

For linear programming, a primal-dual interior-point algorithm was recently constructed by Zhang and Tapia that achieves both polynomial complexity and Q-superlinear convergence (Q-quadratic in the nondegenerate case). In this pa- per, we extend their results to quadratic programming and linear complementarity problems.