GlbSolve

Purpose

Solve box-bounded global optimization problems. glbSolve solves problems of the form

${\begin{array}{cccccc}\min \limits _{x}&f(x)&&&&\\s/t&x_{L}&\leq &x&\leq &x_{U}\\\end{array}}$

where $f\in \mathbb {R}$ and $x,x_{L},x_{U}\in \mathbb {R} ^{n}$.

Calling Syntax

Result = glbSolve(Prob,varargin) 
Result = tomRun('glbSolve', Prob);

Inputs

Prob	Problem description structure. The following fields are used:
	x_L	Lower bounds for x, must be given to restrict the search space.
	x_U	Upper bounds for x, must be given to restrict the search space.
	Name	Name of the problem. Used for security if doing warm start.
	FUNCS.f	Name of m-file computing the objective function f (x).
	PriLevOpt	Print Level. 0 = silent. 1 = some printing. 2 = print each iteration.
	WarmStart	If true, > 0, glbSolve reads the output from the last run from the mat-file glbSave.mat, and continues from the last run.
	MaxCPU	Maximal CPU Time (in seconds) to be used.
	optParam	Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
	IterPrint	Print iteration \#, \# of evaluated points and best f(x) each iteration.
	MaxIter	Maximal number of iterations, default max(5000, n * 1000).
	MaxFunc	Maximal number of function evaluations, default max(10000, n * 2000).
	EpsGlob	Global/local weight parameter, default 1E-4.
	fGoal	Goal for function value, if empty not used.
	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.
	If warm start is chosen, the following fields saved to glbSave.mat are also used and contains information from the previous run:
	C	Matrix with all rectangle centerpoints, in [0,1]-space.
	D	Vector with distances from centerpoint to the vertices.
	DMin	Row vector of minimum function value for each distance.
	DSort	Row vector of all different distances, sorted.
	E	Computed tolerance in rectangle selection.
	F	Vector with function values.
	L	Matrix with all rectangle side lengths in each dimension.
	Name	Name of the problem. Used for security if doing warm start.
	glbfMin	Best function value found at a feasible point.
	iMin	The index in D which has lowest function value, i.e. the rectangle which minimizes (F - glbfMin+E)./D where E = max(EpsGlob*abs(glbfMin), 1E -8).
	varargin	Other parameters directly sent to low level routines.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	x_k	Matrix with all points giving the function value f_k.
	f_k	Function value at optimum.
	Iter	Number of iterations.
	FuncEv	Number function evaluations.
	maxTri	Maximum size of any triangle.
	ExitText	Text string giving ExitFlag and Inform information.
	ExitFlag	Exit code. 0 = Normal termination, max number of iterations /func.evals reached. 1 = Some bound, lower or upper is missing. 2 = Some bound is inf, must be finite. 4 = Numerical trouble determining optimal rectangle, empty set and cannot continue.
	Inform	Inform code. 0 = Normal Exit. 1 = Function value f is less than fGoal. 2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f - fGoal)/abs(fGoal) <= fTol. 9 = Max CPU Time reached.
	Solver	Solver used, 'glbSolve'.

Description

The global optimization routine glbSolve is an implementation of the DIRECT algorithm. DIRECT is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. Since no such constant is used, there is no natural way of defining convergence (except when the optimal function value is known). Therefore glbSolve runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbSolve with the final status of all parameters from the previous run, a so called warm start .

Assume that a run has been made with glbSolve on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbSolve a flag Prob.WarmStart should be set to one. Then glbSolve is using output previously written to the file glbSave.mat to make the restart. The m-file glbSolve also includes the subfunction conhull (in MEX) which is an implementation of the algorithm GRAHAMHULL with a modification. conhull is used to identify all points lying on the convex hull defined by a set of points in the plane.

M-files Used

iniSolve.m, endSolve.m