《《2016 A Preconditioner for Linear Systems Arising from Interior Point Optimization Methods》.pdf

A PRECONDITIONER FOR LINEAR SYSTEMS ARISING FROM INTERIOR POINT OPTIMIZATION METHODS TIM REES∗ AND CHEN GREIF† Abstract. 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. Key words. block preconditioners, saddle point systems, primal-dual interior point methods, augmentation AMS subject classifications. 65F10, 65K05 1. Introduction. Interior point methods for solving linear and quadratic pro- gramming problems have been gaining popularity in the last two decades. These methods have forged connections between previously disjoint fields and allowed for a fairly general algebraic framework to be used; see, for example, [11] for a compre- hensive survey. The size of many problems of interest is very large and the matrices involved are frequently sparse and often have a special structure. As a result, there is an increasing interest in iterative solution methods for the saddle point linear systems that arise throughout the iterations. The general optimization framework is as follows. Consider the quadratic pro- gramming (QP) pr