The Nonlinear Programming Solver

Example 7.5 Solving NLP Problems with Several Local Minima

Some NLP problems contain many local minima. By default, the NLP solver converges to a single local minimum. However, the NLP solver is able to search the feasible region and try to locate other local minima. Once it completes the search it returns the point where the objective function achieves its minimum value. (This point might not be a local minimum; see the SOLTYPE= option for more details.) Consider the following example, taken from Hock and Schittkowski (1981):

In order to call the NLP solver to search the feasible region and locate different local minima, you can write the following SAS statements:

proc optmodel;
   var x{i in 1..5} >= -5 <= 5 init -2;
   
   min f=(x[1] - 1)^2 + (x[1] - x[2])^2 + (x[2] - x[3])^3 + 
         (x[3] - x[4])^4 + (x[4] - x[5])^4;
         
   con g1: x[1] + x[2]^2 + x[3]^3 =  2 + 3*sqrt(2);
   con g2: x[2] + x[4]   - x[3]^2 = -2 + 2*sqrt(2);
   con g3: x[1]*x[5] = 2;
   
   solve with nlp/ms msnumstarts=10;
   print x;
quit;

Note that the MS option is specified after the call to the NLP solver, together with the MSNUMSTARTS= option. The MS option informs the solver that you want multiple runs of the solver from different starting points. Setting the MSNUMSTARTS= option to 10 directs the solver to start from 10 different starting points. The actual starting points are determined internally by the solver.

The SAS log is shown in Output 7.5.1.

The first column in the log counts the number of starting points, and the second column records the best objective that has been found so far. Columns 3 to 5 record the final objective, infeasibility error, and optimality error of the local solver when started from the corresponding starting point. Finally the last column records the status of the local solver, namely whether it was able to converge to a local optimum from the corresponding starting point.

The summaries and solution are shown in Output 7.5.2.

Multistart also provides the option to see details of the local solver progress. This is achieved by specifying a value of 3 for the MSPRINTLEVEL= option. To see this, you can solve the previous example again by writing the following SAS statements:

proc optmodel;
   var x{i in 1..5} >= -5 <= 5 init -2;
   
   min f = (x[1] - 1)^2 + (x[1] - x[2])^2 + (x[2] - x[3])^3 + 
         (x[3] - x[4])^4 + (x[4] - x[5])^4;
         
   con g1: x[1] + x[2]^2 + x[3]^3 =  2 + 3*sqrt(2);
   con g2: x[2] + x[4]   - x[3]^2 = -2 + 2*sqrt(2);
   con g3: x[1]*x[5] = 2;
   
   solve with nlp/ms msnumstarts=3 msprintlevel=3 printfreq=50;
   print x.init x.msinit x;
quit;

These statements specify that you want to restart the local solver from three different points (MSNUMSTARTS=3), and you want to see the progress of the local solver from each starting point (MSPRINTLEVEL=3). You also want to set the frequency by which the local iterations are printed to 50 (PRINTFREQ=50). You have also decided to print the initial point specified in the VAR declaration (x.init), the starting point that led to the best local solution (x.msinit), and finally the best local solution (x) found by the NLP solver in multistart mode.

The SAS log is shown in Output 7.5.3.

The summaries and solution are shown in Output 7.5.4. Note that the best solution was found by starting the local solver from a starting point (x.msinit) that is different from the point specified in the VAR declaration (x.init).