Stanford 50: State of the Art and Future Directions of Computational Mathematics and Numerical Computing


  • March 29, 2007
  • 4:00 pm - 4:25 pm

Iterative methods for generalized saddle-point problems

Philip Gill (UC San Diego)

We consider iterative methods for generalized saddle-point problems that arise in interior methods for general nonlinear optimization. Interior methods define a sequence of KKT systems that represent the symmetrized (but indefinite) equations associated with Newton's method for satisfying the perturbed optimality conditions. These equations involve both the primal and dual variables and become increasingly ill-conditioned as the optimization proceeds. In this context, an iterative linear solver must not only handle the ill-conditioning but also detect KKT matrices with incorrect inertia.

We focus on the application of the conjugate-gradient method to a certain "doubly-augmented system'' that is positive definite with respect to both the primal and the dual variables. This property means that a standard preconditioned CG method involving both primal and dual variables will either terminate successfully or detect if the KKT matrix has wrong inertia.

Constraint preconditioning is a well-known technique for preconditioning the CG method on saddle-point problems. A family of constraint preconditioners is proposed that provably eliminates the inherent ill-conditioning. A considerable benefit of combining constraint preconditioning with the doubly-augmented system is that the preconditioner need not be applied exactly.

The talk is based on joint work with Anders Forsgren and Joshua Griffin.

Stanford University Home Page