GRG Solver Stopping Conditions

Aside from common stopping conditions such as reaching the Max Time or Max Iterations limits, the GRG Solver normally stops when the first of three tests is satisfied. For each of these tests, a different Solver Completion Message appears in the Solver Results dialog. It is important to understand exactly what each of these messages means.

1. Solver found a solution. All constraints and optimality conditions are satisfied.
2. Solver has converged to the current solution. All constraints are satisfied.
3. Solver cannot improve the current solution. All constraints are satisfied.

Bear in mind that all of these messages assume that the model is reasonably well-scaled, and/or that the Use Automatic Scaling box has been checked in the Solver Options dialog (it is unchecked by default). As discussed in the topic If you aren't getting the solution you expect, a poorly scaled model can "fool" all of the Solver's algorithmic methods.

Locally Versus Globally Optimal Solutions

When the first message ("Solver found a solution") appears, it means that the GRG Solver has found a locally optimal solution -- there is no other set of values for the decision variables close to the current values which yields a better value for the objective. Figuratively, this means that the Solver has found a "peak" (if maximizing) or "valley" (if minimizing) -- but there may be other taller peaks or deeper valleys far away from the current solution. Mathematically, this message means that the Karush - Kuhn - Tucker (KKT) conditions for local optimality have been satisfied (to within a certain tolerance, related to the Precision setting in the Solver Options dialog).

Although there is ongoing research in globally optimal nonlinear programming methods which we are monitoring, the best that current nonlinear methods can guarantee is to find a locally optimal solution. We recommend that you run the GRG Solver starting from several different sets of initial values for the decision variables -- ideally chosen based on your own knowledge of the problem. In this way you can increase the chances that you have found the best possible "optimal solution."

Frontline's enhanced solvers use an improved set of algorithmic tests for the KKT conditions, which are less sensitive to scaling and other sources of "noise" in the numerical values used by the Solver.

When Solver has Converged to the Current Solution

When the GRG Solver's second stopping condition is satisfied (before the KKT conditions are satisfied), the second message ("Solver converged to the current solution") appears. This means that the objective function value is changing very slowly for the last few iterations or trial solutions. More precisely, the GRG Solver stops if the absolute value of the relative change in the objective function is less than a convergence tolerance for the last N iterations. The values of convergence and N are fixed internally at present and are not changeable by the user. In recent releases of Microsoft Excel, convergence has been either 1.0E-4 or 1.0E-5, and N has been in the range 3 to 5. Although these settings are suitable for most problems, in some cases they can cause the GRG Solver to stop prematurely when this test is satisfied, instead of continuing for more iterations until the KKT conditions are satisfied.

A poorly scaled model is more likely to trigger this stopping condition, even if the Use Automatic Scaling box in the Solver Options dialog is checked. So it pays to design your model to be reasonably well scaled in the first place: The typical values of the objective and constraints should not differ from each other, or from the decision variable values, by more than three or four orders of magnitude.

If you are getting this message when you are seeking a locally optimal solution, you should first consider why it is that the objective function is changing so slowly. Perhaps you can add constraints or use different starting values for the variables, so that the Solver does not get "trapped" in a region of slow improvement. For those models where these measures are insufficient, however, we are considering making the convergence setting a user-settable option in future versions of the Solver. Send us an email message for an update on this topic.

When Solver Cannot Improve the Current Solution

The third stopping condition, which yields the message "Solver cannot improve the current solution," occurs only rarely. It means that the model is degenerate and the Solver is probably cycling. The issues involved are beyond the level of our Web discussion, as well as most of the Recommended Books. For a full explanation of this condition, you'll need to consult one of the advanced texts recommended in the topic Nonlinear Programming. One possibility worth checking is that some of your constraints are redundant, and should be removed. If this suggestion doesn't help, you will probably need specialized consulting assistance: Contact Compass Modeling Solutions and ask about their Member Consultants program.

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