Using incomplete indefinite LDL^T preconditioning for inexact interior point methods for linear programming

MaRDI QIDQ6290101zbMATH OpenFDO

Authors Robert Luce

Publication date 14 August 2017

Abstract: Most linear algebra kernels in interior point methods for linear programming require the solution of linear systems of equation with the matrix $N=A^T{D}^{-1}A$ (or $A{D}^{-1}{A}^T$), where $A$ denotes the constraint matrix of the linear program. This matrix $N$ arises from the reduced KKT system by block elimination. If the number of non-zeros in $N$ or in its Cholesky factorization $N=L{L}^T$ is very large, the computational cost and memory requirement to solve the linear systems of equations with $N$ may be prohibitively large. In this work we implement an interior point method described by R. Freund and F. Jarre. Forming the normal equation matrix $N$ is avoided altogether and we work with the reduced KKT system instead. We solve the linear systems for the Newton directions iteratively only to low accuracy using SQMR and an indefinite multilevel preconditioner. Preliminary numerical results are encouraging.

This page was built for publication: Using incomplete indefinite $LDL^T$ preconditioning for inexact interior point methods for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6290101)