GlcCluster
{{#switch: | left =
{{#switch:{{#if: | {{{smallimage}}} | }} | none =| #default =
}} {{#if:{{#if: | {{{smallimageright}}} | }} | {{#ifeq:{{#if: | {{{smallimageright}}} | }}|none | | }} }}{{
#switch:left | left =| #default = }} {{#if:{{#if: | {{{smallimage}}} | }} | {{#if: | {{{smallimage}}} | }} | [[File:{{#switch:caution | critical = Ambox speedy deletion.png | important = Ambox deletion.png | warning = Ambox content.png | caution = Cleanup.png | move = Ambox move.png | protection = Ambox protection.png | notice | #default = Cleanup.png }} | {{#switch:left | left = 20x20px | #default = 40x40px }} |link=|alt=]] }}{{#switch:left | left =| #default = | {{#if:
| {{{smalltext}}} | Cleanup is needed}} | {{#switch:left
| left = {{#if: | {{{smallimageright}}} | }}| #default = {{#if:
}}| {{{smallimageright}}} |}} |
| #default =
{{#switch: | none =| #default =
}}{{#if: | {{#ifeq:|none
|| }} }}
{{
#switch: | left =| #default = }} {{#if: | | [[File:{{#switch:caution | critical = Ambox speedy deletion.png | important = Ambox deletion.png | warning = Ambox content.png | caution = Cleanup.png | move = Ambox move.png | protection = Ambox protection.png | notice | #default = Cleanup.png }} | {{#switch: | left = 20x20px | #default = 40x40px }} |link=|alt=]] }}{{#switch: | left =| #default = | Cleanup is needed Clean this article. |
{{#switch:
| left =| #default = |
}}
Purpose
Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.
glcCluster solves problems of the form
Failed to parse (unknown function "\multicolumn"): {\displaystyle \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} \\& & & \multicolumn{3}{c}{x_i \in \MATHSET{N} \; \forall i \in I} \\ \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle $x,x_{L},x_{U}\in \MATHSET{R}^{n}$}
,
Failed to parse (unknown function "\MATHSET"): {\displaystyle $c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}$}
,
Failed to parse (unknown function "\MATHSET"): {\displaystyle $A\in \MATHSET{R}^{m_{2}\times n}$}
and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle $b_{L},b_{U}\in \MATHSET{R}^{m_{2}}$}
.
Calling Syntax
Result = glcCluster(Prob, maxFunc1, maxFunc2, maxFunc3, ProbL)
Result = tomRun('glcCluster', Prob, PriLev) (driver call)
Description of 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 Table 141. 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(I ntV ars) > 1 ==> length(I ntV ars) == length(c) should hold. Then I ntV ars(i) == 1 ==> x(i) integer. I ntV ars(i) == 0 ==> x(i) real. If length(I ntV ars) < 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. |
Description of 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, see \[52\], 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