GlcCluster: Difference between revisions
No edit summary |
No edit summary |
||
Line 126: | Line 126: | ||
==Description== | ==Description== | ||
glcCluster is | glcCluster is a global optimization algorithm, developed by Prof.Dr. Kenneth Holmström. | ||
It is a hybrid algorithm, combining the DIRECT global optimization algorithm, a clustering | It is a hybrid algorithm, combining the DIRECT global optimization algorithm, a clustering | ||
algorithm and local search. | algorithm and local search. |
Latest revision as of 06:15, 16 August 2013
Purpose
Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.
glcCluster solves problems of the form
where ,
,
and .
The variables , the index subset of 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
glcCluster is a global optimization algorithm, developed by Prof.Dr. Kenneth Holmström. It is a hybrid algorithm, combining the DIRECT global optimization algorithm, a clustering algorithm and local search.
glcCluster is using one of the following DIRECT algorithms: glcDirect (default), glcFast or glcSolve, for global search (Step 1). Step 2 is an adaptive clustering algorithm to find a suitable number of clusters, where the best point in each cluster is then used as an initial point for a local search (Step 3). The 4th step is to run the DIRECT algoirithm once again, to possibly improve. If the DIRECT algorithm improves the best point, a local search is finally made as Step 5 with the new best point(s) as starting points. The routine glcCluster implements an extended version of DIRECT that handles problems with both nonlinear and integer constraints.
M-files Used
iniSolve.m, endSolve.m, glcFast.m