Next: Interior Point Methods Up: Mathematical Software for Previous: Approximating the Permanent

### Large Scale Nonlinear Programming

P.T. Boggs, ACMD
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.

Next: Interior Point Methods Up: Mathematical Software for Previous: Approximating the Permanent

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