TOMLAB Solving Global Optimization Problems

This page is part of the TOMLAB Manual. See TOMLAB Manual.

Global Optimization deals with optimization problems that might have more than one local minimum. To find the global minimum out of a set of local minimum demands other types of methods than for the problem of finding local minimum. The TOMLAB routines for global optimization are based on using only function or constraint values, and no derivative information. Two different types are defined, Box-bounded global optimization glb and global mixed-integer nonlinear programming glc. For the second case, still the problem should be box-bounded.

All demonstration examples that are using the TOMLAB format are collected in the directory examples. Running the menu program tomMenu, it is possible to run all demonstration examples. It is also possible to run each example separately. The examples relevant to this section are glbDemo and glcDemo.

Box-Bounded Global Optimization Problems

Box-bounded global optimization problems are simple to define, only one function routine is needed, because the global optimization routines in TOMLAB does not utilize information about derivatives. To define the Shekel 5 test problem in a routine glb1_f, the following statements are needed

function f = glb1_f(x,  Prob)

A  = [4 4 4 4;  1 1 1 1;  8 8 8 8;  6 6 6 6;  3 7 3 7]';
f=0;    c = [.1 .2  .2  .4  .4]';

for i = 1:5
   z = x-A(:,i);
   f = f - 1/(z'*z + c(i) ); % Shekel 5
end

To solve the Shekel 5 test problem define the following statements, available as glb1Demo in glbDemo.

function glb1Demo

Name       = 'Shekel 5';
x_L	= [ 0  0  0  0]';     % Lower bounds in the  box 
x_U	= [10 10 10 10]'; % Upper bounds in the  box

% Generate the  problem  structure using  the  TOMLAB  format  (short call) 
Prob	= glcAssign('glb1_f', x_L,  x_U, Name);
Result  = tomRun('glbSolve', Prob,  1); % Solve  using  the  default of  200 iterations

If the user knows the optimal function value or some good approximation, it could be set as a target for the optimization, and the solver will stop if the target value is achieved within a relative tolerance. For the Shekel 5 problem, the optimal function value is known and could be set as target value with the following statements.

Prob.optParam.fGoal = -10.1532; %   The optimal value  set  as target
Prob.optParam.eps_f =  0.01;    %   Convergence tolerance one percent

Convergence will occur if the function value sampled is within one percent of the optimal function value.

Without additional knowledge about the problem, like the function value at the optimum, there is no convergence criteria to be used. The global optimization routines continues to sample points until the maximal number of function evaluations or the maximum number of iteration cycles are reached. In practice, it is therefore important to be able to do warm starts, starting once again without having to recompute the past history of iterations and function evaluations. Before doing a new warm start, the user can evaluate the results and determine if to continue or not. If the best function value has not changed for long it is a good chance that there are no better function value to be found.

In TOMLAB warm starts are automatically handled, the only thing the user needs to do is to set one flag, Prob.WarmStart, as true. The solver glbSolve defines a binary mat-file called glbSave.mat to store the information needed for a warm start. It is important to avoid running other problems with this solver when doing warm starts. The warm start information would then be overwritten. The example glb3Demo in glbDemo shows how to do warm starts. The number of iterations per call is set very low to be able to follow the process.

Name      = 'Shekel 5';
x_L       = [ 0   0   0   0]';
x_U       = [10  10  10  10]';

%   Generate the  problem  structure using  the  TOMLAB  format  (short call) 
Prob	= glcAssign('glb1_f', x_L,  x_U, Name); 
Prob.optParam.MaxIter = 5;  % Do only  five iterations per  call

Result 	= tomRun('glbSolve',Prob,2);  
pause(1) 
Prob.WarmStart 	= 1;  %   Set  the  flag for warm  start

for i = 1:6   %  Do   6 warm  starts
   Result  = tomRun('glbSolve',Prob,2);  pause(1)
end

The example glb4Demo in glbDemo illustrates how to send parameter values down to the function routine from the calling routine. Change the Shekel 5 test problem definition so that A and c are given as input to the function routine

function f = glb4_f(x,  Prob)

%  A   and c info are  sent  using  Prob structure 
f = 0;  A  = Prob.user.A; c = Prob.user.c;
for i = 1:5
   z = x-A(:,i);
   f = f - 1/(z'*z + c(i) ); 	%   Shekel 5
end

Then the following statements solve the ''Shekel 5 ''test problem.

Name	= 'Shekel 5';
x_L	= [0  0  0  0]';
x_U	= [10 10 10 10]';

%   Generate the  problem  structure using  the  TOMLAB  format  (short call) 
Prob	= glcAssign('glb4_f', x_L,  x_U, Name);

%   Add information to  be sent  to  glb4_f. Used in f(x) computation 
Prob.user.A = [4 4 4 4; 1 1 1 1; 8 8 8 8; 6 6 6 6; 3 7 3 7]'; 
Prob.user.c = [.1 .2 .2 .4 .4]';

Result  = tomRun('glbSolve',Prob,2);

Global Mixed-Integer Nonlinear Problems

To solve global mixed-integer nonlinear programming problems with the TOMLAB format, only two routines need to be defined, one routine that defines the function and one that defines the constraint vector. No derivative information is utilized by the TOMLAB solvers. To define the Floudas-Pardalos 3.3 test problem, one routine glc1_f

function f = fp3_3f(x,  Prob)
f = -25*(x(1)-2)^2-(x(2)-2)^2-(x(3)-1)^2-(x(4)-4)^2-(x(5)-1)^2-(x(6)-4)^2;

and one routine glc1_c

function c = fp3_3c(x,  Prob)
c = [(x(3)-3)^2+x(4); (x(5)-3)^2+x(6)]; % Two nonlinear constraints (QP)

is needed. Below is the example glc1Demo in glcDemo that shows how to solve this problem doing ten warm starts. The warm starts are automatically handled, the only thing the user needs to do is to set one flag as true, Prob.WarmStart. The solver glcSolve defines a binary mat-file called glcSave.mat to store the information needed for the warm start. It is important to avoid running other problems with glcSolve when doing warm starts. Otherwise the warm start information will be overwritten with the new problem. The original Floudas-Pardalos 3.3 test problem, has no upper bounds on x₁ and x₂ , but such bounds are implicit from the third linear constraint, x₁ + x₂ <=6. This constraint, together with the simple bounds x₁ >= 0 and x₂ >= 0 immediately leads to x₁ <= 6 and x₂ <= 6. Using these inequalities a finite box-bounded problem can be defined.

Name	= 'Floudas-Pardalos 3.3'; % This  example is number 16 in  glc_prob.m 

x_L	= [ 0  0 1 0 1 0]';   % Lower bounds on x
A       = [ 1 -3 0 0 0 0
           -1  1 0 0 0 0
            1  1 0 0 0 0];    % Linear equations
b_L	= [-inf -inf	2 ]'; % Upper bounds for linear equations
b_U	= [  2	  2	6 ]'; % Lower bounds for linear equations
x_U	= [6  6 5 6 5 10]';   % Upper bounds after x(1),x(2) values  inserted 
c_L	= [4  4]';	      % Lower bounds on two nonlinear constraints
c_U	= [];	              % Upper bounds are  infinity for nonlinear constraints 
x_opt   = [5  1 5 0 5 10]';   % Optimal x value
f_opt   = -310; 	      % Optimal f(x) value 
x_min = x_L;  x_max = x_U;    % Plotting bounds

% Set the rest of  the  arguments as empty
IntVars = []; VarWeight = [];

fIP = []; xIP = []; fLowBnd = []; x_0 = [];

%IntVars  = [1:5]; % Indices of  the  variables that should  be integer  valued

Prob = glcAssign('glc1_f', x_L,  x_U, Name, A,  b_L,  b_U, 'glc1_c', ... 
          c_L,  c_U, x_0,  IntVars, VarWeight,  ...
          fIP, xIP, fLowBnd, x_min,  x_max, f_opt, x_opt);

% Increase the default max number of function evaluations in glcSolve
Prob.optParam.MaxFunc = 500;

Result  = tomRun('glcSolve', Prob,  3); 

Prob.WarmStart  = 1;
% Do 10 restarts, call driver tomRun, PriLev  = 2 gives call to PrintResult 
for i=1:10
   Result  = tomRun('glcSolve',Prob,2);
end