Inexact Constraint Preconditioners
for Linear Systems Arising in Interior Point Methods

Technical Report MS 2005-002

L. Bergamaschi, J. Gondzio, Manolo Venturin and G. Zilli,

Issues of indefinite preconditioning of reduced Newton systems arising in optimization with interior point methods are addressed in this paper. Constraint preconditioners have shown much promise in this context. However, there are situations in which an unfavorable sparsity pattern of Jacobian matrix may adversely affect the preconditioner and make its inverse representation unacceptably dense hence too expensive to be used in practice. A remedy to such situations is proposed in this paper. An approximate constraint preconditioner is considered in which sparse approximation of the Jacobian is used instead of the complete matrix. Spectral analysis of the preconditioned matrix is performed and bounds on its non-unit eigenvalues are provided. Preliminary computational results are encouraging.

Key words: Interior-point methods, Iterative solvers, Preconditioners, Approximate Jacobian.

PDF MS05-002.pdf.

Written: November 4, 2005, revised March 1, 2006 and in May 22, 2006.
Published: Computational Optimization and Applications 36 (2007) No 2-3, pp. 137-147.
See Erratum (9 June 2008): MS05-002erratum.pdf
Published: Computational Optimization and Applications 49 (2011) pp. 401-406. DOI 10.1007/s10589-009-9298-6

Related Software:
HOPDM Higher Order Primal Dual Method.