Operations Research Models and Methods / Computation / Mathematical Programming /
Nonlinear Programming


Solving the Problem

Given a starting vector for the decision variables, the Excel Solver program uses a search procedure to move to a local optimum. That is, a point in the feasible region such that no improvement can be made by small perturbations from the point. It is a known result that when maximizing a concave objective function with linear constraints every local optimum is a global optimum, the solution that is the best of all feasible solutions. Since the objective function terms for this example are concave, when the Solver program terminates at a point with an indication of optimality, the point should be the global optimum.

In general, we cannot be sure that the Excel Solver or any nonlinear programming algorithm will terminate at an optimal point unless some rather stringent conditions are satisfied. These conditions are the subject of nonlinear programming textbooks. For example if the objective function terms were convex, rather than concave, the algorithm will always terminate at an extreme point of the feasible region (when the region is defined by linear constraints). In many cases the extreme points will not be globally optimum solutions. The situation is even further complicated for integer-nonlinear models. An extensive coverage of these features would take many pages, but the user should beware of the problem of assuring optimality for nonlinear models.

There are limitations on the functions that can appear in nonlinear terms. The functions should be defined, continuous and differentiable in and near the feasible region. This eliminates the use of IF, integer, and absolute value functions in the model. Ratios with denominators that might go to zero or square root terms that have negative arguments are similarly not allowed. These restrictions must be obeyed at every point that the Solver program might try to evaluate. Even if the initial solution is feasible, the Solver program might make small incursions outside the feasible region during the search process. If the program encounters a point for which a function cannot be evaluated it stops with an error message.

Menu


Updated 1/16/01
Operations Research Models and Methods

by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors