TOMLAB OPTIMIZATION ENVIRONMENT: glcFast
|
TOMLAB OPTIMIZATION ENVIRONMENT: glcFast |
|
glcFast
Purpose
For solving global mixed-integer nonlinear programming problems.
Syntax
Result = glcFast(Prob);
Description
glcSolve solves general constrained mixed integer global
optimization. This version, glcFast, is a Fortran MEX
version of glcSolve.
glcSolve / glcFast implements the DIRECT
algorithm by Donald R. Jones
presented in the paper "DIRECT", Encyclopedia of Optimization,
Kluwer Academic Publishers, 2001.
The algorithm is expanded to handle nonlinear and linear equalities, and
linear inequalities.
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
Recommendation: Put the integers as the first variables!
Put low range integers before large range integers.
Linear constraints are specially treated.
Equality constraints are added as penalties to the objective.
Weights are computed automatically, assuimg f(x) scaled to be
roughly 1 at optimum. Otherwise scale f(x)
Usage
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,'GLCC',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 on the two next lines
Prob.optParam.MaxFunc = 500; % Change max number of function evaluations
Prob.optParam.MaxIter = 200; % Change the number of iterations to 200
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
Direct solver call:
Result = glcFast(Prob);
PrintResult(Result);
Driver call, including printing with level 2:
Result = tomRun('glcFast',Prob,[],2);
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)
but 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.
To make a restart, just set the restart flag, and call glcFast
once again:
Prob.WarmStart = 1;
Note - maximal number of iterations or function evaluations might have
to be increased:
Prob.optParam.MaxFunc = 20000; % A total of 20000 including previous run
Result = tomRun('glcFast',Prob,[],2);
IMPORTANT NOTE
The DIRECT algorithm only reaches the variable bounds in the
limit. Therefore convergence for global optimum where components are on the
bounds is slow.
One remedy is to reduce lower bounds with a tolerance, say 1E-4,
and add a similar tolerance 1E-4 to the upper bounds that might
be reached.
Another possibility is to fix a variable on its bound by setting the lower
and upper bounds equal.
The bound problem could be even worse for constrained problems. If a nonlinear problem only is feasible when a certain component is on its bound, then DIRECT will never get feasible in reasonable time. This problem could be even worse if the problem and the constraint is mixed-integer. The solution is to fix variables on their bounds, or, at least temporary, set the troublesome variables as integers (if the bounds are integer-valued) As for unconstrained problems, relaxing the bounds slightly, might also be a way to go.
Also try to avoid linear equality constraints, especially if some of the variables are integers. If say, two linear constraints are equalities, it is always possible to eliminate two variables, and reduce the dimension of the problem.
Always try to reduce the dimension as much as possible when using the
DIRECT algorithm, and try to shrink the box, defined by the lower
and upper bounds, as much as possible.
Input Parameters
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. Try to make a tight bound
x_U Upper bounds for each element in x. Try to make a tight bound
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 = Warm Start info, and same output as IterPrint = 1 (see below)
2 = Printing each iteration, Print iteration number, number of
evaluated points, best f(x) so far and its x-values
each iteration, where the best point has improved
3 = As PriLevOpt=2, also print sampled x, f(x) and if feasible
WarmStart If true, >0, glcFast reads the output from the last run from the
mat-file glcFastSave.mat, and continues from the last run.
optParam Structure in Prob, Prob.optParam.
Defines optimization parameters. Fields used:
IterPrint Print iteration #, # of evaluated points, best f(x) and x for
each iteration, where the best point has improved
bTol Linear constraint tolerance
cTol Nonlinear constraint tolerance
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, 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.
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.
GO Structure in Prob, Prob.GO.
Fields used:
fEqual All points with function values within tolerance fEqual are
considered to be global minima and returned
LinWeight RateOfChange = LinWeight*||a(i,:)|| for linear constraints.
Balance between linear and nonlinear constraints.
Default value 0.1.
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
To make a warm start possible, glcFast saves the following
information in the file glcFastSave.mat:
C Matrix with all rectangle centerpoints, in [0,1]-space. D Vector with distances from centerpoint to the vertices. F Vector with function values. G Matrix with constraint values for each point. Iter Number of iterations Name Name of the problem. Used for security if doing warm start Split Split(i,j) = # splits along dimension i of rectangle j Tr T(i) is the number of times rectangle i has been trisected. glcfMin Best function value found at a feasible point. feasible Flag indicating if a feasible point has been found. ignoreIdx Rectangles to be ignored in the rect. selection procedure. rateOfChange Rate of change s, for each constraint s0 Sum of observed rate of change s0 in the objective t t(i) is the total # splits along dimension i.
|
glcCluster | glcSolve | |