Rees, Tim; Greif, Chen A preconditioner for linear systems arising from interior point optimization methods. (English) Zbl 1155.65048 SIAM J. Sci. Comput. 29, No. 5, 1992-2007 (2007). Authors’ summary: We explore a preconditioning technique applied to the problem of solving linear systems arising from primal-dual interior point algorithms in linear and quadratic programming. The preconditioner has the attractive property of improved eigenvalue clustering with increased ill-conditioning of the \((1,1)\) block of the saddle point matrix. It fits well into the optimization framework since the interior point iterates yield increasingly ill-conditioned linear systems as the solution is approached. We analyze the spectral characteristics of the preconditioner, utilizing projections onto the null space of the constraint matrix, and demonstrate performance on problems from the NETLIB and CUTEr test suites. The numerical experiments include results based on inexact inner iterations. Reviewer: Stefan Mititelu (Bucureşti) Cited in 3 ReviewsCited in 21 Documents MSC: 65K05 Numerical mathematical programming methods 90C51 Interior-point methods 90C05 Linear programming 90C20 Quadratic programming 65F10 Iterative numerical methods for linear systems 65F35 Numerical computation of matrix norms, conditioning, scaling Keywords:block preconditioners; saddle point systems; primal-dual interior point methods; augmentation; linear pogramming; quadratic programming; ill-conditioned linear systems; numerical experiments Software:Ipopt; LIPSOL; SifDec; CUTEr; NETLIB LP Test Set PDFBibTeX XMLCite \textit{T. Rees} and \textit{C. Greif}, SIAM J. Sci. Comput. 29, No. 5, 1992--2007 (2007; Zbl 1155.65048) Full Text: DOI Link