The Nonlinear Programming Solver

An Optimization Problem with Many Local Minima

Consider the following optimization problem:

\[ \begin{array}{lll} \displaystyle \mathop \textrm{minimize}f(x) & =&  e^{\sin (50x)} + \sin (60e^ y) + \sin (70\sin (x)) + \sin (\sin (80y)) \\ & &  - \sin (10(x+y)) + (x^2+y^2)/4\\ \textrm{subject\  to}& &  -1 \le x \le 1 \\ & &  -1 \le y \le 1 \end{array}  \]

The objective function is highly nonlinear and contains many local minima. The NLP solver provides you with the option of searching the feasible region and identifying local minima of better quality. This is achieved by writing the following SAS program:

proc optmodel;
  var x >= -1 <= 1;
  var y >= -1 <= 1;
  min f = exp(sin(50*x)) + sin(60*exp(y)) + sin(70*sin(x)) + sin(sin(80*y))
          - sin(10*(x+y)) + (x^2+y^2)/4;
  solve with nlp / multistart seed=94245 msmaxstarts=30;
quit;

The MULTISTART option is specified, which directs the algorithm to start the local solver from many different starting points. The SAS log is shown in Figure 8.5.

Figure 8.5: Progress of the Algorithm as Shown in the Log

NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 2 variables (0 free, 0 fixed).                            
NOTE: The problem has 0 linear constraints (0 LE, 0 EQ, 0 GE, 0 range).         
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 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: 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 94245 is used.                                         
                    Best       Local  Optimality    Infeasi-  Local  Local      
      Start    Objective   Objective       Error      bility  Iters  Status     
          1   -1.8567821  -1.8567821        5E-7           0      3  Optimal    
          2   -2.9390086  -2.9390086        5E-7           0      3  Optimal    
          3   -2.9390086  -2.6561783        5E-7           0      3  Optimal    
          4   -3.3068686  -3.3068686        5E-7           0      3  Optimal    
          5   -3.3068686  -2.2355863        5E-7           0      3  Optimal    
          6   -3.3068686  -1.9014527  6.14439E-7  6.14439E-7      4  Optimal    
          7   -3.3068686  -0.4808983        5E-7           0      3  Optimal    
          8   -3.3068686  -1.5173191        5E-7           0      4  Optimal    
          9   -3.3068686   -2.076195        5E-7           0      4  Optimal    
         10   -3.3068686  -2.1930943        5E-7           0      5  Optimal    
         11   -3.3068686  -0.7857749        5E-7           0      5  Optimal    
         12   -3.3068686  -0.4033346        5E-7           0      3  Optimal    
         13   -3.3068686  -0.5926643        5E-7           0      4  Optimal    
         14   -3.3068686  -2.0402058        5E-7           0      4  Optimal    
         15   -3.3068686  -2.9525781        5E-7           0      4  Optimal    
         16 * -3.3068686  -1.3289057        5E-7           0      4  Optimal    
         17   -3.3068686  -1.5650191        5E-7           0      7  Optimal    
         18   -3.3068686   -1.404132        5E-7           0      3  Optimal    
         19   -3.3068686  -2.4632393        5E-7           0      3  Optimal    
         20   -3.3068686  -2.4541355        5E-7           0      4  Optimal    
         21   -3.3068686  -2.5171432        5E-7           0      5  Optimal    
         22   -3.3068686  -1.3559281  8.74345E-7  8.74345E-7      3  Optimal    
         23   -3.3068686   -1.031811        5E-7           0      4  Optimal    
         24   -3.3068686  -1.0823455        5E-7           0      5  Optimal    
         25   -3.3068686   -2.387082        5E-7           0      4  Optimal    
         26   -3.3068686  -0.6723829        5E-7           0      4  Optimal    
         27   -3.3068686  -1.2265443        5E-7           0      4  Optimal    
         28   -3.3068686  -0.6391886        5E-7           0      4  Optimal    
         29   -3.3068686  -0.9393803        5E-7           0      4  Optimal    
         30   -3.3068686  -0.5519164        5E-7           0      3  Optimal    
NOTE: The Multistart algorithm generated 320 sample points.                     
NOTE: 30 distinct local optima were found.                                      
NOTE: The best objective value found by local solver = -3.306868647.            
NOTE: The solution found by local solver with objective = -3.306868647 was      
      returned.                                                                 


The SAS log presents additional information when the MULTISTART option is enabled. The first column counts the number of restarts of the local solver. The second column records the best local optimum that has been found so far, and the third through sixth columns record the local optimum to which the solver has converged. The final column records the status of the local solver at every iteration.

The SAS output is shown in Figure 8.6.

Figure 8.6: Problem Summary and Solution Summary

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function f
Objective Type Nonlinear
   
Number of Variables 2
Bounded Above 0
Bounded Below 0
Bounded Below and Above 2
Free 0
Fixed 0
   
Number of Constraints 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 -3.306868647
   
Number of Starts 30
Number of Sample Points 320
Number of Distinct Optima 30
Random Seed Used 94245
Optimality Error 5E-7
Infeasibility 0
   
Presolve Time 0.00
Solution Time 3.57