CGO rbfSolve
This page is part of the CGO Manual. See CGO Manual. |
Purpose
Solve general constrained mixed-integer global black-box optimization problems with costly objective functions.
The optimization problem is of the following form
where ; ; the linear constraints are defined by , ; and the nonlinear constraints are defined by . The variables are restricted to be integers, where is an index subset of possibly empty. It is assumed that the function is continuous with respect to all variables, even if there is a demand that some variables only take integer values. Otherwise it would not make sense to do the surrogate modeling of used by all CGO solvers.
f (x) is assumed to be a costly function while c(x) is assumed to be cheaply computed. Any costly constraints can be treated by adding penalty terms to the objective function in the following way:
where weighting parameters wj have been added. The user then returns p(x) instead of f (x) to the CGO solver.
Calling Syntax
Result = rbfSolve(Prob,varargin) Result = tomRun('rbfSolve', Prob);
Usage
See CGO solver usage
Description of Inputs
Problem structure
The following fields are used in the problem description structure Prob:
Field | Description |
---|---|
Name | See Common input for all CGO solvers |
FUNCS.f | |
FUNCS.c | |
x_L | |
x_U | |
b_U | |
b_L | |
A | |
c_L | |
c_U | |
WarmStart | |
MaxCPU | |
user | |
PriLevOpt | |
f_Low | |
optParam | |
CGO | See the table below but also this table for input common to all CGO solvers |
GO | See common input for all CGO solvers |
MIP | See common input for all CGO solvers |
varargin | Additional parameters to arbfmip are sent to the costly f(x) |
- Special RBF algorithm parameters in Prob.CGO - | |||||||||||||||
rbfType | Selects type of radial basis function
| ||||||||||||||
infStep | If =1, add search step with target value -inffirst in cycle. Default 0. Always =1 for the case fStartRule == 3 | ||||||||||||||
fStarRule | Global-Local search strategy. N = cycle length. Define min_sn as the global minimum on surface.
| ||||||||||||||
DeltaRule | 1 = Skip large f(x) when computing f(x) interval Delta. 0 = Use all points. If objType > 0, default DeltaRule = 0, otherwise default is 1. | ||||||||||||||
AddSurfMin | Add up to AddSurfMin interior local minima on RBF surface as search points, based on estimated Lipschitz constants. AddSurfMin=0 implies no additional minimum added (Default AddSurfMin==1). Only possible if globalSolver = multiMin or glcDirect. Test for additional minimum in local step (modN == N) modN = -2,-3,-4,... are iteration steps with these search points. | ||||||||||||||
TargetMin | Which minimum of several to pick in target value problem:
Default is TargetMin = 3. | ||||||||||||||
eps_sn | Relative tolerance used to test if the minimum of surface, min_sn, is sufficiently lower than the best point (fMin) found. Default is eps_sn = 10-7. |
Description of Outputs
Result structure
The output structure Result contains results from the optimization.
The following fields are set:
Field | Description | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
x_k | See Common output for all CGO solvers for details. | ||||||||||||||||
f_k | |||||||||||||||||
Iter | |||||||||||||||||
FuncEv | |||||||||||||||||
ExitText | |||||||||||||||||
ExitFlag | Always 0, except 1 = Initial interpolation failed, normally because too huge f(x). | ||||||||||||||||
Inform | Information parameter.
| ||||||||||||||||
CGO | Subfield WarmStartInfo saves warm start information, the same information as in cgoSave.mat, see Common output for all CGO solvers#WSInfo. |
Output printing
IterPrint == 1 or PriLev > 0 | |
Row 1 | |
Iter | Number of iterations |
n | Number of trial x, n-Iter is number of points in initial design |
nFunc | Number of costly f(x) computed, nFunc <= n, n-nFunc = rejected points |
Cycle | Cycle steps global to local. infStep is marked -1, 0 to N-1 are global steps. Last step N in cycle is surface minimum |
R | If the letter R is printed, the current step is a RESCUE step, i.e. the new point is already sampled in a previous step, instead the surface minimum is used as a rescue |
fnStar | Target value fn_star |
fGoal | Goal value (if set) |
fMin | Best f(x) found so far. E.g. at 27/It 12 means n=27, Iter=12 fMinI means the best f(x) is infeasible fMinF means the best f(x) is feasible (also integer feasible) IT implies reduction in last step, It no reduction last step |
-- Additional information in iteration 1,2,... | |
fNew | f(xNew), the costly function value for point tried in current Iter |
RelErr | Relative distance to known or assumed global minimum (Prob.x_opt) |
-- Additional information in iteration 0, on next 3 lines | |
max(F) | Maximum of all f(x) in the initial set of points X |
med(X) | Median of all f(x) in the initial set of points X |
rng(F) | maxF-fMin, the range of f(x) values in the initial set X |
pDist | The size of the simply bounded region, ||x_U-x_L||2 |
LipU | Maximum Lipschitz constant for initial set X |
LipL | Minimum Lipschitz constant for initial set X |
objType | Function transformation used during run, one of 0 to 8. |
xMin | Best point in initial set X |
xOpt | User-given global optimum Prob.x_opt (if defined) |
In iteration 0 (if global optimum known and given in Prob.x_opt): | |
dXO | Minimal distance from global optimum to closest point of all sampled points X in experimental design |
SumXO | Sum of distances from global optimum to all sampled points X in experimental design |
doO | Distance from xBest with best f(x) in experimental design to global optimum |
Row 2 | |
xNew | Point tried in the current iteration, scaled back if SCALE==1 |
Row 3 (if PriLev > 2) (All distances are in SCALED space [0,1]d | |
snErr | surfErr=Costly f(x) value - Surface value at x (Actual-Predicted) |
fLoc | Optimal subproblem solution |
min_sn | Minimum on RBF surface, obtained at point min_sn_y |
[.] | Number of variables x active on bound at min_sn_y |
Distances from min_sn_y to: | |
doX | Minimal distance to closest point of all previous sampled points X |
doM | Distance to current best point found xMin, f(xMin) = fMinF |
doO | Distance to global optimum (if Prob.x_opt specified) |
[.] | Number of variables x active on bound at new point xNew |
Distances from xNew to: | |
doX | Minimal distance to closest point of all previous sampled points X |
doM | Distance to current best point found xMin, f(xMin) = fMinF |
doO | Distance to global optimum (if Prob.x_opt specified) |
doS | Distance from min_sn_y to new point xNew |
Row 4 (if PriLev > 3) | |
snNew-min_sn | |
snNew-fnStar | |
snNew-fNew | |
myNew | |
fRed | |
hn | |
hnErr | |
LipU | |
LipL |
Description
rbfSolve implements the Radial Basis Function (RBF) algorithm based on the work by Gutmann. The RBF method is enhanced to handle linear equality and inequality constraints, and nonlinear equality and inequality constraints, as well as mixed-integer problems.
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, snSolve.m, gnSolve.m, expDesign.m.
MEX-files Used
tomsol
See Also
ego.m
Warnings
Observe that when cancelling with CTRL+C during a run, some memory allocated by rbfSolve will not be deal- located. To deallocate, do:
>> clear cgolib