In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors' previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to determine the primal-dual search directions. Since the iterative linear solver can only generate an approximate solution to the HANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a recipe to compute an inexact primal-dual search direction, based on a suitable approximate solution to the HANE. The second difference between this paper and \cite{ONE04} is that, instead of using the maximum weight basis (MWB) preconditioner in the above recipe for constructing the inexact search direction, this paper proposes the use of any member of a whole class of preconditioners, of which the MWB preconditioner is just a special case. The above proposed recipe allows us to (i) establish a polynomial bound on the number of iterations performed by our path-following algorithm and (ii) establish a uniform bound, depending on the quality of the preconditioner, on the number of iterations performed by the iterative solver.

## Citation

Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205, June 2005