Author(s)： Lu Li and Kim-Chuan Toh

J. Math-for-Ind. 2B (2010) 199-212.

• File： JMI2010B-9.pdf (185KB)

Abstract
In this paper, we design an inexact primal-dual infeasible path-following algorithm for convex quadratic programming over symmetric cones. Our algorithm and its polynomial iteration complexity analysis give a unified treatment for a number of previous algorithms and their complexity analysis. In particular, our algorithm and analysis includes the one designed for linear semidefinite programming in "Math. Prog. 99 (2004), pp. 261--282". Under a mild condition on the inexactness of the search direction at each interior-point iteration, we show that the algorithm can find an $\epsilon$-approximate solution in $O(n^2\log(1/\epsilon))$ iterations, where $n$ is the rank of the underlying Euclidean Jordan algebra.

Keyword(s).　 semidefinite programming, symmetric cone programming, infeasible interior point method, inexact search direction, polynomial complexity