Filippo Zanetti, Jacek Gondzio,
Abstract
A surprising result is presented in this paper with possible far reaching consequences
for any optimization technique which relies on Krylov subspace methods employed
to solve the underlying linear equation systems. In this paper the advantages of
the new technique are illustrated in the context of Interior Point Methods (IPMs).
When an iterative method is applied to solve the linear equation system in IPMs, the
attention is usually placed on accelerating their convergence by designing appropriate
preconditioners, but the linear solver is applied as a black box solver with a standard
termination criterion which asks for a sufficient reduction of the residual in the linear
system. Such an approach often leads to an unnecessary “oversolving” of linear
equations. In this paper a new specialized termination criterion for Krylov methods
used in IPMs is designed. It is derived from a deep understanding of IPM needs and
is demonstrated to preserve the polynomial worst-case complexity of these methods.
The new criterion has been adapted to the Conjugate Gradient (CG) and to the
Minimum Residual method (MINRES) applied in the IPM context. The new criterion
has been tested on a set of linear and quadratic optimization problems including
compressed sensing, image processing and instances with partial differential equation
constraints. Evidence gathered from these computational experiments shows that the
new technique delivers significant improvements in terms of inner (linear) iterations
and those translate into significant savings of the IPM solution time.
Key words: Quadratic Programming, Interior Point Methods, Conjugate Gradient, MINRES, Stopping criterion.