J.W. Tolle, ACMD and University of North Carolina

A.J. Kearsley, University of Massachusetts - Dartmouth

Large scale, nonlinear optimization problems are increasingly arising
in diverse applications. The group has been developing, enhancing,
and analyzing an algorithm, called * SPLIT*, for solving such
problems and has been applying * SPLIT* to problems in several
areas. The algorithm is based on the Sequential Quadratic Programming
(SQP) algorithm that solves general nonlinear problems by constructing
a sequence of quadratic subproblems, i.e., optimization problems with
a quadratic objective function and linear constraints. The group's
version of SQP relies heavily on * O3D*, an interior-point method
for solving large scale linear and quadratic programming problems that
is discussed elsewhere in this report.

Work this year has concentrated on two areas: developing procedures when there are many more constraints than variables; and deriving the underlying theoretical convergence properties of the algorithm. In the former, problems with many nonlinear constraints often have inconsistent linearized constraints when the iterates are far from the solution. A perturbation procedure has been devised that always provides consistent constraints and, under reasonable conditions, yields progress towards the solution. This technique was tried on problems with only several hundred variables, but several thousand constraints, with excellent success. Many other algorithms have completely failed on such problems.

A detailed global convergence analysis has been developed for *
SPLIT*. * SPLIT* depends on a ``merit function'' and a sequence of
approximate merit functions for assessing the progress towards a
solution. (A merit function is a scalar-valued function, say ,
with the property that a reduction in implies that progress has
been made.) The approximate merit functions are cheap to evaluate,
but no one of them is a true merit function, so special procedures
have been developed. It is shown that, if the quadratic subproblems
are solved completely, then the basic procedure is globally
convergent, i.e., it will converge to a first order KKT point from any
starting point. Further, if the quadratic subproblems are solved
approximately by taking any number of iterations of * O3D*, then
global convergence is also assured. (This allows a so-called
``truncated'' step that leads to significant computational savings.)
Finally, the perturbation procedure described above is shown to be
globally convergent if the perturbations to achieve consistency are
not too large.

The algorithm has many other enhancements and heuristic procedures that promote efficiency and overcome various pathologies. Not all of these can be guaranteed to maintain global convergence, but they have all led to a code that has been quite successful to date in solving interesting examples of practical, large scale nonlinear problems and the analysis puts these modifications on a firm theoretical foundation.

Generated by boisvert@nist.gov on Mon Aug 19 10:08:42 EDT 1996