topic Re: PROC OPTLSO: strategies to find global optimum in Mathematical Optimization, Discrete-Event Simulation, and OR

PROC OPTLSO: strategies to find global optimum

Forecaster — Tue, 20 Dec 2016 14:35:01 GMT

Firstly Kudos to SAS team for providing the wonderful procedure for general optimization (single and multiobjective) procedure Proc OPTLSO. I have worked in almost all software, this procedure seems to be the most powerful and general solver that I know of.

I have a hard nonlinear and nonsmooth opbjective function with linear and nonlinear constraints. The true global optimum for my problem is 26.35. However proc optlso returns 27.45. When I change the population size from 300 to 250, I get the true optimum of 26.35. When I change the population size to 200 I dont get the optimal solution. Here are my questions:

What is the best strategy to get global optimum "every" time when I run the program ? Is there a best practice ? Changing population size I'm assuming is not ideal.
How o set the seed to random number generator based on clock or something like it ? Will this improve chances of getting the global optimum ? Default seed is 1, I would like to change the seed every time a global solver is started.
Would increasing nglobal and nlocal help improve the chance of getting global optimum ?

proc optlso
	ABSFCONV= 1e-20
   	primalout = solution
   	variables = vardata
   	lincon    = lindata
	nlincon   = condata
	objective = objdata
	POPSIZE = 300
    logfreq = 50
	NGLOBAL = 20
	nlocal = 20
	;
run;

Re: PROC OPTLSO: strategies to find global optimum

joshgriffin — Wed, 21 Dec 2016 02:57:57 GMT

Though PROC OPTLSO does conduct a global search of the feasible region using a GA and LHS, it does not currently attempt to calculate a global optimality certificate such as one might find in a branch and bound algorithm. Typically the computation of such certificates either require much stronger assumptions on the objective and constraint functions and/or significantly longer running time. So unfortunately there is no way to guarantee the returned point is globally optimal. However, there are many things we can try to increase the probability that a global optimal point is found such as increasing popsize, nlocal, and/or nglobal, as you suggest. In general I have found that increasing popsize tends to be preferrable, but as you pointed out it is not guaranteed to improve the objective.

If you use seed=0, a random seed will be generated each time. One possibility is to run with (or without) seed=0 and perform a small grid search over a set of popsizes (something similar could be added to search on nglobal/nlocal). For example:

%let popsize=200;
%macro loopSolve(ntimes);
proc delete data=pall;
%do i=1 %to &ntimes.;
   %let popsize = %eval(&popsize. + 10*&i.); 
   proc optlso   
      /* your other options here */
      popsize=&popsize.
      seed=0   
      primalout=pout;  
      performance nthreads=2;
   run;
   
   data pout;
     set pout;
     _sol_=&i.;
   run;

   proc append base=pall data=pout;
   run; 
%end;
 
%mend;
 
%loopSolve(10);

proc transpose data=pall out=pallrow (drop=_label_ _name_);
    by _sol_;
    var _value_;
    id _id_;  
 run;  

 proc print data=pallrow;
 run;

I've attached a documentation example using the above code. Hopefully this help and please let us know if you have more questions.

Best,

--Josh

Re: PROC OPTLSO: strategies to find global optimum

Forecaster — Wed, 21 Dec 2016 13:29:17 GMT

@joshgriffin Thank you very much, setting seed=0 and running the program multiple times did the trick. I really appreciate your quick response.