# 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*_{1} and *x*_{2} , but such bounds are implicit from the third linear constraint, *x*_{1} + *x*_{2} *<=*6. This constraint, together with the simple bounds *x*_{1} *>= *0 and *x*_{2} *>= *0 immediately leads to *x*_{1} *<= *6 and *x*_{2} *<= *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
```