A detailed description of the TOMLAB /CGO solvers is given below. Also
see the M-file help for
Solve general constrained mixed-integer global optimization
problems with costly objective functions.
.
) is assumed to
be cheaply computed.
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(f−fGoal) <= abs(fGoal) * fTol , if fGoal !=0. Stop if abs(f−fGoal) <= 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−(n−nInit))/N)2*Deltan (Default), 2: fStar = minsn − (N−(n−nInit))/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, minsn−k*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. |
|
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(f−fGoal) <= fTol, fGoal=0. |
|
|
3 = Relative Error in function value f(x) is less than fTol, i.e. abs(f−fGoal)/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: nInit ≥ d+1, 2d if center points. |
|
Fpen |
Vector with function values + additional penalty if infeasible. |
|
fMinIdx |
Index of the best point found. |
], augmented to handle linear and
non-linear constraints. The method is based on [
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.
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:
Solve box-bounded constrained mixed-integer global nonlinear
optimization problems.
.
)
are assumed to be cheaply computed. If some subset of the constraints,
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 MaxFunc ≤ nFunc (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 |f−fGoal| ≤ |fGoal| eps_f, if fGoal is nonzero. |
|
|
Stop if |f−fGoal| ≤ 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 xU − xL. 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. |
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(f−fGoal) <= fTol, fGoal=0. |
|
|
3 = Relative Error in function value f(x) is less than fTol, i.e. abs(f−fGoal)/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. |
|
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" [
].
Please note that Jones et al. has a slightly different problem
formulation. The TOMLAB version of
samples points to which a response surface is fitted. The
algorithm then balances between sampling new points and minimization on the surface.
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: