Inertia Revealing Preconditioning For Large-Scale Nonconvex Constrained Optimization

Please always quote using this URN: urn:nbn:de:0297-zib-10314
  • 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 only guaranteed to be a descent direction 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's 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 do not provide the inertia. Here we present a preconditioner based on a multilevel incomplete $LBL^T$ 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 3D PDE-constrained optimal control problems, as well as 3D PDE-constrained 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Olaf Schenk, Andreas Wächter, Martin WeiserORCiD
Document Type:ZIB-Report
Tag:inertia; interior-point method; multilevel incomplete factorization; nonconvex constrained optimization
MSC-Classification:49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX] / 49Mxx Numerical methods [See also 90Cxx, 65Kxx] / 49M15 Newton-type methods
65-XX NUMERICAL ANALYSIS / 65Fxx Numerical linear algebra / 65F10 Iterative methods for linear systems [See also 65N22]
65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K10 Optimization and variational techniques [See also 49Mxx, 93B40]
Date of first Publication:2007/11/08
Series (Serial Number):ZIB-Report (07-32)
ISSN:1438-0064
Published in:Appeared in: SIAM J. Scientific Computing 31 (2008) 939-960