UC San Diego

The KKT systems arising in nonlinearly constrained optimization problems may not have correct inertia, and therefore must be modified to avoid convergence to nonoptimal KKT points. Matrix factorizations can determine the inertia of a general symmetric matrix but are too costly in the PDE contextIn PDE-constrained optimization, KKT systems are generally solved with preconditioned iterative methods that are unable to detect whether the current matrix has correct inertia. Moreover, the preconditioners assume the existence of a preconditioner for the underlying PDE. Methods are discussed that solve the constrained problem by minimizing a sequence of smooth primal-dual merit functions. The Newton equations are solved approximately with a variant of the preconditioned conjugate-gradient (PCG) method that naturally determines when the regularized KKT system for the constrained problem has incorrect inertia. Convergence is accelerated with a sparsity exploiting preconditioner that implicitly defines a positive-definite system. The preconditioning strategy is entirely algebraic and is based on an incomplete factorization of an equivalent symmetric indefinite system. It explicitly takes advantage of dual regularization, and in the PDE constrained context, does not require a preconditioner for the underlying PDE