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.