Inertia-revealing preconditioning for large-scale nonconvex constrained optimization

Olaf Schenk*, Andreas Wachter, Martin Weiser

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

Fast nonlinear programming methods following the all-at-once approach usually employ Newton's method for solving linearized Karush-Kuhn-Tucker (KKT) systems. In nonconvex problems, the Newton direction is guaranteed to be a descent direction only if the Hessian of the Lagrange function is positive definite on the nullspace of the active constraints; otherwise some modifications to Newton's method are necessary. This condition can be verified using the signs of the KKT eigenvalues (inertia), which are usually available from direct solvers for the arising linear saddle point problems. Iterative solvers are mandatory for very large-scale problems, but in general they do not provide the inertia. Here we present a p reconditioner based on a multilevel incomplete LBLT factorization, from which an approximation of the inertia can be obtained. The suitability of the heuristics for application in optimization methods is verified on an interior point method applied to the CUTE and COPS test problems, on large-scale three-dimensional (3D) PDE- constrained optimal control problems, and on 3D PDE-constrain ed optimization in biomedical cancer hyperthermia treatment planning. The efficiency of the preconditioner is demonstrated on convex and nonconvex problems with 150 3 state variables and 150 2 control variables, both subject to bound constraints.

Original languageEnglish (US)
Pages (from-to)939-960
Number of pages22
JournalSIAM Journal on Scientific Computing
Volume31
Issue number2
DOIs
StatePublished - Dec 1 2008

Keywords

  • Biomedical cancer application
  • Indefinite systems
  • Inertia
  • Interior point method
  • Multilevel preconditioning
  • Nonconvex constrained optimization
  • Optimal control

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Inertia-revealing preconditioning for large-scale nonconvex constrained optimization'. Together they form a unique fingerprint.

Cite this