LINGO exploits the convex nature of linear models to find globally optimal solutions. However, we aren’t as fortunate with nonlinear models. With NLP models, LINGO’s default NLP solver uses a local search procedure. This can lead to LINGO stopping at locally optimal points, perhaps missing a global point lying elsewhere. You may refer to On Mathematical Modeling for more information on how and why this can happen.

A strategy that has proven successful in overcoming this problem is to restart the NLP solver several times from different initial points. It is not uncommon for a different starting point to lead to a different local solution point.  Thus, if we restart from enough unique points, saving the best local solution as we go, then we stand a much better chance of finding the true global solution.  We refer to this solution strategy as multistart.

The Multistart Solver box on the Global Solver tab:

contains two options, Attempts and Multistart Hurdle.

The Attempts option is used to set the number of times the multistart solver restarts the standard NLP solver in its attempt to find successively better local solutions.  Each new starting point is intelligently generated to maximize the chances of finding a new local point. The default option, Solver Decides, entails restarting 5 times on small NLPs and disabling multistart on larger models. Setting multistart to 1 causes the NLP solver to be invoked only once, effectively disabling multistart. Setting multistart to any value greater than 1 will cause the NLP solver to restart that number of times on all NLPs. In general, we have found that setting the number of multistarts to around 5 tends to be adequate for most models. Highly nonlinear models may require a larger setting.

The Multistart Hurdle option sets a goal for the multistart solver.  If the multistart solver finds a solution as good, or better, than the hurdle value, the solver will interrupt and return that solution.  This is useful on long-running models, where you may be happy with any solution better than, say, 100.

The following example illustrates the usefulness of multistart. Consider the simple, yet highly nonlinear, model:

MODEL:

  MIN = X * @COS( 3.1416 * X);

  @BND( 0, X, 6);

END

The graph of the objective function is as follows:

The objective function has three local minimal points over the feasible range. These points are summarized in the following table:

Clearly, the third local point is also the globally best point, and we would like the NLP solver to converge to this point. Below is the solution you will get from LINGO if the multistart option is disabled:

  Local optimal solution found at step:             11

  Objective value:                           -1.046719

          Variable           Value        Reduced Cost

                 X        1.090405           0.1181082E-07

               Row    Slack or Surplus      Dual Price

                 1       -1.046719           -1.000000

Unfortunately, as you can see, we converged to the least preferable of the local minimums. However, after setting the number of multistarts to five and re-solving, we do obtain the global solution:

  Local optimal solution found at step:             39

  Objective value:                           -5.010083

          Variable           Value        Reduced Cost

                 X        5.020143          -0.7076917E-08

               Row    Slack or Surplus      Dual Price

                 1       -5.010083           -1.000000