# TOMLAB  
# REGISTER (TOMLAB)
# LOGIN  
# myTOMLAB
TOMLAB LOGO

« Previous « Start » Next »

5  TOMLAB /CGO Solver Reference

A detailed description of the TOMLAB /CGO solvers is given below. Also see the M-file help for rbfSolve.m and ego.m.

5.1  rbfSolve

Purpose
Solve general constrained mixed-integer global optimization problems with costly objective functions.

rbfSolve solves problems of the form
 
min
x
f(x)        
s/t xL x xU
  bL Ax bU
  cL c(x) cU
where x,xL,xU∈ Rn, c(x),cL,cU∈ Rm1, A∈ Rm2× n and bL,bU∈ Rm2.

The variables x ∈ I, the index subset of 1,...,n are restricted to be integers.

f(x) is assumed to be a costly function while c(x) is assumed to be cheaply computed.

If some subset cI(x) of the constraints is very costly, create F(x) as a penalty function as F(x) = f(x) + βT cI(x), β positive penalties.

Calling Syntax
Result = rbfSolve(Prob,varargin)
Result = tomRun('rbfSolve', Prob);

Description of Inputs

Prob Problem description structure. The following fields are used:
 
  A Linear constraint matrix.
  b_U Upper bounds for the linear constraints.
  b_L Lower bounds for the linear constraints.
 
  c_U Upper bounds for the nonlinear constraints.
  c_L Lower bounds for the nonlinear constraints.
 
  x_L Lower bounds on the variables. Must be finite.
  x_U Upper bounds on the variables. Must be finite.
 
  FUNCS.f Name of function to compute the objective function.
  FUNCS.c Name of function to compute the nonlinear constraint vector.
 
  Name Name of the problem. Used for security when doing warm starts.
  WarmStart Set true (non-zero) to load data from previous run from cgoSave.mat.
  MaxCPU Maximal CPU Time (in seconds) to be used.
 
  PriLevOpt Print Level. 0 = silent. 1 = Summary 2 = Printing each iteration. 3 = Info about local / global solution. 4 = Progress in x.
 
  f_Low Lower bound on the optimal function value. If defined, used to restrict the target values into interval [f_Low,min(surface)].
 
  optParam Structure with optimization parameters. The following fields are used:
 
  IterPrint Print one information line each iteration, and the new x tried. Default IterPrint = 1. fMinI means the best f(x) is infeasible. fMinF means the best f(x) is feasible (also integer feasible).
  MaxFunc Maximal number of costly function evaluations, default 300. If WarmStart == 1 and MaxFunc <= nFunc (Number of f(x) used) then MaxFunc = MaxFunc + nFunc.
  MaxIter Maximal number of iterations used in the local optimization on the response surface in each step. Default 1000, except for pure IP problems, then max(GO.MaxFunc, MaxIter);.
  fGoal Goal for function value, not used if inf or empty.
  eps_f Relative accuracy for function value, fTol == epsf. Stop if abs(ffGoal) <= abs(fGoal) * fTol , if fGoal !=0. Stop if abs(ffGoal) <= fTol , if fGoal ==0. See the output field maxTri.
  bTol Linear constraint tolerance.
  cTol Nonlinear constraint tolerance.
 
  CGO Structure (Prob.CGO) with parameters concerning global optimization options.
    The following fields are used:
  idea Type of search strategy on the response surface.
    1 - cycle of 6 points in target value fnStar
    2 - cycle of 4 points in alpha (default).
 
  rbfType Type of radial basis function: 1 - thin plate spline; 2 - Cubic Spline (default).
 
  SCALE 0 - original search space.
    1 - transform search space to unit cube (default).
 
  PLOT 0 - no plotting (default).
    1 - Plot sampled points.
 
  REPLACE 0 - No replacement (default for constrained problems).
    1 - Large function values are replaced by the median (uc default).
 
  LOCAL 0 - No local searches after global search. If RBF surface is inaccurate, might be an advantage.
    1 - Local search from best points after global search. If equal best function values, up to 20 local searches are done.
 
  globalSolver Name of solver used for global optimization on the RBF surface.
  localSolver Name of solver user for local optimization on the RBF surface.
 
  MaxCycle Max number of cycles without progress before stopping, default 10.
 
  Percent Strategy to get initial sampled values.
    Percent ≥ 100: User gives initial points x as a matrix in CGO.X. Each column is one sampled point. The user must supply at least d+1 points: If d =length(Prob.x), then size(X,1) = d, size(X,2) ≥ d+1) must hold. CGO.F should be defined as empty, or contain a vector of corresponding f(x) values. Any CGO.F value set as NaN will be computed by rbfSolve.
 
    0 < Percent < 100: Random strategy, the Percent value gives the percentage size of an ellipsoid around the so far sampled points that the new points are not allowed in. Range 1%-50%. Recommended values 10% - 20%.
 
    Percent = 0: Initial points is the corner points of the box. Generates too many points if the dimension is high.
 
    Percent < 0: Latin hypercube space-filling design. The value of abs(Percent) should in principle be the dimension. The call made is X = daceInit(round(abs(Percent)),Prob.x_L,Prob.x_U); Let k = abs(Percent), then the number of points are:
    k : 1 2 3 4 5 6 >6
    Points : 21 21 33 41 51 65 65
 
    Percent < −1000: Latin hypercube space-filling design, only keep the points that fulfill the linear and nonlinear constraints. The algorithm will try up to M = abs(Percent−1000) points, stopping when it has got length(xL)+1 feasible points.
 
    Percent = −999: Gutmann strategy: Initial points are x_L and d points x_L + (xU(i) − xL(i))*ei, i=1,...,d.
 
  X If Percent >= 100, a matrix of initial x values. One column for every x value. size(X,2) >= dim(x)+1 needed
 
  F If Percent >= 100, a vector of initial f(x) values. If any element is set to NaN, rbfSolve will compute f(x)
 
  CX If Percent >= 100, optionally a matrix of nonlinear constraint c(x) values. If nonempty, then size(CX,2) == size(X,2). If any element in a column i is set as NaN, the vector c(x) = CX(:,i) will be recomputed
 
  RandState If >=0, rand('state',RandState) is set to initialize the pseudo-random generator. If < 0, rand('state',100*clock) is set to give a new set of random values each run. Default RandState = 0
 
  N Cycle length in idea 1 (default N=5 for fStarRule 1 and 2, default N=1 for fStarRule 3) or idea 2 (always N=3).
 
  infStep If =1, add search step with target value -inf first in cycle. Default 0.
 
  AddMP If = 1, add the midpoint as extra point in the corner strategy or the Gutmann strategy. Default 0.
 
  fStarRule Global-Local search strategy in idea 1. N = cycle length. Define min_sn as local minimum on surface. fStar Target value. 1: fStar = minsn − ((N−(nnInit))/N)2*Deltan (Default), 2: fStar = minsn − (N−(nnInit))/N*Deltan. Strategy 1 and 2 depends on Delta_n estimate (see DeltaRule). If infStep true, addition of -inf-step first in cycle. 3: fStar = -inf-step, minsnk*0.1*|minsn| k=N,...,0. Strategy names in Gutmanns thesis: III, II, I.
 
  DeltaRule 1 = Skip large f(x) when computing f(x) interval Delta. 0 = Use all points. Default 1.
 
  GO Structure Prob.GO (Default values are set for all fields).
    The following fields are used:
 
  MaxFunc Maximal number of function evaluations in each global search.
 
  MaxIter Maximal number of iterations in each global search.
 
  maxFunc1 glcCluster parameter, max function evaluations 1st call. Only used if globalSolver is glcCluster, see help globalSolver.
 
  maxFunc2 glcCluster parameter, max function evaluations 2nd call. Only used if globalSolver is glcCluster, see help globalSolver.
 
  localSolver The local solver used by glcCluster.
 
  DIRECT DIRECT method used in glcCluster, glcSolve or glcFast(default).
 
  MIP Structure in Prob, Prob.MIP.
    Defines integer optimization parameters. Fields used:
 
  IntVars If empty, all variables are assumed non-integer. If length(IntVars) >1 ==> length(IntVars) == length(c) should hold. Then IntVars(i) ==1 ==> x(i) integer. IntVars(i) ==0 ==> x(i) real. If length(IntVars) < n, IntVars is assumed to be a set of indices.
    If MIP problems are solved then the only subsolvers working are glcCluster, and OQNLP (for both the local and global subproblem). E.g. Prob.CGO.globalSolver = 'oqnlp'; Prob.CGO.localSolver = 'oqnlp'; will use the OQNLP solver, a license for TOMLAB /OQNLP is needed.
    For pure IP problems, only glcSolve and glcFast (default) may be used. Set Prob.CGO.globalSolver = 'glcSolve'; to use glcSolve, otherwise glcFast is used.
 
varargin Other parameters directly sent to low level routines.
 

Description of Outputs
Result Structure with result from optimization. The following fields are set:
 
  x_k Matrix with the best points as columns.
  f_k The best function value found so far.
 
  Iter Number of iterations.
  FuncEv Number of function evaluations.
  ExitText Text string with information about the run.
  ExitFlag Always 0.
  Inform Information parameter.
    0 = Normal termination.
    1 = Function value f(x) is less than fGoal.
    2 = Error in function value f(x), abs(ffGoal) <= fTol, fGoal=0.
    3 = Relative Error in function value f(x) is less than fTol, i.e. abs(ffGoal)/abs(fGoal) <= fTol.
    4 = Failure in global sub solvers, same point sampled over and over. Try lower cTol and or bTol, or other subsolver.
    7 = All feasible integers tried.
    8 = No progress for MaxCycle*(N+1)+1 function evaluations (>MaxCycle cycles, input CGO.MaxCycle).
    9 = Max CPU Time reached.
 
  cgoSave.mat To make warm starts possible, rbfSolve saves the following
    information in the file cgoSave.mat:
  Name Name of the problem. Used for safety check so that the warm start is not made with data from a different problem.
  O Matrix with sampled points (in original space).
  X Matrix with sampled points (in unit space, if Prob.CGO.SCALE==1).
  F Vector with function values.
  F_m Vector with function values (replaced).
  nInit Number of initial points: nInitd+1,  2d if center points.
  Fpen Vector with function values + additional penalty if infeasible.
  fMinIdx Index of the best point found.

Description
rbfSolve implements the Radial Basis Function (RBF) algorithm presented in [2], augmented to handle linear and non-linear constraints. The method is based on [8].

A response surface based on radial basis functions is fitted to a collection of sampled points. The algorithm then balances between minimizing the fitted function and adding new points to the set.

M-files Used
daceInit.m, iniSolve.m, endSolve.m, conAssign.m, glcAssign.m

MEX-files Used
tomsol

See Also
ego.m

Warnings
If rbfSolve is called but is interrupted by the user, or fails, for example due to incorrect input data, it is necessary to issue one of the following commands:
  • clear mex
  • clear all
  • tomsol(25)
The reason for this is that the MEX-file solver tomsol is used by rbfSolve for time-critical tasks and allocates memory which must be deallocated.



5.2  ego

Purpose
Solve box-bounded constrained mixed-integer global nonlinear optimization problems.

ego solves problems of the form:

 
min
x
f(x)  
subject to xL x xU, xL and xU finite
  bL A x bU
  cL c(x) cU
where x,xL,xU∈ Rn, c(x),cL,cU∈ Rm1, A∈ Rm2× n and bL,bU∈ Rm2.

The variables x ∈ I, the index subset of 1,...,n are restricted to be integers.

f(x) is assumed to be a costly function while the constraints c(x) are assumed to be cheaply computed. If some subset of the constraints, cI(x), is very costly, create f(x) as a penalty function:
f(x) = f(x) + βT cI(x),    β positive penalties


Calling Syntax
Result=ego(Prob,varargin)
Result = tomRun('ego', Prob);

Description of Inputs
Prob Problem description structure. The following fields are used:
 
  Name Problem name. Used for safety check when doing warm starts.
  A Linear constraint matrix.
  b_L Lower bounds for the linear constraints.
  b_U Upper bounds for the linear constraints.
 
  c_L Lower bounds for the nonlinear constraints.
  c_U Upper bounds for the nonlinear constraints.
 
  x_L Lower bounds for each element in x.
  x_U Upper bounds for each element in x.
 
  FUNCS.f String giving the name of the function to compute the objective function.
  FUNCS.c String giving the name of the function to compute the nonlinear constraint vector.
 
  WarmStart If true (>0), ego reads the output from the last run from the mat-file cgoSave.mat and resumes optimization from where the last run ended. ego and rbfSolve (Section 5.1) uses the same mat-file and can read the output of one another.
  MaxCPU Maximal CPU Time (in seconds) to be used.
  PriLevOpt Print level. 0 = silent. 1 = Summary, 2 = Printing each iteration, 3 = Info about local / global solution, 4 = Progress in x.
  user User field used to send information to low-level functions.
 
  optParam Structure with fields for optimization parameters. Used fields are:
 
  IterPrint Print one line of information each iteration, including the new x tried. Default 1.
  MaxIter Maximum number of iterations used in the global optimization on the response surface in each step. Default 10000.
  MaxFunc Maximum number of function evaluations in ego. Default 200.
    If doing a warm start and MaxFuncnFunc (present # of f(x) calls) then MaxFunc = MaxFunc+nFunc.
  fGoal Goal for function value, not used if empty.
  eps_f Relative accuracy for function value.
    Stop if |ffGoal| ≤ |fGoal| eps_f, if fGoal is nonzero.
    Stop if |ffGoal| ≤ eps_f, if fGoal is zero.
  bTol Linear constraint tolerance.
  cTol Nonlinear constraint tolerance.
 
  CGO Structure (Prob.CGO) with parameters concerning global optimization options.
    The following fields are used:
 
  SCALE 0 - original search space.
    1 - transform search space to unit cube (default).
  PLOT 0 - no plotting (default).
    1 - Plot sampled points.
  REPLACE 0 - No replacement.
    1 - Large function values are replaced by the median (default).
  LOCAL 0 - No local searches after global search. If EGO surface is inaccurate, might be an advantage.
    1 - Local search from best points after global search. If equal best function values, up to 20 local searches are done.
  TolExpI Convergence tolerance for expected improvement, default 1E-6.
  pEst 1 - Estimate d-vector, p parameters (default), 0 - fix p=2.
  TRANSFORM Function value transformation.
    0 - No transformation made.
    1 - log(y) transformation made.
    2 - -log(-y) transformation made.
    3 - -1/y transformation made.
    Default EGO is computing the best possible transformation from the initial set of data. Note! No check is made on illegal y if user gives TRANSFORM.
  globalSolver Name of solver used for global optimization on the response surface. If the globalSolver is glcCluster, the fields Prob.GO.maxFunc1 and Prob.GO.maxFunc2 is used. See the help for maxFunc1 and maxFunc2 in glcCluster.
  localSolver Name of solver user for local optimization on the response surface.
 
  Percent Strategy to get initial sampled values. Percent ≥ 100: User gives initial points x as a matrix in CGO.X. Each column is one sampled point. If d = length(Prob.xL), then size(X,1) = d, size(X,2) >= d+1 CGO.F should be defined as empty, or contain a vector of corresponding f(x) values. Any CGO.F value set as NaN will be computed by ego.
    Percent > 0 (less then 100): Random strategy, the Percent value gives the percentage size of an ellipsoid around the so far sampled points that the new points are not allowed in. Range 1%-50%. Recommended values 10% - 20%.
 
    Percent = 0: Initial points are the corner points of the box xUxL. Generates too many points if the dimension is high.
 
    Percent < 0: Latin hypercube space-filling design. The value of abs(Percent) should in principle be the dimension. The call made is X = daceInit(round(abs(Percent)),Prob.x_L,Prob.x_U); Let k = abs(Percent), then the number of points are:
    k : 1 2 3 4 5 6 >6
    Points : 21 21 33 41 51 65 65
 
    Percent < −1000: Latin hypercube space-filling design, only keep the points that fulfill the linear and nonlinear constraints. The algorithm will try up to M = abs(Percent−1000) points, stopping when it has got length(xL)+1 feasible points.
 
    Percent = −999: Gutmann strategy: Initial points are x_L and d points x_L + (xU(i) − xL(i))*ei, i=1,...,d.
 
  X If Percent >= 100, a matrix of initial x values. One column for every x value. size(X,2) >= dim(x)+1 needed
 
  F If Percent >= 100, a vector of initial f(x) values. If any element is set to NaN, rbfSolve will compute f(x)
 
  CX If Percent >= 100, optionally a matrix of nonlinear constraint c(x) values. If nonempty, then size(CX,2) == size(X,2). If any element in a column i is set as NaN, the vector c(x) = CX(:,i) will be recomputed
 
  RandState If >=0, rand('state',RandState) is set to initialize the pseudo-random generator. If < 0, rand('state',100*clock) is set to give a new set of random values each run. Default RandState = 0
 
  AddMP If = 1, add the midpoint as extra point in the corner strategy or the Gutmann strategy. Default 0.
 
  GO Structure Prob.GO (Default values are set for all fields).
    The following fields are used:
 
  MaxFunc Maximal number of function evaluations in each global search.
 
  MaxIter Maximal number of iterations in each global search.
 
  maxFunc1 glcCluster parameter, max function evaluations 1st call. Only used if globalSolver is glcCluster, see help globalSolver.
 
  maxFunc2 glcCluster parameter, max function evaluations 2nd call. Only used if globalSolver is glcCluster, see help globalSolver.
 
  localSolver The local solver used by glcCluster.
 
  DIRECT DIRECT method used in glcCluster, glcSolve or glcFast(default).
 
  MIP.IntVars Defines integer optimization parameters. If empty, all variables are assumed non-integer. If length(IntVars) >1 ==> length(IntVars) == length(c) should hold. Then IntVars(i) ==1 ==> x(i) integer. IntVars(i) ==0 ==> x(i) real. If length(IntVars) < n, IntVars is assumed to be a set of indices.
 
    If MIP problems are solved then the only subsolvers working are glcCluster, and OQNLP (for both the local and global subproblem) e.g. Prob.CGO.globalSolver = 'oqnlp'; and Prob.CGO.localSolver = 'oqnlp'; will use the OQNLP solver, a license for TOMLAB /OQNLP is needed.
 
    For pure IP problems, only glcSolve and glcFast (default) may be used. Set Prob.CGO.globalSolver = 'glcSolve'; to use glcSolve, otherwise glcFast is used.
 
varargin Other arguments sent directly to low level functions.

Description of Outputs
Result Structure with result from optimization.
 
  x_k Matrix containing the best points as columns.
  f_k Vector with function values corresponding to x_k.
 
  Iter Number of iterations used.
  FuncEv Number of function evaluations.
  ExitText Text string giving information about the run.
  ExitFlag Always 0.
  Inform Information parameter.
    0 = Normal termination.
    1 = Function value f(x) is less than fGoal.
    2 = Error in function value f(x), abs(ffGoal) <= fTol, fGoal=0.
    3 = Relative Error in function value f(x) is less than fTol, i.e. abs(ffGoal)/abs(fGoal) <= fTol.
    7 = All feasible integers tried.
    9 = Max CPU Time reached.
 
  cgoSave.mat MATLAB mat-file saved to current directory, used for warmstarts. This file can be read by rbfSolve as well. The file contains the following variables:
 
  Name Problem name. Checked against the Prob.Name field if doing a warmstart.
  O Matrix with sampled points (in original space).
  X Matrix with sampled points (in unit space if SCALE==1)
  F Vector with function values.
  F_m Vector with function values (replaced).
  nInit Number of initial points.
  Fpen Vector with function values + additional penalty if infeasible.
  fMinIdx Index of the best point found.
 

Description
ego implements the algorithm EGO by D. R. Jones, Matthias Schonlau and William J. Welch presented in the paper "Efficient Global Optimization of Expensive Black-Box Functions" [4].

Please note that Jones et al. has a slightly different problem formulation. The TOMLAB version of ego treats linear and nonlinear constraints separately.

ego samples points to which a response surface is fitted. The algorithm then balances between sampling new points and minimization on the surface.

ego and rbfSolve use the same format for saving warm start data. This means that it is possible to try one solver for a certain number of iterations/function evaluations and then do a warm start with the other. Example:
>> Prob           = probInit('glc_prob',1);  % Set up problem structure
>> Result_ego     = tomRun('ego',Prob);      % Solve for a while with ego
>> Prob.WarmStart = 1;                       % Indicate a warm start
>> Result_rbf     = tomRun('rbfSolve',Prob); % Warm start with rbfSolve
M-files Used
iniSolve.m, endSolve.m, conAssign.m, glcAssign.m

See Also
rbfSolve



« Previous « Start » Next »