Olaf Schenk
University of Basel, Switzerland
E-mail: Olaf.Schenk@unibas.ch
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.
[1] 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.
[2] 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.
[3] O. Schenk and K. Gaertner, On fast factorization pivoting methods for
symmetric indefinite systems, Electronic Transaction of Numerical
Analysis, 23 (2006), pp. 158--179.
[4] 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,
pp. 321-341
Calendar of seminars