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 x1 and x2 , but such bounds are implicit from the third linear constraint, x1 + x2 <=6. This constraint, together with the simple bounds x1 >= 0 and x2 >= 0 immediately leads to x1 <= 6 and x2 <= 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