R.M. Gower and J. Gondzio
Abstract
At the heart of Newton based optimization methods is a sequence
of symmetric linear systems. Each consecutive system in this sequence
is similar to the next, so solving them separately is a waste
of computational effort. Here we describe automatic preconditioning
techniques for iterative methods for solving such sequences of systems
by maintaining an estimate of the inverse system matrix. We update
the estimate of the inverse system matrix with quasi-Newton type
formulas based on what we call an action constraint instead
of the secant equation. We implement the estimated inverses
as preconditioners in a Newton-CG method and prove quadratic
termination. Our implementation is the first parallel quasi-Newton
preconditioners, in full and limited memory variants. Tests
on logistic Support Vector Machine problems reveal that our
method is very efficient, converging in wall clock time before
a Newton-CG method without preconditioning. Further tests on a set
of classic test problems reveal that the method is robust.
The action constraint makes these updates flexible enough to mesh
with trust-region and active set methods, a flexibility that is not
present in classic quasi-Newton methods.
Key words: quasi-Newton method, inexact Newton method, preconditioners, linear systems, conjugate gradients, balancing preconditioner.