In this paper we develop an interior-point primal-dual long-step path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of an iterative (linear system) solver. We propose a new linear system, which we refer to as the \emph{augmented normal equation} (ANE), to determine the primal-dual search directions. Since the condition number of the matrix associated with the ANE may become large for degenerate CQP problems, we use a maximum weight basis preconditioner introduced by Resende and Veiga to better condition this matrix. Using a result obtained by Monteiro, O'Neal, and Tsuchiya, we establish a uniform bound, depending only on CQP data, on the number of iterations required for the iterative solver to obtain a sufficiently accurate solution to the ANE. Since the iterative solver can only generate an approximate solution to the ANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a way to compute an inexact primal-dual search direction so that the Newton equation corresponding to the primal residual is satisfied exactly, while the one corresponding to the dual residual contains a manageable error which allows us to establish a polynomial bound on the number of iterations of our method.
Citation
Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, May 2004.
Article
View An Iterative Solver-Based Infeasible Primal-Dual Path-Following Algorithm for Convex QP