Nonlinear Programming

As outlined earlier, nonlinear programming (NLP) problems are intrinsically more difficult to solve than linear programming (LP) and quadratic programming (QP) problems. Because of the possibility of multiple feasible regions and multiple locally optimal points within such regions, there is no known way to determine with certainty that the problem is infeasible, the objective unbounded, or that an optimal solution is the "global optimum" across all feasible regions. However, many common NLP problems have a simpler structure than this general description, and are more amenable to solution.

It is important to realize that an NLP solver, like the one in our spreadsheet Solvers, applies the same methods to all problems, even those that are really LPs or QPs. If you don't check the Assume Linear Model box in the Solver Options dialog (or in the enhanced solvers, if you don't select another solver from the dropdown list in the Solver Parameters dialog), the default GRG nonlinear solver will be used. This solver may have difficulty with LP or QP problems that could have been solved easily with one of the other solvers.

General Nonlinear Methods

A good overview of the methods of nonlinear programming is found in Winston's Operations Research: Applications and Algorithms, listed in Recommended Books. For a more sophisticated treatment (requiring some background in linear algebra and vector calculus), consult one of the following:

Practical Optimization by Gill, Murray and Wright, published by Academic Press. ISBN 0-12-283952-8.

Practical Methods of Optimization, 2nd Edition by R. Fletcher, published by John Wiley. ISBN 0-471-91547-5.

The GRG Method

In the standard spreadsheet Solvers, NLP problems are solved with the GRG (Generalized Reduced Gradient) method as implemented in Lasdon and Waren's GRG2 code. This method and specific implementation have been proven in use over many years as one of the most robust and reliable approaches to solving difficult NLP problems.

The GRG method is subject to the intrinsic limitations cited above on its ability to find the globally optimal solution. However, limited guarantees can be made about the GRG method's ability to find a "local optimum," in particular where the objective function and all of the constraints are twice continuously differentiable. When these are combined with your knowledge of problem structure in a specific case, the result will often be a definitive "optimal solution." For more information on this issue, please consult If You Aren't Getting the Solution You Expect and GRG Solver Stopping Conditions.

As with the Simplex method, the GRG method in the standard spreadsheet Solvers uses a "dense" problem representation, and its memory and solution time increases with the number of variables times the number of constraints. It is also subject to problems of numerical instability, which may be even more severe than for LP and QP problems. For the AMPL and AMPL Plus Modeling Systems, Frontline Systems offers a Large-Scale NLP Solver based on Lasdon, Waren and Smith's LSGRG code, which uses sparse storage methods and more sophisticated numerical techniques specific to nonlinear models.

For a technical description of the nonlinear GRG method included with our spreadsheet Solvers, please consult the following references to the academic literature:

L.S. Lasdon, A. Waren, A. Jain and M. Ratner. Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming. ACM Transactions on Mathematical Software 4:1 (1978), pp. 34-50.

L.S. Lasdon and S. Smith. Solving Sparse Nonlinear Programs Using GRG. ORSA Journal on Computing 4:1 (1992), pp. 2-15.

Copyright © 1996 Frontline Systems Inc.
Last modified: December 01, 1996