317. A low-rank error correction technique for improving approximate factorisation preconditioners
Invited abstract in session TC-2: Developments in interior point methods, stream Developments in interior point methods.
Thursday, 11:25 - 12:40Room: M:O
Authors (first author is the speaker)
| 1. | Andreas Bock
|
Abstract
Interior point methods (IPM) require the solution of linear systems of equations for the Newton directions. These linear systems become increasingly ill-conditioned as the IPM progresses, so preconditioning is mandatory when using the conjugate gradient method within an inexact Newton method. We propose a preconditioner based on nearness in the Bregman log determinant divergence. The form of the proposed preconditioner is given as the sum of a user-specified approximate factorisation (e.g. incomplete Cholesky) plus a low-rank correction term. The latter is based on the (in general indefinite) approximate factorisation error, and is generally different from one obtained by a truncated singular value decomposition (TSVD). This gives rise to a new type of truncation which we compare with the TSVD in terms of convergence of the preconditioned conjugate gradient method (PCG). We show numerous examples where PCG converges to a small tolerance using the proposed preconditioner, whereas PCG using a TSVD-based preconditioner fails. We also consider SuiteSparse matrices from IPM from linear programming that do not admit an incomplete Cholesky factorisation by default, and present a robust incomplete Cholesky preconditioner based on the proposed methodology.
Keywords
- Large- and Huge-scale optimization
Status: accepted
Back to the list of papers