Limited-memory LDL⊤ factorization of symmetric quasi-definite matrices with application to constrained optimization

We propose a generalization of the limited-memory Cholesky factorization of Lin and Moré (SIAM J. Sci. Comput. 21(1), 24–45, 1999) to the symmetric indefinite case with special interest in symmetric quasi-definite matrices. We use this incomplete factorization to precondition two formulations of linear systems arising from regularized interior-point methods for quadratic optimization. An advantage of the limited-memory approach is predictable memory requirements. We establish existence of incomplete factors when the input matrix is an H-matrix but our numerical results illustrate that the factorization succeeds more generally. An appropriate diagonal shift is applied whenever the input matrix is not quasi definite. As the memory parameter increases an efficiency measure of the preconditioner suggested by Scott and Tůma (2013) improves. The combination of the 3×3 block formulation analyzed by Greif, Moulding, and Orban (SIAM J. Optim. 24(1), 49–83, 2014), the SYMAMD ordering, and a moderate memory parameter results in encouraging performance.