Summary:
Near the solution, optimization algorithms based on Newton's method generally demonstrate
quadratic convergence. Often, the rate-limiting step in these methods is the calculation of search
directions, which involves solving symmetric linear systems of equations of the form
Ax = b at each
iteration. For large-scale problems, these equations can be solved using conjugate-gradient
(CG) methods whenever
A is positive definite. However, CG methods can
break down if
A is indefinite because the
LDL' factorization of the
tridiagonal matrix
T in the underlying Lanczos process is unstable.
(Here,
L is unit lower triangular and
D is diagonal.)
This instability can be overcome by diagonal pivoting strategies that
compute an
LBL' factorization of
T instead,
where
B is
block diagonal with 1x1 and 2x2 blocks.
It can be proven that solving a symmetric tridiagonal linear system using a factorization
we proposed with this pivoting strategy is normwise backwards stable,
with the additional feature that it reduces to the
LDL' factorization whenever
T is positive
definite. This pivoting strategy was used to solve indefinite systems (like the KKT
system arising in optimization or saddle-point systems in numerical PDE).
On these systems, the performance of a
symmetric indefinite factorized CG (ASIFCG) method we developed has a comparable
convergence behavior to those of well-established methods like
SYMMLQ for solving symmetric indefinite systems;
however, it was shown that ASIFCG is more computationally efficient.
More recently, this diagonal pivoting approach was generalized to
solve
unsymmetric tridiagonal linear systems, and similar proofs of stability were also obtained.
Collaborators:
James Bunch (UC San Diego),
Jennifer Erway (Wake Forest)
Students:
Joseph Tyson (Wake Forest)