GlbDirect

Purpose

Solve box-bounded global optimization problems.

glbDirect 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}$.

glbDirect is a Fortran MEX implementation of glbSolve.

Calling Syntax

Result = glbDirectTL(Prob, varargin) 
Result = tomRun('glbDirect', 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 = Errors. 2 = Termination message and warm start info. 3 = Option summary.
	WarmStart	If true, > 0, glbDirect reads the output from the last run from Prob.glbDirect.WarmStartInto if it exists. If it doesn't exist, glbDirect attempts to open and read warm start data from mat-file glbDirectSave.mat. glbDirect uses this warm start information to continue from the last run.
	optParam	Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used:
	IterPrint	Print iteration log every IterPrint iteration. Set to 0 for no iteration log. PriLev must be set to at least 1 to have iteration log to be printed.
	MaxIter	Maximal number of iterations, default 200.
	MaxFunc	Maximal number of function evaluations, default 10000 (roughly).
	EpsGlob	Global/local weight parameter, default 1E-4.
	fGoal	Goal for function value, if empty not used.
	eps f	Relative accuracy for function value, f T ol == epsf . Stop if abs(f - f Goal)<= abs(f Goal) * f T ol , if f Goal = 0. Stop if abs(f - f Goal)<= f T ol , iff Goal == 0.
	eps x	Convergence tolerance in x. All possible rectangles are less than this tolerance(scaled to (0,1) ). See the output field maxTri.
	glbDirect	Structure in Prob, Prob.glbDirect. Solver specific.
options	Structure with options. These options have precedence over all other options in the Prob struct. Available options are: PRILEV: Equivalent to Prob.PrilevOpt. Default: 0 MAXFUNC: Eq. to Prob.optParam.MaxFunc. Default: 10000 MAXITER: Eq. to Prob.optParam.MaxIter. Default: 200 PARALLEL: Set to 1 in order to have glbDirect to call Prob.FUNCS.f with a matrix x of points to let the user function compute function values in parallel. Default: 0 WARMSTART: Eq. to Prob.WarmStart. Default: 0 ITERPRINT: Eq. to Prob.optParam.IterPrint. Default: 0 FUNTOL: Eq. to Prob.optParam.eps f. Default: 1e-2 VARTOL: Eq. to Prob.optParam.eps x. Default: 1e-13 GLWEIGHT: Eq. to Prob.optParam.EpsGlob. Default: 1e-4 Structure with WarmStartInfo. Use WarmDefDIRECT.m to define it.
	WarmStartInfo

Outputs

Result	Structure with result from optimization. The following fields are changed:
	x_k	Matrix with optimal points as columns.
	f_k	Function value at optimum.
	Iter	Number of iterations.
	FuncEv	Number function evaluations.
	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. 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 - f Goal)/abs(f Goal) <= f T ol. 3 = Maximum number of iterations done. 4 = Maximum number of function evaluations done. 91= Numerical trouble, did not find element in list. 92= Numerical trouble, No rectangle to work on. 99= Other error, see ExitFlag.
	glbDirect	Substructure for glbDirect specific result data.
	nextIterFunc	If optimization algorithm was stopped because of maximum number of function evaluations reached, this is the number of function evaluations required to complete the next iteration.
	maxTri	Maximum size of any triangles. Structure containing warm start data. Could be used to continue optimization
	WarmStartInfo	where glbDirect stopped.
	To make a warm start possible, glbDirect saves the following information in the structure Result.glbDirect.WarmStartInfo and file glbDirectSave.mat (for internal solver use only):
	points	Matrix with all rectangle centerpoints, in [0,1]-space.
	dRect	Vector with distances from centerpoint to the vertices.
	fPoints	Vector with function values.
	nIter	Number of iterations.
	lRect	Matrix with all rectangle side lengths in each dimension.
	Name	Name of the problem. Used for security if doing warm start.
	dMin	Row vector of minimum function value for each distance.
	ds	Row vector of all different distances, sorted.
	glbfMin	Best function value found at a feasible point.
	iMin	The index in D which has lowest function value, i.e. the rectangle which mini- mizes (F -glbf M in+E)./D where E = max(EpsGlob*abs(glbf M in), 1E -8).
	ign	Rectangles to be ignored in the rect. selection procedure.

Description

The global optimization routine glbDirect is an implementation of the DIRECT algorithm. The algorithm in glbDirect is a Fortran MEX implementation of the algorithm in glbSolve. 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 glbDirect 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 glbDirect with the final status of all parameters from the previous run, a so called warm start.

Assume that a run has been made with glbDirect 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 glbDirect a flag Prob.WarmStart should be set to one and WarmDefDIRECT run. Then glbDirect is using output previously obtained 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 glbSolve.m.