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

${\begin{array}{cccccc}\min \limits _{x}&f(x)&&&&\\s/t&x_{L}&\leq &x&\leq &x_{U}\\&b_{L}&\leq &Ax&\leq &b_{U}\\&c_{L}&\leq &c(x)&\leq &c_{U}\\&~x_{j\in \mathbb {N} \ ~~\forall j\in \mathbb {I} },\\\end{array}}$

where $f(x)\in \mathbb {R}$; $x_{L},~x,~x_{U}\in \mathbb {R} ^{d}$; the $m_{1}$ linear constraints are defined by $A\in \mathbb {R} ^{m_{1}\times d}$, $b_{L},~b_{U}\in \mathbb {R} ^{m_{1}}$; and the $m_{2}$ nonlinear constraints are defined by $c_{L},~c(x),~c_{U}\in ~\mathbb {R} ^{m_{2}}$. The variables $x_{I}$ are restricted to be integers, where $\mathbb {I}$ is an index subset of $\{1,\ldots ,d\},$ possibly empty. It is assumed that the function $f(x)$ 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 $f(x)$ 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:

$\min _{x}\quad p(x)=f(x)+\sum _{j}w_{j}\max \left(0,c^{j}(x)-c_{U}^{j},c_{L}^{j}-c^{j}(x)\right),$

where weighting parameters w_j 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 rbfSolve are sent to the costly f(x)

- Special RBF algorithm parameters in Prob.CGO -
rbfType	Selects type of radial basis function Value Type 1 Thin Plate Spline 2 Cubic Spline (default) 3 Multiquadric 4 Inverse multiquadric 5 Gaussian 6 Linear.
infStep	If =1, add search step with target value -inf first 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. Value fStar target value 1 min_sn - ((N - (n - nInit))/N )2 * Deltan (Default) 2 min_sn - (N - (n - nInit))/N * Deltan. Strategy 1 and 2 depends on Deltan estimate (see DeltaRule). 3 -inf-step, min_sn-k *0.1*|min_sn| k = N,...,0. If infStep true, addition of -inf-step first in cycle.
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: Value Minimum picked 0 Use global minimum. 1 Use best interior local minima, if none use global minimum. 2 Use best interior local minima, if none use RBF interior minimum. 3 Use best minimum with lowest number of coefficients on bounds. 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. Value Signification 0 Normal termination. 1 Function value f(x) is less than fGoal. 2 Error in function value f (x), |f - fGoal| <= fTol, fGoal = 0. 3 Relative Error in function value f (x) is less than fTol, i.e. |f - fGoal|/|fGoal| <= fTol. 6 All sample points same as previous point for the last 11 iterations. 7 All feasible integers tried. 9 Max CPU Time reached.
CGO	Subfield WarmStartInfo saves warm start information, the same information as in cgoSave.mat, see Common output for all CGO solvers#WSInfo.

Output printing

PRINTING in MATLAB window in Iteration 0 after Experimental Design
If IterPrint >= 1 or PriLev > 1
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
--->>	Time stamp (date and exact time of this printout)
N	Cycle length Prob.CGO.N 0 to N-1 are global steps. Last step N in cycle is surface minimum
fStarRule	Cycle strategy
DeltaRule	See help Prob.CGO.DeltaRule
infStep	See help Prob.CGO.infStep
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)
Row 2
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
LipUFt	Maximum Lipschitz constant for initial set X, using transform F
objType	Function transformation used during run, one of 0 to 8.
Row 3
xMin	Best point in initial set X
Row 4
xOptS	User-given global optimum Prob.x_opt (if defined)
If PriLev > 2 and global optimum xOptS known and given in Prob.x_opt
Row 5
xOptS	The known global optimum
Row 6
SumXO	Sum of distances from global optimum xOptS to all sampled points X in experimental design
MeanXO	Mean of distances from global optimum xOptS to all sampled points X in experimental design
doO	Distance from global optimum xOptS to closest point of sampled points X in experimental design
If PriLev > 3
dXO	Minimal distance from global optimum to closest point of all sampled points X in experimental design
snOptf	Surface value at xOptS, sn_f(xOptS)
snOptg	Surface gradient at xOptS, sn_g(xOptS)
snOptE	Sum of negative eigenvalues of surface Hessian at xOptS, sum((eig(sn_H(xOptS)) < 0))

PRINTING in MATLAB window in Iteration 1,2, ...
if IterPrint >= 1 or PriLev > 1
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 pnts
--->>	Time stamp (date and exact time of this printout)
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
Row 2 Header line
# f(x) Task onB fnStar doX doM doS surfErr f-Reduc doO ln10(my)
Row 3 to m+2 with m new sample points xNew(1,1:m) obtained in last iteration
#	ith new point x = xNew(:,i)
f(x)	Costly f(x) value at x
Task	Which method that gave the new point Value Method 0,1,...,N-1 Global minimum in Target value search using target value fnStar N Global minimum of RBF surface -1 Global minimum of Target value -inf search (infStep) -2,-3, ... Additional AddGNMin minima in Target Value Search -2,-3, ... Additional AddSurfMin minima in RBF surface minimization 999 Rescue -7 Sample point inside local shrinked box -8 Random sample point inside the full box defined by [x_L,x_U] -9 Sample point using randomdesign
onB	Number of coordinates on bound for new point, onB(x)
fnStar	Target value used obtaining new point
doX	Minimal distance from x to sample set X, min||x-X||
doM	Distance from x to (xMin,fMin), best point found, min||x-xMin||
doS	Distance from x to minimum on surface, min||x-min_sn_y||
surfErr	Error between predicted and actual value of f(x), i.e. Costly f(x) - Surface value at x
f-Reduc	Function value reduction if fNew < fMin
doO	Distance from x to global optimum xOptS ||x-xOptS|| (if Prob.x_opt specified)
ln10(my)	Coefficient my in RBF interpolation
x:	x values for i:th point, scaled back i SCALE == 1
Row m+3 with values for current global surface minimum (min_sn_y, min_sn)
Sn	f(x) = min_sn, onB', doX, doM, doO values for min_sn_y, and x: are values for min_sn_y transformed back to original coordinates if SCALE == 1
NOTE: All distances measured are in SCALED space [0,1]d, if SCALE' == 1
Row m+4 Status row when updating RBF. Interpolation quality, illconditioning etc
LU	Estimate of condition number for current interpolation matrix
minDist	Minimal distance between points in sample set X, if small value ill-conditioning might occur
errsnFLast	Difference between f(x) transformed and RBF surface value at last point added
errsnFmax	Worst difference between f(x) transformed and RBF surface for x in set X, idx for worst point given.
errCVmin	Value and index for point with least cross validation error
errCVminR	Value and index for point with least cross validation error normalized with |f(x)|
CrossVal	Cross validation measure, deleting one interpolation point at the time
InterpErr	Maximal interpolation error using f(x) non-transformed. OK if < 10-6

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