TOMLAB OPTIMIZATION ENVIRONMENT: glcCluster
|
TOMLAB OPTIMIZATION ENVIRONMENT: glcCluster |
|
glcCluster
Purpose
Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.
Syntax
Result = glcCluster(Prob, maxFunc1, maxFunc2)
Description
glcCluster solves general constrained mixed integer global
optimization
glcCluster is a hybrid algorithm, that is using
glcFast (a DIRECT algorithm) for global search, a new
clustering algorithm to find suitable initial points, and then local search from
these points. The 4th step is to run glcFast once again. If
glcFast improves the best point, a local search is finally made
with the new best point(s) as starting points.
Problem
min f(x)
x
s/t x_L <= x <= x_U
b_L <= A x <= b_U
c_L <= c(x) <= c_U
x(i) integer, for i in I
Usage
The algorithm has the following five phases:
Phase 1: Run glcFast maxFunc1 function value trials
If glcFast never finds a feasible point, it will run warm starts
with maxFunc1 function evaluations until totally maxFunc3 evaluations
If glcFast never finds a feasible point, and maxFunc is reached
then glcCLuster will stop
Phase 2: Apply a clustering algorithm on all sampled points by DIRECT
The algorithm finds a set of nPnt clusters. The point with the
lowest function value in each cluster is selected.
Phase 3: Do a local search with each of the nPnt best cluster points as
initial starting value. Most likely the local search will find
the global optimum, if there are not too many local minima
Phase 4: If the best point point in the local searches is better than the
best point found in the global search in Phase 1, this new point
is inserted in the glcFast database mat file glcFastSave. A warm
start run with glcFast doing maxFunc2 function trials is done.
(if solver glcSolve is used , the database file is glcSave.mat)
Phase 5: If glcFast has improved in Phase 4, a local search is done from
each of the points with the best function value
If the local search improves the best point found, then this point
is inserted in the glcFast data base mat file glcFastSave
It is then possible for the user to do further warm start runs
with glcFast (if solver glcSolve, database file glcSave.mat)
A warm start of glcCluster is also possible
Let the name of the problem be "GLCF Test"
The function GLCF is best written as
function f = GLCF(x, Prob)
Then any information, say u and W is easily sent to
GLCF (and GLCC) using the Prob structure.
See the example below.
Assume bounds x_L and x_U are initialized, as well as
the linear constraint matrix A, lower and upper bounds,
b_L and b_U on the linear constraints,
and lower and upper bounds c_L and c_U on the
nonlinear constraints (Put [] if all bounds are inf or
-inf). Use the TOMLAB Quick format:
Prob = glcAssign('GLCF',x_L,x_U,'GLCF Test',A,b_L,b_U,'GLCF',c_L,c_U);
Prob.user.u = u; Prob.user.W=W; % example of extra user data
% Default values are now set for PriLevOpt, and structure optParam
% To change a value, examples are shown below
Prob.GO.maxFunc1 = 1000; % Number of initial function valls to glcFast
Prob.GO.maxFunc2 = 200; % Number of final function valls to glcFast
Prob.GO.maxFunc3 = 2000; % Total number of calls in Phase 1, if infeasible
Prob.GO.Prob = ProbL; % Set the structure for the local search
Prob.optParam.MaxFunc = 10000; % Must be suffiently large for all local
% searches + maxFunc1 + maxFunc2
Prob.optParam.MaxIter = 1000; % Max number of iterations in each local
% search, normally much less are used
Prob.PriLevOpt = 1; % Some printing from each algorithm phase
If there are integer variables, they may be set as additional input
to glcAssign, or directly as the next line shows:
Prob.MIP.IntVars = [1 3]; % 1st and third variables are integers
A second structure ProbL for the local search is best setup using
conAssign.
Driver call, including printing with level 2:
Result = tomRun('glcCluster',Prob,[],2);
Direct solver call:
Result = glcCluster(Prob);
or with all input parameters as
Result = glcCluster(Prob, maxFunc1, maxFunc2, maxFunc3, ProbL)
Then print the results with call
PrintResult(Result);
The user function GLCF is written as
function f = GLCF(x, Prob)
u = Prob.user.u; W = Prob.user.W;
f = "some function of x, u and W"
It is also possible to use the function format
function f = GLCF(x)
Put then any additional parameters must be sent as global variables.
The user function GLCC, computing the nonlinear constraints, is
written as
function c = GLCC(x, Prob)
u = Prob.user.u; W = Prob.user.W;
c = "some vector function of x, V and W";
Note! If GLCF has the 2nd input argument Prob,
also GLCC must have that.
Input Parameters
The following two parameters are either set in Prob.GO, or as extra
input
maxFunc1 Number of function evaluations in 1st call to glcFast.
Should be odd number (automatically corrected).
Default 10*dim(x) + 1. May also be set as Prob.GO.maxFunc1
maxFunc2 Number of function evaluations in 2nd call to glcFast.
May also be set as Prob.GO.maxFunc2
maxFunc3 If glcFast is not feasible after maxFunc1 function evaluations,
it will be repeatedly called (warm start) doing maxFunc1 function
evaluations until maxFunc3 function evaluations reached.
May also be set as Prob.GO.maxFunc3
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
May also be set as Prob.GO.Prob
Prob Structure, where the following variables are used:
Name Name of the problem. Used for security if doing warm start
USER.f The routine to compute the function, given as a string, say GLCF
USER.c The routine to compute the nonlinear constraint, say GLCC
A call to mFiles.m or glcAssign.m sets these fields.
x_L Lower bounds for each element in x.
x_U Upper bounds for each element in x.
b_L Lower bounds for the linear constraints
b_U Upper bounds for the linear constraints
A Linear constraint matrix
c_L Lower bounds for the nonlinear constraints
c_U Upper bounds for the nonlinear constraints
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.
optParam Structure in Prob, Prob.optParam.
Defines optimization parameters. Fields used:
IterPrint In the global optimization (glcFast):
Print iteration #, # of evaluated points, best f(x) and x for
each iteration, where the best point has improved
IterPrint = 1 implies PriLevOpt >= 1
cTol Nonlinear constraint tolerance
MaxIter Maximal number of iterations in local search, default 1000
MaxFunc Maximal number of function evaluations, default 10000 (roughly)
As 1st step needs maxFunc = 100*n + 1; maxFunc >> 100*n
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 == eps_f
Stop if abs(f-fGoal) <= abs(fGoal) * fTol , if fGoal \=0
Stop if abs(f-fGoal) <= fTol , if fGoal ==0
eps_x Convergence tolerance in x. All possible rectangles are
less than this tolerance (scaled to (0,1) )
See the output field maxTri.
GO
localSolver Optionally change local solver used ('snopt' or 'npsol' etc.)
maxFunc1 See description above
maxFunc2 See description above
maxFunc3 See description above
ProbL See description above
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
MIP Structure in Prob, Prob.MIP.
Defines integer optimization parameters. Fields used:
IntVars: If IntVars is a scalar, then variables 1,...,IntVars are
assumed to be integers.
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 adviced to number the integer values as the first
variables, before the continuous. The tree search will then
be done more efficiently.
Output Parameters
Result Structure with results from optimization x_k Matrix with optimal points as columns. f_k The best function value found so far c_k Nonlinear constraints values at x_k Iter Number of iterations FuncEv Number of function evaluations maxTri Maximum size of any triangle ExitText Text string giving ExitFlag and Inform information ------------------------------------------------------- Result.Cluster, subfield with clustering information ------------------------------------------------------- Cluster.x_k Matrix with best cluster points Cluster.f_k Row vector with f(x) values for each column in Cluster.x_k Cluster.maxDist maxDist used for clustering Cluster.minDist vector of all minimal distances between points
|
glbSolve | glcFast | |