Standard Excel Solver - Limitations of Nonlinear Optimization
Nonlinear problems are intrinsically more difficult to solve than linear problems, and there are fewer guarantees about what the Solver (or any optimization method) can do. The Solver uses the GRG (Generalized Reduced Gradient) algorithm -- one of the most robust nonlinear programming methods -- to solve problems whenever the Assume Linear Model box in the Solver Options dialog is unchecked. (When the box is checked, the Solver uses the Simplex method for linear programming problems.)
- Linear and Nonlinear Problems
- Feasible Regions, Peaks and Valleys
- Slow Progress and Stopping Conditions
Bear in mind that -- since the Assume Linear Model box is unchecked by default -- the Solver will try to solve your model using the GRG method, even if it is actually a linear model that could be solved by the (faster and more reliable) Simplex method. The GRG method, while it is always slower, will usually find the optimal solution to a linear problem -- but occasionally you will receive a Solver Completion Message indicating some uncertainty about the status of the solution -- especially if the model is poorly scaled, as discussed above. So you should make sure that the Assume Linear Model box is checked for linear problems.
A nonlinear problem may have more than one feasible region, or set of similar values for the decision variables, where all of the constraints are satisfied. Within each feasible region, there may be more than one "peak" (if maximizing) or "valley" (if minimizing) -- and there is no general way to determine which peak is tallest, or which valley is deepest. There may also be false peaks or valleys known as "saddle points." Because of these possibilities, nonlinear optimization methods can make few guarantees about finding the "true" optimal solution.
When dealing with a nonlinear problem, it is a good idea to run the Solver starting from several different sets of initial values for the decision variables. Since the Solver follows a path from the starting values (guided by the direction and curvature of the objective function and constraints) to the final solution values, it will normally stop at a peak or valley closest to the starting values you supply. By starting from more than one point -- ideally chosen based on your own knowledge of the problem -- you can increase the chances that you have found the best possible "optimal solution."
Frontline's Premium Solver Platform can automate the process of starting the Solver from different initial values, using so-called multistart methods for global optimization. You may also wish to consult our Solver Tutorial and the Premium Solver Platform User Guide for further information about "locally optimal" and "globally optimal" solutions.
At best, the GRG Solver -- like virtually all nonlinear optimization algorithms -- will find a locally optimal solution to a reasonably well-scaled model. At times, however, the Solver will stop before finding a locally optimal solution, when it is making very slow progress (the objective function is changing very little from one trial solution to another) or for other reasons. For a more information, click on GRG Nonlinear Solver Stopping Conditions.