The Nonlinear Programming Solver

Example 9.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 seed=1234 msmaxstarts=10;
   print x.init x.msinit x;
quit;

The PRINT statement prints the initial point (x.init) that was specified in the INIT option of the VAR declaration; the starting point (x.msinit) that led to the best local solution; and finally the best local solution (x) that was found by the NLP solver in multistart mode. The SAS log is shown in Output 9.5.1.

Output 9.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   607.035512  607.035512  2.81991E-7  5.88394E-9      7  Optimal    
          2   52.9025715  52.9025715  1.19566E-7  9.15988E-8      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 R 52.9025715  607.035846  5.40618E-7  5.40618E-7     11  Optimal    
          6   27.8719055  27.8719055  9.03316E-7   3.1145E-7      6  Optimal    
          7   27.8719055   27.871906  5.99633E-7  1.83684E-7      6  Optimal    
          8   27.8719055  64.8740121        5E-7  3.42541E-7      8  Optimal    
          9   0.02931086  0.02931086  9.77552E-7  9.77552E-7      8  Optimal    
         10   0.02931076  0.02931076  5.93194E-7  5.93194E-7     12  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.0293107602.            
NOTE: The solution found by local solver with objective = 0.0293107602 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 9.5.2. Note that the best local 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).

Output 9.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.0293107602
   
Number of Starts 10
Number of Sample Points 800
Number of Distinct Optima 9
Random Seed Used 1234
Optimality Error 5.9319399E-7
Infeasibility 5.9319399E-7
   
Presolve Time 0.00
Solution Time 3.49

[1] x.INIT x.MSINIT x
1 -2 2.87632 1.1166
2 -2 3.26949 1.2205
3 -2 -1.32653 1.5378
4 -2 -0.49448 1.9727
5 -2 1.27877 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 seed=1234 msmaxstarts=10;
   print x;
quit;

The SAS log is displayed in Output 9.5.3.

Output 9.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.9025015  52.9025015  9.03254E-7  9.03254E-7      5  Optimal    
          2   52.9025015  52.9025916  7.08702E-7  7.08702E-7      6  Optimal    
          3   52.9025015  52.9026134  4.08103E-7  4.08103E-7      8  Optimal    
          4   52.9025015  52.9025794  6.69221E-8  3.26907E-9      8  Optimal    
          5   0.02931083  0.02931083  2.53227E-7  3.54208E-9     10  Optimal    
          6   0.02931083  607.035871  8.43836E-7  8.43836E-7      8  Optimal    
          7   0.02931083  52.9025792  2.39856E-7  2.84012E-8      7  Optimal    
          8   0.02931083  607.035521  4.17297E-7  4.17297E-7      8  Optimal    
          9   0.02931083  64.8739968  2.99588E-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 9.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 9.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
Grid Mode Symmetric
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.00
Solution Time 1.99

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