TOMLAB OPTIMIZATION ENVIRONMENT: glcSolve
|
TOMLAB OPTIMIZATION ENVIRONMENT: glcSolve |
|
glcSolve
Purpose
For solving general constrained mixed-integer global optimization problems.
Syntax
Result = glcSolve(Prob, varargin );
Description
Solves general constrained mixed integer global optimization problems.
glcSolve.m implements the algorithm DIRECT 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
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:
The name of the problem is set to "GLCF Test"
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, an example is shown on the next line
Prob.optParam.MaxFunc = 500; % Change max number of function evaluations
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
Result = glcSolve(Prob);
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)
or sending the extra parameters as additional input
Result = glcSolve(Prob,u,W);
function f = GLCF(x,Prob,u,W)
NOTE! If additional parameters are sent, Prob must be the second
input parameter to GLCF (and GLCC)
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"
To make a restart, just set the restart flag, and call glcSolve
once again:
Prob.WarmStart = 1;
Result = glcSolve(Prob); % Assuming no extra parameters in the call
PrintResult(Result);
If the maximum number of iterations have been reached, it must be increased:
Prob.optParam.MaxIter = 1000;
To change the number of function evaluations for each call to
glcFast:
Prob.optParam.MaxFunc = 500;
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 could be used to set the names into
the Prob struct:
Prob = mFiles(Prob,'GLCF',[],[],'GLCC');
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 = some printing. 2 = print each iteration
WarmStart If true, >0, glcSolve reads the output from the last run
from the mat-file glcSave.mat, and continues from the last run.
optParam Structure in Prob, Prob.optParam.
Defines optimization parameters. Fields used:
IterPrint Print one line each iteration
cTol Nonlinear constraint tolerance
MaxIter Maximal number of iterations, default 50.
MaxFunc Maximal number of function evaluations, default 200 (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 ExitText Text string giving ExitFlag and Inform information
To make a warm start possible, glcSolve saves the following
information in the file glcSave.mat:
Name Name of the problem. Used for security if doing warm start C Matrix with all rectangle centerpoints, in [0,1]-space. F Vector with function values. T T(i) is the number of times rectangle i has been trisected. D Vector with distances from centerpoint to the vertices. G Matrix with constraint values for each point. I_L I_L(i,j) is the lower bound for rect. j in integer dim. I(i) I_U I_U(i,j) is the upper bound for rect. j in integer dim. I(i) s_0 s_0 is used as s(0) s s(j) is the sum of observed rates of change for constraint j. t t(i) is the total # splits along dimension i. ignoreidx Rectangles to be ignored in the rect. selection proceedure. feasible Flag indicating if a feasible point has been found. Split Split(i,j) = # splits along dimension i of rectangle j glcfMin Best function value found at a feasible point. fMinIdx Indices of the currently best points fMinEQ sum(abs(infeasibilities)) for minimum points, 0 if no equalities
|
glcFast | goalSolve | |