University of Basel, Switzerland
We propose an inertia revealing preconditioning approach for the solution of
nonconvex constrained optimization problems. If interior methods with
second-derivative information are used for these optimization problems, a
linearized Karush-Kuhn-Tucker system of the optimality conditions has to be
solved. The main issue addressed is how to ensure that the Hessian is
positive definite in the null-space of the constraints while neither
adversely affecting the convergence of Newton's method or incurring a
significant computational overhead. In the nonconvex case, it is of
interest to find out the inertia of the current iteration system so that the
matrix may be modified a posteriori to obtain convergence to a minimum.
However, in order to not destroy the rapid convergence rate of the interior
method, the modification has only be performed in the cases where the
inertia is not correct and factorization methods [3, 4] are very often used
in order to compute the inertia information. In this work, we propose a new
inertia revealing preconditioned Krylov iteration to solve the linearized
Karush-Kuhn-Tucker system of optimality conditions. Our preconditioning
approaches for the symmetric indefinite Karush-Kuhn-Tucker systems are based
on maximum weighted matchings and algebraic multi-level incomplete $LBL^T$
factorizations [1, 2]. Finally, we present numerical results on several
large-scale three-dimensional examples of PDE-constrained optimizations in
the full space of states, control and adjoints variables with equality and
non-equality constraints and test them with artificial as well as clinical
data from biomedical cancer hyperthermia treatment planning.
 M. Hagemann and O. Schenk, Weighted matchings for the preconditioning of
symmetric indefinite linear systems, SIAM Journal of Scientific Computing,
28 (2006), pp. 403-420.
 O. Schenk, M.Bollhoefer, and R. Roemer, On large-scale diagonalization
techniques for the Anderson model of localization, SIAM Journal of
Scientific Computing, 28 (2006), pp. 963-983.
 O. Schenk and K. Gaertner, On fast factorization pivoting methods for
symmetric indefinite systems, Electronic Transaction of Numerical
Analysis, 23 (2006), pp. 158--179.
 O. Schenk, A. Waechter, and M. Hagemann, Matching-based preprocessing
algorithms to the solution of saddle-point problems in large-scale
nonconvex interior-point optimization, Journal of Computational
Optimization and Applications, Volume 36, Numbers 2-3 / April, 2007,