Back to Search
Start Over
An iterative solver-based long-step infeasible primal-dual path-following algorithm for convex QP based on a class of preconditioners.
- Source :
-
Optimization Methods & Software . Feb2009, Vol. 24 Issue 1, p123-143. 21p. - Publication Year :
- 2009
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGORITHMS
*LITERATURE
*LINEAR systems
*ALGEBRA
*FOUNDATIONS of arithmetic
Subjects
Details
- Language :
- English
- ISSN :
- 10556788
- Volume :
- 24
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Optimization Methods & Software
- Publication Type :
- Academic Journal
- Accession number :
- 35656844
- Full Text :
- https://doi.org/10.1080/10556780802414049