A New Implementation of Fletcher's Exact Merit Function for Nonlinear Optimization (12rit180)

Objectives

Nonlinear optimization is widely regarded as a vital tool of applied
mathematics. Nonlinear optimization problems occur in their own right
in such diverse application areas as resource allocation, machine
learning, tumor detection, aerodynamics, medical treatment planning,
and numerous other fields, but also as subproblems in discretized
optimal control and optimization with partial differential equation
constraints. Many practitioners and researchers rely heavily on
software for solving large-scale nonlinear programs. Such software
must be robust---i.e., can dependably find solutions even for
difficult or ill-posed problems---and it must be fast. However, the
most common algorithms rely on explicitly forming and factorizing
sequences of large linear systems at each iteration. This can be
prohibitively expensive in many large-scale applications. It is
therefore crucial to develop efficient matrix-free methods.

Our aim is to devise and analyse an efficient implementation of a
method based on Fletcher's exact merit function [2]. This merit
function is unusual because it is smooth---in contrast, most other
known merit functions are non-smooth, which leads to theoretical and
practical difficulties.

We already have a functional implementation of our algorithms for
equality-constrained problems of the form
$$min_x quad f(x) quad text{subject to} quad c(x) = 0, $$
where $f : mathbb{R}^n to mathbb{R}$ and $c : mathbb{R}^n to
mathbb{R}^m$ are smooth. This confirms that the method is
competitive with other modern methods. This is surprising, because
Fletcher's smooth merit function has been considered computationally
impractical. However, we have discovered that it can be efficiently
evaluated by leveraging recent technologies for linear least-squares
problems. A corresponding paper documenting our approach is now in
preparation.

There are two remaining challenges: extend the approach to handle
inequality constraints $c(x)le0$, and modify the merit function to be
robust to degeneracy. We believe that we can handle both of these
challenges by embedding the merit function within a primal-dual
regularized interior framework. The scaffold for the algorithm
is fairly clear to us, but further work is needed to flesh out the
details and the corresponding convergence theory and
implementation. This approach circumvents Fletcher's original proposal
for inequality constraints, which causes his merit function to exhibit
non-smoothness across active-set boundaries.

This approach builds on our previous work on exact regularization of
primal-dual interior methods for convex quadratic programming
[4]. That project gave us a deep understanding of the interaction
between regularization (needed to counteract the effects of
degeneracy) and the convergence of an algorithm. Moreover, the
regularized linear systems used in that research project bear
remarkable similarity to the least-squares problems needed to
efficiently evaluate Fletcher's merit function. This has allowed us to
make quick progress.

Our hope is that a period of focused work at BIRS will allow us to
finalize the convergence analysis of the generalization to inequality
constraints, thus making our method suitable for general nonlinear
optimization problems. If time allows, we hope to be able to
experiment with inexact subproblem solves and identify the parts of
the convergence theory that will need adjustments.

We have been collaborating on this paper over email and have been
making steady progress. However, an intensive session of working
face-to-face and away from distractions of the university is needed in
order to finish and submit our paper.

To summarize, our goals for the present proposal are as follows:

1. To generalize the convergence theory of the equality-constrained case to the inequality-constrained case;
2. To finalize the implementation of the inequality-constrained case;
3. To design a strategy for inexact subproblem solves and, if time allows, to sketch an initial implementation;
4. To draft a paper describing the regularization stratiegies and convergence theory.

References

1. M. Arioli and D. Orban, *Iterative Methods for Quasi-Definite Systems*, Cahier du GERAD G-2012-xx, GERAD, Montr'eal, Canada, 2012.
2. R. Fletcher, *A Class of Methods for Non-Linear Programming III: Rates of Convergence*, Numerical Methods for Nonlinear Optimization, Edited by F. A. Lootsma, Academic Press, New York, New York, pp. 371--393, 1973
3. A. Forsgren and P. E. Gill, Primal-dual interior methods for nonconvex nonlinear programming. *SIAM Journal on Optimization*, 8(4):1132--1152, 1998.
4. M. P. Friedlander and D. Orban. *A primal-dual regularized
interior-
point method for convex quadratic programs*, 2011. To appear in
Mathematical Programming Computation.