The Nonlinear Programming Solver

Example 10.5 Solving NLP Problems That Have 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 can search the feasible region for other local minima. After 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):

\[ \begin{array}{ll} \displaystyle \mathop {\textrm{minimize}}&  f(x) = (x_1-1)^2 + (x_1-x_2)^2 + (x_2-x_3)^3 + (x_3-x_4)^4 + (x_4-x_5)^4 \\ \textrm{subject to}&  x_1 + x_2^2 + x_3^3 = 2+3\sqrt {2} \\ &  x_2+x_4-x_3^2 = -2+2\sqrt {2} \\ &  x_1 x_5 = 2 \\ &  -5 \le x_ i \le 5, i=1,\dots ,5 \end{array}  \]

The following statements call the NLP solver to search the feasible region for different local minima. The PERFORMANCE statement requests that the multistart algorithm use up to four threads. The SEED= option is specified for reproducibility, but it is not required in running the multistart algorithm.

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;

   performance nthreads=4;
   solve with nlp/multistart=(maxstarts=10) seed=1234;
   print x.msinit x;
quit;

The PRINT statement prints the starting point (x.msinit) that led to the best local solution and the best local solution (x) that the NLP solver found in multistart mode. The SAS log is shown in Output 10.5.1.

Output 10.5.1: Progress of the Algorithm as Shown in the Log

NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 5 variables (0 free, 0 fixed).                            
NOTE: The problem has 0 linear constraints (0 LE, 0 EQ, 0 GE, 0 range).         
NOTE: The problem has 3 nonlinear constraints (0 LE, 3 EQ, 0 GE, 0 range).      
NOTE: The OPTMODEL presolver removed 0 variables, 0 linear constraints, and 0   
      nonlinear constraints.                                                    
NOTE: Using analytic derivatives for objective.                                 
NOTE: Using analytic derivatives for nonlinear constraints.                     
NOTE: The NLP solver is called.                                                 
NOTE: The Interior Point algorithm is used.                                     
NOTE: The MULTISTART option is enabled.                                         
NOTE: The deterministic parallel mode is enabled.                               
NOTE: The Multistart algorithm is executing in single-machine mode.             
NOTE: The Multistart algorithm is using up to 4 threads.                        
NOTE: Random number seed 1234 is used.                                          
                    Best       Local  Optimality    Infeasi-  Local  Local      
      Start    Objective   Objective       Error      bility  Iters  Status     
          1   52.9025715  52.9025715  1.19566E-7  9.15988E-8      7  Optimal    
          2   52.9025715  607.035512  2.81991E-7  5.88394E-9      7  Optimal    
          3   52.9025715  607.035801  8.62585E-7  8.62585E-7      7  Optimal    
          4   52.9025715  52.9025734   4.3799E-7  6.32168E-8     13  Optimal    
          5 * 52.9025715  64.8739919   2.6454E-8  9.53134E-9      8  Optimal    
          6    27.871905   27.871905  7.23188E-7  1.45427E-7      5  Optimal    
          7    27.871905  27.8719062  5.37383E-7  1.23714E-7      7  Optimal    
          8    0.0293108   0.0293108  6.00111E-7  4.05694E-7      8  Optimal    
          9    0.0293108  0.02931083        5E-7  1.15697E-7     10  Optimal    
         10 r  0.0293108  0.02931083        5E-7  1.57633E-8      7  Optimal    
NOTE: The Multistart algorithm generated 800 sample points.                     
NOTE: 9 distinct local optima were found.                                       
NOTE: The best objective value found by local solver = 0.0293107959.            
NOTE: The solution found by local solver with objective = 0.0293107959 was      
      returned.                                                                 



The first column in the log indicates the index of the current starting point. An additional indicator (*, r, or R) can appear after the index to provide more information about the optimization run that started from the current point. For more information, see the section Iteration Log for Multistart. The second column records the best objective that has been found so far. Columns 3 to 6 report the objective value, optimality error, infeasibility, and number of iterations that the local solver returned when it was started from the current 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 current starting point.

The summaries and solution are shown in Output 10.5.2. Note that the best local solution was found by starting the local solver from a point at x.msinit.

Output 10.5.2: Summaries and the Optimal Solution

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Nonlinear
   
Number of Variables 5
Bounded Above 0
Bounded Below 0
Bounded Below and Above 5
Free 0
Fixed 0
   
Number of Constraints 3
Linear LE (<=) 0
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
Nonlinear LE (<=) 0
Nonlinear EQ (=) 3
Nonlinear GE (>=) 0
Nonlinear Range 0

Performance Information
Execution Mode Single-Machine
Number of Threads 4

Solution Summary
Solver Multistart NLP
Algorithm Interior Point
Objective Function f
Solution Status Optimal
Objective Value 0.0293107959
   
Number of Starts 10
Number of Sample Points 800
Number of Distinct Optima 9
Random Seed Used 1234
Optimality Error 6.0011139E-7
Infeasibility 4.0569362E-7
   
Presolve Time 0.00
Solution Time 3.52

[1] x.MSINIT x
1 -0.23856 1.1166
2 2.93912 1.2205
3 1.08486 1.5378
4 -1.11094 1.9726
5 1.80540 1.7911



Alternatively, the following SAS statements show how you can add the NODES= option in the PERFORMANCE statement to run this example in distributed mode.

Note: SAS High-Performance Optimization software must be installed before you can invoke the MULTISTART option in distributed mode.

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;

   performance nodes=4 nthreads=4;
   solve with nlp/multistart=(maxstarts=10) seed=1234;
   print x;
quit;

The SAS log is displayed in Output 10.5.3.

Output 10.5.3: Progress of the Algorithm as Shown in the Log

NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 5 variables (0 free, 0 fixed).                            
NOTE: The problem has 0 linear constraints (0 LE, 0 EQ, 0 GE, 0 range).         
NOTE: The problem has 3 nonlinear constraints (0 LE, 3 EQ, 0 GE, 0 range).      
NOTE: The OPTMODEL presolver removed 0 variables, 0 linear constraints, and 0   
      nonlinear constraints.                                                    
NOTE: Using analytic derivatives for objective.                                 
NOTE: Using analytic derivatives for nonlinear constraints.                     
NOTE: The NLP solver is called.                                                 
NOTE: The Interior Point algorithm is used.                                     
NOTE: The MULTISTART option is enabled.                                         
NOTE: The deterministic parallel mode is enabled.                               
NOTE: The Multistart algorithm is executing in the distributed computing        
      environment with 4 worker nodes.                                          
NOTE: The Multistart algorithm is using up to 4 threads.                        
NOTE: Random number seed 1234 is used.                                          
                    Best       Local  Optimality    Infeasi-  Local  Local      
      Start    Objective   Objective       Error      bility  Iters  Status     
          1   52.9025794  52.9025794  6.69221E-8  3.26907E-9      8  Optimal    
          2   52.9025015  52.9025015  9.03254E-7  9.03254E-7      5  Optimal    
          3   0.02931083  0.02931083  2.53227E-7  3.54208E-9     10  Optimal    
          4   0.02931083  607.035871  8.43836E-7  8.43836E-7      8  Optimal    
          5   0.02931083  52.9025916  7.08702E-7  7.08702E-7      6  Optimal    
          6   0.02931083  52.9025792  2.39856E-7  2.84012E-8      7  Optimal    
          7   0.02931083  52.9026134  4.08103E-7  4.08103E-7      8  Optimal    
          8   0.02931083  607.035521  4.17297E-7  4.17297E-7      8  Optimal    
          9   0.02931083  64.8739968  2.99593E-7  1.19421E-7      8  Optimal    
         10   0.02931083  52.9026071  3.70891E-7  3.70891E-7     11  Optimal    
NOTE: The Multistart algorithm generated 1600 sample points.                    
NOTE: 10 distinct local optima were found.                                      
NOTE: The best objective value found by local solver = 0.0293108314.            
NOTE: The solution found by local solver with objective = 0.0293108314 was      
      returned.                                                                 



Output 10.5.4 shows the summaries and solution. Note that the "Performance Information" table shows that four computing nodes with four threads on each node are used in distributed mode.

Output 10.5.4: Summaries and the Optimal Solution

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Nonlinear
   
Number of Variables 5
Bounded Above 0
Bounded Below 0
Bounded Below and Above 5
Free 0
Fixed 0
   
Number of Constraints 3
Linear LE (<=) 0
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
Nonlinear LE (<=) 0
Nonlinear EQ (=) 3
Nonlinear GE (>=) 0
Nonlinear Range 0

Performance Information
   
Host Node << your grid host >>
Execution Mode Distributed
Number of Compute Nodes 4
Number of Threads per Node 4

Solution Summary
Solver Multistart NLP
Algorithm Interior Point
Objective Function f
Solution Status Optimal
Objective Value 0.0293108314
   
Number of Starts 10
Number of Sample Points 1600
Number of Distinct Optima 10
Random Seed Used 1234
Optimality Error 2.5322746E-7
Infeasibility 3.5420806E-9
   
Presolve Time 0.01
Solution Time 1.93

[1] x
1 1.1167
2 1.2204
3 1.5378
4 1.9727
5 1.7911