TOMLAB OPTIMIZATION ENVIRONMENT: glbSolve

glbSolve

Purpose

For solving box-bounded global optimization problems.

Syntax

   Result = glbSolve(Prob,varargin);

Description

glbSolve implements a modified version of the algorithm DIRECT.

Problem

glbSolve solves box-bounced global optimization problems of the form:

    min   f(x)
     x
    s/t   x_L <= x <= x_U   

Usage

Let the name of the problem be "GLBF Test"
The function GLBF is best written as

     function f = GLBF(x, Prob)

Then any information, say b and C is easily sent to GLBF in the Prob structure by the call (assume bounds x_L and x_U are initialized)

     Prob   = glcAssign('GLBF',x_L,x_U,'GLBF Test');
     Prob.user.b = b; Prob.user.C=C;        % example of extra user data

     % Default values are now set for PriLevOpt, and structure optParam
     % To change a value, examples are shown on the two next lines
     Prob.optParam.MaxFunc = 500; % Change max number of function evaluations 
     Prob.optParam.MaxIter = 100; % Change the number of iterations to 100

Direct solver call:

     Result = glbSolve(Prob);
     PrintResult(Result);

Driver call, including printing with level 2:

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

The user function GLBF is written

     function f = GLBF(x, Prob) 
     b = Prob.user.b; C = Prob.user.C;
     f = "some function of x, b and C"

It is also possible to use the function format

     function f = GLBF(x) 

or sending the extra parameters as additional input

     Result = glbSolve(Prob,b,C);

     function f = GLBF(x,Prob,b,C) 

NOTE! If additional parameters are sent, Prob must be the second input parameter to GLBF

To make a restart, just set the restart flag, and call glbSolve once again:

     Prob.WarmStart = 1;
     Result = glbSolve(Prob);  % Assuming no extra parameters in the call
     PrintResult(Result);

IMPORTANT NOTE

The DIRECT algorithm only reaches the variable bounds in the limit. Therefore convergence for global optimum where components are on the bounds is slow.

One remedy is to reduce lower bounds with a tolerance, say 1E-4, and add a similar tolerance 1E-4 to the upper bounds that might be reached. Another possibility is to fix a variable on its bound by setting the lower and upper bounds equal.

Always try to reduce the dimension as much as possible when using the DIRECT algorithm, and try to shrink the box, defined by the lower and upper bounds, as much as possible.

Reference:
D. R. Jones, C. D. Perttunen and B. E. Stuckman,
Lipschitzian Optimization Without the Lipschitz Constant,
JOTA Vol. 79, No. 1, October 1993.

Input Parameters

 Prob        Structure, where the following variables are used:
   Name      Name of the problem. Used for security if doing warm start
   USER.f    The routine to compute the function, given as a string.
             A call to mFiles.m or glcAssign.m is setting this field. 
   x_L       Lower bounds for each element in x.
   x_U       Upper bounds for each element in x.
   PriLevOpt Print Level 
             0 = silent. 1 = some printing. 2 = print each iteration
   WarmStart If true, >0, glbSolve reads the output from the last run
             from the mat-file glbSave.mat, and continues from the last run.
 optParam    Structure in Prob, Prob.optParam 
             Defines optimization parameters. Fields used: 
  IterPrint  Print one line each iteration
  MaxIter    Maximal number of iterations, default 50.
  MaxFunc    Maximal number of function evaluations, default 10000 (roughly)
  EpsGlob    Global/local weight parameter, default 1E-4.
  fGoal      Goal for function value, if empty not used
  eps_f      Relative accuracy for function value, fTol == eps_f
             Stop if abs(f-fGoal) <= abs(fGoal) * fTol , if fGoal \=0
             Stop if abs(f-fGoal) <= fTol , if fGoal ==0

Output Parameters

 Result    Structure with results from optimization
  x_k      Matrix with optimal points as columns.
  f_k      The best function value found so far
  Iter     Number of iterations
  FuncEv   Number of function evaluations
  maxTri   Maximum size of any triangle
  ExitText Text string giving ExitFlag and Inform information

To make a warm start possible, glbSolve saves the following information in the file glbSave.mat:

   Name    Name of the problem. Used for security if doing warm start
   C       Matrix with all rectangle centerpoints, in [0,1]-space.
   D       Vector with distances from centerpoint to the vertices.
   L       Matrix with all rectangle side lengths in each dimension.
   F       Vector with function values.
   DSort   Row vector of all different distances, sorted.
   DMin    Row vector of minimum function value for each distance 

glbFast

glcCluster