An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners

Abstract

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 [Z. Lu, R.D.C. Monteiro, and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17(1) (2006), pp. 287–310], we propose a new linear system, which we refer to as the 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 [Z. Lu, R.D.C. Monteiro, and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17(1)(2006), pp. 287–310] is that, instead of using the maximum weight basis (MWB) preconditioner in the aforesaid 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 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.

Keywords:

• convex quadratic programming
• iterative linear solver
• primal-dual path-following methods
• interior-point methods
• hybrid augmented normal equation
• inexact search directions
• polynomial convergence

AMS Subject Classification :

• 65F10
• 65F35
• 90C20
• 90C25
• 90C51

Acknowledgements

Z. Lu was partially supported by SFU Presidential Grant and NSERC Discovery Grant. R.D.C. Monteiro was partially supported by NSF Grants CCR-0203113 and CCF-0430644 and CCF-0808863 and ONR Grants N00014-05-1-0183 and N00014-08-1-0033. J.W. O'Neal was supported in part by the NDSEG Fellowship Program sponsored by the Department of Defense.