« Previous « Start » Next »
7 Solving Global Optimization Problems
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 (TQ) 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 .
7.1 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);
7.2 Global Mixed-Integer Nonlinear
Problems
To solve global mixed-integer nonlinear programming problems
with the TQ 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
« Previous « Start » Next »
TOMLAB
