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.
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.