GlcCluster

Purpose

Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.

glcCluster solves problems of the 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}\\&&&{c}{x_{i}\in \mathbb {N} \;\forall i\in I}\\\end{array}}$

where $x,x_{L},x_{U}\in \mathbb {R} ^{n}$, $c(x),c_{L},c_{U}\in \mathbb {R} ^{m_{1}}$, $A\in \mathbb {R} ^{m_{2}\times n}$ and $b_{L},b_{U}\in \mathbb {R} ^{m_{2}}$.

The variables $x\in I$, the index subset of $1,...,n$ are restricted to be integers.

Calling Syntax

Result = glcCluster(Prob, maxFunc1, maxFunc2, maxFunc3, ProbL)
Result = tomRun('glcCluster', Prob, PriLev) (driver call)

Inputs

Prob	Problem description structure. The following fields are used:
	A	Constraint matrix for linear constraints.
	b_L	Lower bounds on the linear constraints.
	b_U	Upper bounds on the linear constraints.
	c_L	Lower bounds on the general constraints.
	c_U	Upper bounds on the general constraints.
	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.
	FUNCS.f	Name of m-file computing the objective function f (x).
	FUNCS.c	Name of m-file computing the vector of constraint functions c(x).
	PriLevOpt	Print level. 0=Silent. 1=Some output from each glcCluster phase. 2=More output from each phase. 3=Further minor output from each phase. 6=Use PrintResult( ,1) to print summary from each global and local run. 7 = Use PrintResult( ,2) to print summary from each global and local run. 8 = Use PrintResult( ,3) to print summary from each global and local run.
	WarmStart	If true, > 0, glcCluster warm starts the DIRECT solver. The DIRECT solver will utilize all points sampled in last run, from one or two calls, dependent on the success in last run. Note: The DIRECT solver may not be changed if doing WarmStart mat-file glcFastSave.mat, and continues from the last run.
	Name	Name of the problem. glcCluster uses the warmstart capability in glcFast and needs the name for security reasons.
	GO	Structure in Prob, Prob.GO. Fields used:
	maxFunc1	Number of function evaluations in 1st call to glcFast. Should be odd number (automatically corrected). Default 100 * dim(x) + 1.
	maxFunc2	Number of function evaluations in 2nd call to glcFast.
	maxFunc3	If glcFast is not feasible after maxFunc1 function evaluations, it will be repeat- edly called (warm start) doing maxFunc1 function evaluations until maxFunc3 function evaluations reached.
	ProbL	Structure to be used in the local search. By default the same problem structure as in the global search is used, Prob (see below). Using a second structure is important if optimal continuous variables may take values on bounds. glcFast used for the global search only converges to the simple bounds in the limit, and therefore the simple bounds may be relaxed a bit in the global search. Also, if the global search has difficulty fulfilling equality constraints exactly, the lower and upper bounds may be slightly relaxed. But being exact in the local search. Note that the local search is using derivatives, and can utilize given analytic derivatives. Otherwise the local solver is using numerical derivatives or automatic differentiation. If routines to provide derivatives are given in ProbL, they are used. If only one structure Prob is given, glcCluster uses the derivative routines given in the this structure.
	localSolver	Optionally change local solver used ('snopt' or 'npsol' etc.).
	DIRECT	DIRECT subsolver, either glcSolve or glcFast (default).
	localTry	Maximal number of local searches from cluster points. If <= 0, glcCluster stops after clustering. Default 100.
	maxDistmin	The minimal number used for clustering, default 0.05.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used are: PriLev, cTol, IterPrint, MaxIter, MaxFunc, EpsGlob, fGoal, eps_f, eps_x.
	MIP.IntVars	Structure in Prob, Prob.MIP. If empty, all variables are assumed non-integer (LP problem). If length(IntVars) > 1 ==> length(IntVars) == length(c) should hold. Then IntVars(i) == 1 ==> x(i) integer. IntVars(i) == 0 ==> x(i) real. If length(IntVars) < n, IntVars is assumed to be a set of indices. It is advised to number the integer values as the first variables, before the continuous. The tree search will then be done more efficiently.
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.
	c_k	Nonlinear constraints values at x_k.
	Iter	Number of iterations.
	FuncEv	Number function evaluations.
	maxTri	Maximum size of any triangle.
	ExitText	Text string giving ExitFlag and Inform information.
	Cluster	Subfield with clustering information
	x_k	Matrix with best cluster points.
	f_k	Row vector with f(x) values for each column in Cluster.x_k.
	maxDist	maxDist used for clustering.
	minDist	vector of all minimal distances between points.

Description

The routine glcCluster implements an extended version of DIRECT that handles problems with both nonlinear and integer constraints.

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 glcCluster is run for a predefined number of function evaluations and considers the best function value found as the optimal one. It is possible for the user to restart glcCluster with the final status of all parameters from the previous run, a so called warm start Assume that a run has been made with glcCluster on a certain problem for 500 function evaluations. Then a run of e.g. 200 function evaluations more should give the same result as if the run had been using 700 function evaluations in the first place. To do a warm start of glcCluster a flag Prob.WarmStart should be set to one. Then glcCluster is using output previously written to the file glcSave.mat to make the restart.

DIRECT does not explicitly handle equality constraints. It works best when the integer variables describe an ordered quantity and is less effective when they are categorical.

M-files Used

iniSolve.m, endSolve.m, glcFast.m