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.
Bibliographical noteFunding Information:
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.
Copyright 2011 Elsevier B.V., All rights reserved.
- Convex quadratic programming
- Hybrid augmented normal equation
- Inexact search directions
- Interior-point methods
- Iterative linear solver
- Polynomial convergence
- Primal-dual path-following methods