Dominique Orban, GERAD and Ecole Polytechnique

Abstract

We describe the properties of a smooth exact merit function first proposed by Fletcher (1970), and the details of our own implementation. The main computational kernel is solving structured linear systems. We show how to solve these systems efficiently by storing a single factorization per iteration when the matrices are available explicitly. We also give a factorization-free implementation. The penalty function shows particular promise when such linear systems can be solved efficiently, e.g., for PDE-constrained optimization problems where efficient preconditioners exist. Regularization provides robustness towards the solution of degenerate problems. A special feature of our implementation is the ability to evaluate inexact first and second derivatives of the merit function while preserving global convergence.

Co-Authors: Ron Estrin, Michael Saunders, Michael Friedlander