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);

Description of Inputs

Problem description structure. The following fields are used:

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 common input for all CGO solvers and the table below
GO	See common input for all CGO solvers
MIP
varargin	Additional parameters to arbfmip are sent to the costly f(x)

- Special RBF algorithm parameters in Prob.CGO -
rbfType	Type of radial basis function: 1 - thin plate spline; 2 - Cubic Spline (default); 3 - Multiquadric; 4 - Inverse multiquadric; 5 - Gaussian; 6 - Linear.
idea	Type of search strategy on the response surface. idea = 1 - cycle of N+1 points in target value fnStar. if fStarRule =3, then N=1 default, otherwise N=4 default. By default idea =1, fStarRule =1, i.e. N =4. To change N, see below. idea = 2 - cycle of 4 points (N+1, N=3 always) in alpha. alpha is a bound on an algorithmic constraint that implicitly sets a target value fStar.
N	Cycle length in idea 1 (default N=1 for fStarRule 3, otherwise default N=4) or idea 2 (always N=3).
infStep	If =1, add search step with target value -8 first in cycle. Default 0. Always =1 for the case idea =1, fStarRule =3.
fStarRule	Global-Local search strategy in idea 1, where N is the cycle length. Define minsn as the global minimum on the RBF surface. The following strategies for setting the target value fStar is defined: 1: fStar = minsn - ((N - (n - nInit))/N )2 * Δn (Default), 2: fStar = minsn - (N - (n - nInit))/N * Δn . Strategy 1 and 2 depends on Δ n estimate (see DeltaRule). If infStep =1, add $-\infty$-step first in cycle. 3: fStar = $-\infty$-step, minsn-k *0.1*|minsn|k = N, ..., 0. These strategies had the following names in Gutmanns thesis: III, II, I.
DeltaRule	1 = Skip large f(x) when computing f(x) interval ?. 0 = Use all points. Default 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). This option is only possible if globalSolver = multiMin. Test for additional minimum is done in the local step (modN == N) If these additional local minima are used, in the printout modN = -2, -3, -4, ... are the iteration steps with these search points.
TargetMin	Which minimum, if several minima found, to select in the target value problem: =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 the RBF surface, minsn , is sufficiently lower than the best point (fM in ) found (default is 10-7 ).

Description of Outputs

Structure with result from optimization. The following fields are changed:

Field	Description
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.
CGO	Subfield WarmStartInfo saves warm start information, the same information as in cgoSave.mat, see below.
Inform	Information parameter. 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. 4 = No new point sampled for MaxCycle iteration steps. 5 = All sample points same as the best point for MaxCycle last iterations. 6 = All sample points same as previous point for MaxCycle last iterations. 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 a warm start possible, all CGO solvers saves information in the file cgoSave.mat. The file is created independent of the solver, which enables the user to call any CGO solver using the warm start information. cgoSave.mat is a MATLAB mat-file saved to the current directory. If the parameter SAVE is 1, the CGO solver saves the mat file every iteration, which enables the user to break the run and restart using warm start from the current state. SAVE = 1 is currently always set by the CGO solvers. If the cgoSave.mat file fails to open for writing, the information is also available in the output field Result.CGO.WarmStartInfo, if the run was concluded without interruption. Through a call to WarmDefGLOBAL, the Prob structure can be setup for warm start. In this case, the CGO solver will not load the data from cgoSave.mat. 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 (penalty added for costly Cc(x))
F_m	Vector with function values (replaced).
F00	Vector of pure function values, before penalties. Cc MMatrix with costly constraint values, C c(x). nInit Number of initial points.
Fpen	Vector with function values + additional penalty if infeasible using the linear constraints and noncostly nonlinear c(x).
fMinIdx	Index of the best point found.
rngState	Current state of the random number generator used.

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