TOMLAB Solver Reference: Difference between revisions
Line 21: | Line 21: | ||
*[[TOMLAB Solver conSolve]] | *[[TOMLAB Solver conSolve]] | ||
==cutPlane== | |||
Solve mixed integer linear programming problems (MIP). | Solve mixed integer linear programming problems (MIP). | ||
*[[cutPlane]] | |||
* | |||
====DualSolve==== | ====DualSolve==== |
Revision as of 06:48, 10 July 2011
{{#switch:
| left =
| #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 = |
}}
This page is part of the TOMLAB Manual. See TOMLAB Manual. |
Detailed descriptions of the TOMLAB solvers, driver routines and some utilities are given in the following sections. Also see the M-file help for each solver. All solvers except for the TOMLAB Base Module are described in separate manuals.
For a description of solvers called using the MEX-file interface, see the M-file help, e.g. for the MINOS solver minosTL.m. For more details, see the User's Guide for the particular solver.
clsSolve
Solves dense and sparse nonlinear least squares optimization problems with linear inequality and equality con- straints and simple bounds on the variables.
conSolve
Solve general constrained nonlinear optimization problems.
cutPlane
Solve mixed integer linear programming problems (MIP).
DualSolve
Purpose
Solve linear programming problems when a dual feasible solution is available.
DualSolve solves problems of the form
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 \in \MATHSET{R}^{n}$}
, Failed to parse (unknown function "\MATHSET"): {\displaystyle $A\in \MATHSET{R}^{m\times n}$}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle $b_{U} \in \MATHSET{R}^{m}$}
.
Finite upper bounds on x are added as extra inequality constraints. Finite nonzero lower bounds on x are added as extra inequality constraints. Fixed variables are treated explicitly. Adding slack variables and making necessary sign changes gives the problem in the standard form
and the following dual problem is solved,
with Failed to parse (unknown function "\MATHSET"): {\displaystyle $x,c \in \MATHSET{R}^{n}$}
, Failed to parse (unknown function "\MATHSET"): {\displaystyle $A\in \MATHSET{R}^{\hat{m}\times n}$}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle $b,y \in \MATHSET{R}^{m}$}
.
Calling Syntax
[Result] = DualSolve(Prob)
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
QP.c | Constant vector. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point, must be dual feasible. | |
y_0 | Dual parameters (Lagrangian multipliers) at x _0. | |
QP.B | Active set B_0 at start: | |
B(i) = 1: Include variable x(i) is in basic set. | ||
B(i) = 0: Variable x(i) is set on its lower bound. | ||
B(i) = -1: Variable x(i) is set on its upper bound. | ||
Solver.Alg | Variable selection rule to be used: | |
0: Minimum reduced cost (default). | ||
1: Bland's anti-cycling rule. | ||
2: Minimum reduced cost. Dantzig's rule. | ||
PriLevOpt | Print Level. | |
optParam | Structure with special fields for optimization parameters, see Table 141. | |
Fields used are: MaxIter, wait, eps f, eps Rank and xTol. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
x_k | Optimal primal solution x. | |
f_k | Function value at optimum. | |
v_k | Optimal dual parameters. Lagrange multipliers for linear constraints. | |
x_0 | Starting point. | |
Iter | Number of iterations. | |
QP.B | Optimal active set. | |
ExitFlag | Exit flag: | |
0: Optimal solution found. | ||
1: Maximal number of iterations reached. No primal feasible solution found. | ||
2: Infeasible Dual problem. | ||
4: Illegal step length due to numerical difficulties. Should not occur. | ||
6: No dual feasible starting point found. | ||
7: Illegal step length due to numerical difficulties. | ||
8: Convergence because fk >= QP.DualLimit. | ||
9: for some i. No solution exists. | ||
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
c | Constant vector in standard form formulation. | |
A | Constraint matrix for linear constraints in standard form. | |
b | Right hand side in standard form. |
Description
When a dual feasible solution is available, the dual simplex method is possible to use. DualSolve implements this method using the algorithm in \[35, pages 105-106\]. There are three rules available for variable selection. Bland's cycling prevention rule is the choice if fear of cycling exist. The other two are variants of minimum reduced cost variable selection, the original Dantzig's rule and one which sorts the variables in increasing order in each step (the default choice).
M-files Used
cpTransf.m
See Also
lpSimplex
expSolve
Purpose
Solve exponential fitting problems for given number of terms p.
Calling Syntax
Prob = expAssign( ... );
Result = expSolve(Prob, PriLev); or
Result = tomRun('expSolve', PriLev);
Description of Inputs
Prob.SolverL2||Name of solver to use. If empty, TOMLAB selects dependent on license.Prob | Problem created with expAssign. |
PriLev | Print level in tomRun call. |
Description of Outputs
Result TOMLAB | Result structure as returned by solver selected by input argument Solver. |
LS | Statistical information about the solution. See Table 153, page 239. |
Global Parameters Used
Description
expSolve solves a cls (constrained least squares) problem for exponential fitting formulates by expAssign. The problem is solved with a suitable or given cls solver.
The aim is to provide a quicker interface to exponential fitting, automating the process of setting up the problem structure and getting statistical data.
M-files Used
GetSolver, expInit, StatLS and expAssign
Examples
Assume that the Matlab vectors t, y contain the following data:
To set up and solve the problem of fitting the data to a two-term exponential model
,
give the following commands:
>> p = 2; % Two terms >> Name = 'Simple two-term exp fit'; % Problem name, can be anything >> wType = 0; % No weighting >> SepAlg = 0; % Separable problem >> Prob = expAssign(p,Name,t,y,wType,[],SepAlg); >> Result = tomRun('expSolve',Prob,1); >> x = Result.x_k' x = 0.01 0.58 72.38 851.68
The vector contains the parameters as so the solution may be visualized with
>> plot(t,y,'-*', t,x(3)*exp(-t*x(1)) + x(4)*exp(-t*x(2)) );
Figure 6: Results of fitting experimental data to two-term exponential model. Solid line: final model, dash-dot: data.
glbDirect
Purpose
Solve box-bounded global optimization problems.
glbDirect solves problems of the form
where Failed to parse (unknown function "\MATHSET"): {\displaystyle $f \in \MATHSET{R}$}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle $x,x_{L},x_{U}\in \MATHSET{R} ^{n}$}
.
glbDirect is a Fortran MEX implementation of glbSolve.
Calling Syntax
Result = glbDirectTL(Prob,varargin)
Result = tomRun('glbDirect', Prob);
Description of Inputs
options||Structure with options. These options have precedence over all other options in the Prob struct. Available options are: MAXITER: Eq. to Prob.optParam.MaxIter. Default: 200Prob | Problem description structure. The following fields are used: | |
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. | |
Name | Name of the problem. Used for security if doing warm start. | |
FUNCS.f | Name of m-file computing the objective function f (x). | |
PriLevOpt | Print Level. 0 = Silent. 1 = Errors. 2 = Termination message and warm start info. 3 = Option summary. | |
WarmStart | If true, > 0, glbDirect reads the output from the last run from Prob.glbDirect.WarmStartInto if it exists. If it doesn't exist, glbDirect attempts to open and read warm start data from mat-file glbDirectSave.mat. glbDirect uses this warm start information to continue from the last run. | |
optParam | Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used: | |
IterPrint | Print iteration log every IterPrint iteration. Set to 0 for no iteration log. PriLev must be set to at least 1 to have iteration log to be printed. | |
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, f T ol == epsf . Stop if abs(f - f Goal)<= abs(f Goal) * f T ol , if f Goal = 0. Stop if abs(f - f Goal)<= f T ol , iff Goal == 0. | |
eps x | Convergence tolerance in x. All possible rectangles are less than this tolerance(scaled to (0,1) ). See the output field maxTri. | |
glbDirect | Structure in Prob, Prob.glbDirect. Solver specific. | |
PRILEV: Equivalent to Prob.PrilevOpt. Default: 0 | ||
MAXFUNC: Eq. to Prob.optParam.MaxFunc. Default: 10000 | ||
PARALLEL: Set to 1 in order to have glbDirect to call Prob.FUNCS.f with a matrix x of points to let the user function compute function values in parallel. Default: 0 | ||
WARMSTART: Eq. to Prob.WarmStart. Default: 0 | ||
ITERPRINT: Eq. to Prob.optParam.IterPrint. Default: 0 | ||
FUNTOL: Eq. to Prob.optParam.eps f. Default: 1e-2 | ||
VARTOL: Eq. to Prob.optParam.eps x. Default: 1e-13 | ||
GLWEIGHT: Eq. to Prob.optParam.EpsGlob. Default: 1e-4 | ||
Structure with WarmStartInfo. Use WarmDefDIRECT.m to define it. | ||
WarmStartInfo |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
x_k | Matrix with optimal points as columns. | |
f_k | Function value at optimum. | |
Iter | Number of iterations. | |
FuncEv | Number function evaluations. | |
ExitText | Text string giving ExitFlag and Inform information. | |
ExitFlag | Exit code. | |
0 = Normal termination, max number of iterations /func.evals reached. | ||
1 = Some bound, lower or upper is missing. | ||
2 = Some bound is inf, must be finite. | ||
4 = Numerical trouble determining optimal rectangle, empty set and cannot continue. | ||
Inform | Inform code. | |
1 = Function value f is less than fGoal. | ||
2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f - f Goal)/abs(f Goal) <= f T ol. | ||
3 = Maximum number of iterations done. | ||
4 = Maximum number of function evaluations done. | ||
91= Numerical trouble, did not find element in list. | ||
92= Numerical trouble, No rectangle to work on. | ||
99= Other error, see ExitFlag. | ||
glbDirect | Substructure for glbDirect specific result data. | |
nextIterFunc | If optimization algorithm was stopped because of maximum number of function evaluations reached, this is the number of function evaluations required to complete the next iteration. | |
maxTri | Maximum size of any triangles. Structure containing warm start data. Could be used to continue optimization | |
WarmStartInfo | where glbDirect stopped. | |
To make a warm start possible, glbDirect saves the following information in the structure Result.glbDirect.WarmStartInfo and file glbDirectSave.mat (for internal solver use only): | ||
points | Matrix with all rectangle centerpoints, in [0,1]-space. | |
dRect | Vector with distances from centerpoint to the vertices. | |
fPoints | Vector with function values. | |
nIter | Number of iterations. | |
lRect | Matrix with all rectangle side lengths in each dimension. | |
Name | Name of the problem. Used for security if doing warm start. | |
dMin | Row vector of minimum function value for each distance. | |
ds | Row vector of all different distances, sorted. | |
glbfMin | Best function value found at a feasible point. | |
iMin | The index in D which has lowest function value, i.e. the rectangle which mini- mizes (F -glbf M in+E)./D where E = max(EpsGlob*abs(glbf M in), 1E -8). | |
ign | Rectangles to be ignored in the rect. selection procedure. |
Description
The global optimization routine glbDirect is an implementation of the DIRECT algorithm presented in \[14\]. The algorithm in glbDirect is a Fortran MEX implementation of the algorithm in glbSolve. 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 glbDirect runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbDirect with the final status of all parameters from the previous run, a so called warm start. Assume that a run has been made with glbDirect on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbDirect a flag Prob.WarmStart should be set to one and WarmDefDIRECT run. Then glbDirect is using output previously obtained to make the restart. The m-file glbSolve also includes the subfunction conhull (in MEX) which is an implementation of the algorithm GRAHAMHULL in \[65, page 108\] with the modifications proposed on page 109. conhull is used to identify all points lying on the convex hull defined by a set of points in the plane.
M-files Used
iniSolve.m, endSolve.m glbSolve.m.
glbSolve
Purpose
Solve box-bounded global optimization problems. glbSolve solves problems of the form
where Failed to parse (unknown function "\MATHSET"): {\displaystyle $f \in \MATHSET{R}$}
and Failed to parse (unknown function "\MATHSET"): {\displaystyle $x,x_{L},x_{U}\in \MATHSET{R} ^{n}$}
.
Calling Syntax
Result = glbSolve(Prob,varargin)
Result = tomRun('glbSolve', Prob);
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
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. | |
Name | Name of the problem. Used for security if doing warm start. | |
FUNCS.f | Name of m-file computing the objective function f (x). | |
PriLevOpt | Print Level. 0 = silent. 1 = some printing. 2 = print each iteration. | |
WarmStart | If true, > 0, glbSolve reads the output from the last run from the mat-file glbSave.mat, and continues from the last run. | |
MaxCPU | Maximal CPU Time (in seconds) to be used. | |
optParam | Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used: | |
IterPrint | Print iteration \#, \# of evaluated points and best f(x) each iteration. | |
MaxIter | Maximal number of iterations, default max(5000, n * 1000). | |
MaxFunc | Maximal number of function evaluations, default max(10000, n * 2000). | |
EpsGlob | Global/local weight parameter, default 1E-4. | |
fGoal | Goal for function value, if empty not used. | |
eps_f | Relative accuracy for function value, f T ol == epsf . Stop if abs(f - f Goal)<= abs(f Goal) * f T ol , if f Goal = 0. Stop if abs(f - f Goal) <= f T ol , if f Goal == 0. | |
If warm start is chosen, the following fields saved to glbSave.mat are also used and contains information from the previous run: | ||
C | Matrix with all rectangle centerpoints, in [0,1]-space. | |
D | Vector with distances from centerpoint to the vertices. DMin Row vector of minimum function value for each distance. DSort Row vector of all different distances, sorted. | |
E | Computed tolerance in rectangle selection. | |
F | Vector with function values. | |
L | Matrix with all rectangle side lengths in each dimension. Name Name of the problem. Used for security if doing warm start. glbfMin Best function value found at a feasible point. | |
iMin | The index in D which has lowest function value, i.e. the rectangle which mini- mizes (F -glbf M in+E)./D where E = max(EpsGlob*abs(glbf M in), 1E -8). | |
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. | |
Iter | Number of iterations. | |
FuncEv | Number function evaluations. | |
maxTri | Maximum size of any triangle. | |
ExitText | Text string giving ExitFlag and Inform information. | |
ExitFlag | Exit code. | |
0 = Normal termination, max number of iterations /func.evals reached. | ||
1 = Some bound, lower or upper is missing. | ||
2 = Some bound is inf, must be finite. | ||
4 = Numerical trouble determining optimal rectangle, empty set and cannot continue. | ||
Inform | Inform code. | |
0 = Normal Exit. | ||
1 = Function value f is less than fGoal. | ||
2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f - f Goal)/abs(f Goal) <= f T ol. | ||
9 = Max CPU Time reached. | ||
Solver | Solver used, 'glbSolve'. |
Description
The global optimization routine glbSolve is an implementation of the DIRECT algorithm presented in \[14\]. 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 glbSolve runs a predefined number of iterations and considers the best function value found as the optimal one. It is possible for the user to restart glbSolve with the final status of all parameters from the previous run, a so called warm start Assume that a run has been made with glbSolve on a certain problem for 50 iterations. Then a run of e.g. 40 iterations more should give the same result as if the run had been using 90 iterations in the first place. To do a warm start of glbSolve a flag Prob.WarmStart should be set to one. Then glbSolve is using output previously written to the file glbSave.mat to make the restart. The m-file glbSolve also includes the subfunction conhull (in MEX) which is an implementation of the algorithm GRAHAMHULL in \[65, page 108\] with the modifications proposed on page 109. conhull is used to identify all points lying on the convex hull defined by a set of points in the plane.
M-files Used
iniSolve.m, endSolve.m
glcCluster
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 (unknown function "\MATHSET"): {\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
glcDirect
Purpose
Solve global mixed-integer nonlinear programming problems.
glcDirect solves problems of the form
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 (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 $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}}$}
.
The variables 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 $x \in I$, the index subset of $1,...,n$}
are restricted to be integers. 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, assuming f(x) scaled to be roughly 1 at optimum. Otherwise scale f(x).
glcDirect is a Fortran MEX implementation of glcSolve.
Calling Syntax
Result = glcDirectTL(Prob,varargin)
Result = tomRun('glcDirect', Prob);
Description of Inputs
1 demands||f cALL == 0. This option could save some time if f(x) is a bit costly, however overall performance could on some problems be dramatically worse.Prob | Problem description structure. The following fields are used: | |
Name | Problem name. Used for safety when doing warm starts. | |
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). | |
A | Linear constraints matrix. | |
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 finite to restrict the search space. | |
x_U | Upper bounds for x, must be finite to restrict the search space. | |
PriLevOpt | Print Level. This controls both regular printing from glcDirect and the amount of iteration log information to print. | |
0 = Silent. | ||
1 = Warnings and errors printed. Iteration log on iterations im- proving function value. | ||
2 = Iteration log on all iterations. | ||
3 = Log for each function evaluation. | ||
4 = Print list of parameter settings. | ||
See optParam.IterPrint for more information on iteration log printing. | ||
WarmStart | If true, > 0, glcDirect reads the output from the last run from Prob.glcDirect.WarmStartInfo if it exists. If it doesn't exist, glcDirect attempts to open and read warm start data from mat-file glcDirectSave.mat. glcDirect uses this warm start information to continue from the last run. | |
MaxCPU | Maximum CPU Time (in seconds) to be used. | |
MIP | Structure in Prob, Prob.MIP. | |
Intvars | 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. | |
fIP | An upper bound on the optimal f(x) value. If empty, set as Inf. | |
xIP | The x-values giving the fIP value. If fIP empty and xIP given, fIP will be computed if xIP nonempty, its feasibility is checked | |
glcDirect | Structure with DIRECT algorithm specific parameters. Fields used: | |
fcALL | =0 (Default). If linear constraints cannot be feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point. | |
=1 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Do not update rates of change for the constraints. | ||
=2 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Update rates of change constraints. | ||
useRoC | =1 (Default). Use original Rate of Change (RoC) for constraints to weight the constraint violations in selecting which rectangle divide. | |
=0 Avoid RoC, giving equal weights to all constraint violations. Suggested if difficulty to find feasible points. For problems where linear constraints have been added among the nonlinear (NOT RECOMMENDED; AVOID!!!), then option useRoc=0 has been successful, whereas useRoC completely fails. | ||
=2 Avoid RoC for linear constraints, giving weight one to these constraint violations, whereas the nonlinear constraints use RoC. | ||
=3 Use RoC for nonlinear constraints, but linear constraints are not used to determine which rectangle to use. | ||
BRANCH | =0 Divide rectangle by selecting the longest side, if ties use the lowest index. This is the Jones DIRECT paper strategy. | |
=1 First branch the integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0. DEFAULT! Normally much more efficient than =0 for mixed- integer problems. | ||
=2 First branch the integer variables with 1,2 or 3 possible values, e.g \[0,1\],\[0,2\] variables, selecting the variable with least splits. Then branch the other integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0. | ||
=3 Like =2, but use priorities on the variables, similar to mipSolve, see Prob.MIP.VarWeight. | ||
RECTIE | When minimizing the measure to find which new rectangle to try to get feasible, there are often ties, several rectangles have the same minimum. RECTIE = 0 or 1 seems reasonable choices. Rectangles with low index are often larger then the rectangles with higher index. Selecting one of each type could help, but often =0 is fastest. | |
=0 Use the rectangle with value a, with lowest index (original). | ||
=1 (Default): Use 1 of the smallest and 1 of largest rectangles. | ||
=2 Use the last rectangle with the same value a, not the 1st. | ||
=3 Use one of the smallest rectangles with same value a. | ||
=4 Use all rectangles with the same value a, not just the 1st. | ||
EqConFac | Weight factor for equality constraints when adding to objective function f(x) (Default value 10). The weight is computed as EqConFac/"right or left hand side constant value", e.g. if the constraint is Ax <= b, the weight is EqCon- Fac/b If DIRECT just is pushing down the f(x) value instead of fulfilling the equality constraints, increase EqConFac. | |
AxFeas | Set nonzero to make glcDirect skip f(x) evaluations, when the linear constraints are infeasible, and still no feasible point has been found. The default is 0. Value | |
fEqual | All points with function values within tolerance fEqual are considered to be global minima and returned. Default 1E-10. | |
LinWeight | \|a(i, :)\|\| for linear constraints. Balance be- tween linear and nonlinear constraints. Default 0.1. The higher value, the less influence from linear constraints. | |
alpha | Exponential forgetting factor in RoC computation, default 0.9. | |
AvIter | How many values to use in startup of RoC computation before switching to exponential smoothing with forgetting factor alpha. Default 50. | |
optParam | Structure with special fields for optimization parameters, see Table 141 on page 229. | |
Fields used by glcDirect are: IterPrint, bTol, cTol, MaxIter, MaxFunc, EpsGlob, fGoal, eps f, eps x. | ||
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. | |
ExitFlag | 0 = Normal termination, max number of iterations func.evals reached. | |
2 = Some upper bounds below lower bounds. | ||
4 = Numerical trouble, and cannot continue. | ||
7 = Reached maxFunc or maxIter, NOT feasible. | ||
8 = Empty domain for integer variables. | ||
10= Input errors. | ||
Inform | 1 = Function value f is less than fGoal. | |
2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f-fGoal)/abs(fGoal) <= fTol. | ||
3 = Maximum number of iterations done. | ||
4 = Maximum number of function evaluations done. | ||
5 = Maximum number of function evaluations would most likely be too many in the next iteration, save warm start info, stop. | ||
6 = Maximum number of function evaluations would most likely be too many in the next iteration, because 2 * sLen >= maxFDim - nFunc, save warm start info, stop. | ||
7 = Space is dense. | ||
8 = Either space is dense, or MIP is dense. | ||
10= No progress in this run, return solution from previous one. | ||
91= Infeasible. | ||
92= No rectangles to work on. | ||
93= sLen = 0, no feasible integer solution exists. | ||
94= All variables are fixed. | ||
95= There exist free constraints. | ||
glcDirect | Substructure for glcDirect specific result data. | |
convFlag | Converge status flag from solver. | |
Structure with warm start information. Use WarmDefDIRECT to reuse this | ||
WarmStartInfo | information in another run. | |
glcDirectSave.mat | To make a warm start possible, glcDirect saves the following information in the structure Result.glcDirect.WarmStartInfo and file glcDirectSave.mat (for internal solver use only): | |
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) is the number of splits along dimension i of rectangle j. | |
Tr | T r(i) is the number of times rectangle i has been trisected. | |
fMinIdx | Indices of the currently best points. | |
fMinEQ | sum(abs(infeasibilities)) for minimum points, 0 if no equalities. | |
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 rectangle selection procedure. | |
roc | Rate of change s, for each constraint. | |
s0 | Sum of observed rate of change s0 in the objective. | |
t | t(i) is the total number of splits along dimension i. |
Description
The routine glcDirect implements an extended version of DIRECT, see \[52\], that handles problems with both nonlinear and integer constraints. The algorithm in glcDirect is a Fortran MEX implementation of the algorithm in glcSolve.
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 glcDirect 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 glcDirect with the final status of all parameters from the previous run, a so called warm start. Assume that a run has been made with glcDirect 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 glcDirect a flag Prob.WarmStart should be set to one. Then glcDirect will use output previously written to the file glcDirectSave.mat (or the warm start structure) 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 and glcSolve.m.
Warnings
A significant portion of glcDirect is coded in Fortran MEX format. If the solver is aborted, it may have allocated memory for the computations which is not returned. This may lead to unpredictable behavior if glcDirect is started again. To reduce the risk of trouble, do "clear mex" if a run has been aborted.
glcSolve
Purpose
Solve general constrained mixed-integer global optimization problems.
glcSolve solves problems of the form
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 \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} \\& & & x_i \mathrm{\ \ integer} & & i \in I \\\end{array} }
where 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 $x,x_{L},x_{U}\in \MATHSET{R}^{n}$}
, 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 $c(x),c_{L},c_{U}\in\MATHSET{R}^{m_{1}}$}
, 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 $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}}$}
.
The variables 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 $x \in I$} , the index subset of 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 $1,...,n$} are restricted to be integers. 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, assuming f(x) scaled to be roughly 1 at optimum. Otherwise scale f(x).
Calling Syntax
Result = glcSolve(Prob,varargin)
Result = tomRun('glcSolve', Prob);
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. | |
MIP | Structure in Prob, Prob.MIP. | |
Intvars | 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. | |
fIP | An upper bound on the optimal f(x) value. If empty, set as Inf. | |
xIP | The x-values giving the fIP value. If fIP empty and xIP given, fIP will be computed if xIP nonempty, its feasibility is checked | |
x_L | Lower bounds for x, must be given to restrict the search space. Any lower bounds that are inf are changed to -10000. | |
x_U | Upper bounds for x, must be given to restrict the search space. Any upper bounds that are inf are changed to 10000. | |
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). | |
Name | Name of the problem. Used for security if doing warm start. | |
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. NOTE: All rectangles that are fathomed in the previous run are deleted. This saves space and computational time and enables solving larger problems and more function evaluations to be done. | |
MaxCPU | Maximal CPU Time (in seconds) to be used. | |
glcDirect | Structure with DIRECT algorithm specific parameters. Fields used: | |
fcALL | =0 (Default). If linear constraints cannot be feasible anywhere inside rectangle, skip f(x) and c(x) computation for middle point. | |
=1 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Do not update rates of change for the constraints. | ||
=2 Always compute f(x) and c(x), even if linear constraints are not feasible anywhere in rectangle. Update rates of change constraints. | ||
useRoC | =1 (Default). Use original Rate of Change (RoC) for constraints to weight the constraint violations in selecting which rectangle divide. | |
=0 Avoid RoC, giving equal weights to all constraint violations. Suggested if difficulty to find feasible points. For problems where linear constraints have been added among the nonlinear (NOT RECOMMENDED; AVOID!!!), then option useRoc=0 has been successful, whereas useRoC completely fails. | ||
=2 Avoid RoC for linear constraints, giving weight one to these constraint violations, whereas the nonlinear constraints use RoC. | ||
=3 Use RoC for nonlinear constraints, but linear constraints are not used to determine which rectangle to use. | ||
BRANCH | =0 Divide rectangle by selecting the longest side, if ties use the lowest index. This is the Jones DIRECT paper strategy. | |
=1 First branch the integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0. DEFAULT! Normally much more efficient than =0 for mixed- integer problems. | ||
=2 First branch the integer variables with 1,2 or 3 possible values, e.g \[0,1\],\[0,2\] variables, selecting the variable with least splits. Then branch the other integer variables, selecting the variable with the least splits. If all integer variables are split, split on the continuous variables as in BRANCH=0. | ||
=3 Like =2, but use priorities on the variables, similar to mipSolve, see Prob.MIP.VarWeight. | ||
RECTIE | When minimizing the measure to find which new rectangle to try to get feasible, there are often ties, several rectangles have the same minimum. RECTIE = 0 or 1 seems reasonable choices. Rectangles with low index are often larger then the rectangles with higher index. Selecting one of each type could help, but often =0 is fastest. | |
=0 Use the rectangle with value a, with lowest index (original). | ||
=1 (Default): Use 1 of the smallest and 1 of largest rectangles. | ||
=2 Use the last rectangle with the same value a, not the 1st. | ||
=3 Use one of the smallest rectangles with same value a. | ||
=4 Use all rectangles with the same value a, not just the 1st. | ||
EqConFac | Weight factor for equality constraints when adding to objective function f(x) (Default value 10). The weight is computed as EqConFac/"right or left hand side constant value", e.g. if the constraint is Ax <= b, the weight is EqCon- Fac/b If DIRECT just is pushing down the f(x) value instead of fulfilling the equality constraints, increase EqConFac. | |
AxFeas | Set nonzero to make glcSolve skip f(x) evaluations, when the linear constraints are infeasible, and still no feasible point has been found. The default is 0. Value 1 demands f cALL == 0. This option could save some time if f(x) is a bit costly, however overall performance could on some problems be dramatically worse. | |
fEqual | All points with function values within tolerance fEqual are considered to be global minima and returned. Default 1E-10. | |
LinWeight | RateOfChange = LinWeight * ||a(i, :)|| for linear constraints. Balance be- tween linear and nonlinear constraints. Default 0.1. The higher value, the less influence from linear constraints. | |
alpha | Exponential forgetting factor in RoC computation, default 0.9. | |
AvIter | How many values to use in startup of RoC computation before switching to exponential smoothing with forgetting factor alpha. Default 50. | |
If WarmStart is chosen, the following fields in glcSave.mat are also used and contains information from the previous run: | ||
C | Matrix with all rectangle centerpoints. | |
D | Vector with distances from centerpoint to the vertices. | |
F | Vector with function values. | |
G | Matrix with constraint values for each point. | |
Name | Name of the problem. Used for security if doing warm start. | |
Split | Split(i, j) is the number of splits along dimension i of rectangle j. | |
T | T (i) is the number of times rectangle i has been trisected. | |
fMinEQ | sum(abs(infeasibilities)) for minimum points, 0 if no equalities. | |
fMinIdx | Indices of the currently best points. | |
feasible | Flag indicating if a feasible point has been found. | |
glcfmin | Best function value found at a feasible point. | |
iL | iL(i, j) is the lower bound for rectangle j in integer dimension I (i). | |
iU | iU (i, j) is the upper bound for rectangle j in integer dimension I (i). | |
ignoreidx | Rectangles to be ignored in the rectangle selection procedure. | |
s | s(j) is the sum of observed rates of change for constraint j. | |
s_0 | s_0 is used as s(0). | |
t | t(i) is the total number of splits along dimension i. | |
SubRes | Additional output from nlp f, if suboptimization done. | |
optParam | Structure with special fields for optimization parameters, see Table 141 on page 229. | |
Fields used by glcSolve are: IterPrint, bTol, cTol, MaxIter (defaultmax(5000, n * 1000)), MaxFunc (default max(10000, n * 2000)), EpsGlob, fGoal, eps_f, eps_x. | ||
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. | |
glcSave.mat | Special file containing: | |
C | Matrix with all rectangle centerpoints. | |
D | Vector with distances from centerpoint to the vertices. | |
F | Vector with function values. | |
G | Matrix with constraint values for each point. | |
Name | Name of the problem. Used for security if doing warm start. | |
Split | Split(i, j) is the number of splits along dimension i of rectangle j. | |
T | T (i) is the number of times rectangle i has been trisected. | |
fMinEQ | sum(abs(infeasibilities)) for minimum points, 0 if no equalities. | |
fMinIdx | Indices of the currently best points. | |
feasible | Flag indicating if a feasible point has been found. | |
glcf min | Best function value found at a feasible point. | |
iL | iL(i, j) is the lower bound for rectangle j in integer dimension I (i). | |
iU | iU (i, j) is the upper bound for rectangle j in integer dimension I (i). | |
ignoreidx | Rectangles to be ignored in the rectangle selection procedure. | |
s | s(j) is the sum of observed rates of change for constraint j. | |
s_0 | s_0 is used as s(0). | |
t | t(i) is the total number of splits along dimension i. | |
Iter | Number of iterations. | |
FuncEv | Number function evaluations. | |
maxTri | Maximum size of any triangle. | |
ExitText | Text string giving ExitFlag and Inform information. | |
ExitFlag | 0 - Reached maxFunc or maxIter. | |
2 - Some upper bounds below lower bounds. | ||
7 - Reached maxFunc or maxIter, NOT feasible. | ||
8 - Empty domain for integer variables. | ||
Inform | 1 = Function value f is less than fGoal. 2 = Absolute function value f is less than fTol, only if fGoal = 0 or Relative error in function value f is less than fTol, i.e. abs(f-fGoal)/abs(fGoal) <= fTol. 3 = Maximum number of iterations done. 4 = Maximum number of function evaluations done. 9 = Max CPU Time reached. 91= Infeasible. 99= Input error, see ExitFlag. |
Description
The routine glcSolve 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 glcSolve 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 glcSolve with the final status of all parameters from the previous run, a so called warm start Assume that a run has been made with glcSolve 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 glcSolve a flag Prob.WarmStart should be set to one. Then glcSolve 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
infLinSolve
Purpose
Finds a linearly constrained minimax solution of a function of several variables with the use of any suitable TOMLAB solver. The decision variables may be binary or integer.
infLinSolve solves problems of the type:
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 \begin{array}{cccccc} \min\limits_x & \multicolumn{5}{l}{\max Dx} \\\mbox{subject to} & x_L & \leq & x & \leq & x_U \\& b_L & \leq & Ax & \leq & b_U \\\end{array} }
where 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 $x,x_L,x_U \in \Rdim{n}$}
, 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 \Rdim{m_1}$}
, 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 $A \in\Rdim{m_1 \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 $D \in \Rdim{m_2 \times n}$}
. The variables 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 $x \in I$}
, the index subset of 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 $1,...,n$}
are restricted to be integers. The different objectives are stored in D row-wise.
Calling Syntax
Result=infLinSolve(Prob,PriLev)
Description of Inputs
Prob | Structure Prob. Prob must be defined. Best is to use Prob = lp/mipAssign(.....), if using the TQ format. Prob.QP.D matrix should then be set to the rows (Prob.QP.c ignored). | |
PriLev | Print level in infLinSolve. | |
= 0 Silent except for error messages. | ||
> 0 Print summary information about problem transformation. | ||
Calls PrintResult with specified PriLev. | ||
= 2 Standard output from PrintResult (default). | ||
Extra fields used in Prob: | ||
SolverInf | Name of the TOMLAB solver. Valid names are: cplex, minos, snopt, xa and more. SeeSolverList('lp'); or SolverList('mip'); | |
QP.D | The rows with the different objectives. | |
f_Low | Lower bound on the objective (optional). | |
f_Upp | Upper bound on the objective (optional). |
Description of Outputs
Result | Structure with results from optimization. Output depends on the solver used. | |
The fields x_k, f_k, x_0, xState, bState, v_k are transformed back to match the original problem. | ||
The output in Result.Prob is the result after infLinSolve transformed the problem, i.e. the altered Prob structure |
Description
The linear minimax problem is solved in infLinSolve by rewriting the problem as a linear optimization problem. One additional variable 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 $z\in \MATHSET{R}$} , stored as 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 $x_{n+1}$} is added and the problem is rewritten as:
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 \begin{array}{cccccc} \multicolumn{6}{l}{\min\limits_x z}\\ \\\mbox{subject to} & x_L & \leq & (x_1,x_2,\ldots,x_n)^T & \leq & x_U \\& -\infty & \leq & z & \leq & \infty \\& b_L & \leq & A x &\leq & b_U \\& -\infty & \leq & D x - z e & \leq & 0 \\ \end{array} }
where 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 $e \in \Rdim{N},\; e(i)=1 \ \forall i$}
.
To handle cases where a row in D\*x is taken the absolute value of: minmax\|D * x\|, expand the problem with extra residuals with the opposite sign: \[D * x; -D * x\].
See Also
lpAssign.
infSolve
Purpose
Find a constrained minimax solution with the use of any suitable TOMLAB solver.
infSolve solves problems of the type:
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 \begin{array}{cccccc} \min\limits_x & \multicolumn{5}{l}{\max r(x)} \\\mbox{subject to} & x_L & \leq & x & \leq & x_U \\& b_L & \leq & Ax & \leq & b_U \\& c_L & \leq & c(x) & \leq & c_U \\ \end{array} }
where 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 $x,x_L,x_U \in \Rdim{n}$} , 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 $r(x) \in \Rdim{N}$} , 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 $c(x),c_L,c_U \in\Rdim{m_1}$} , 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 \Rdim{m_2}$} 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 $A \in \Rdim{m_2 \times n}$} .
Calling Syntax
Result=infSolve(Prob,PriLev)
Description of Inputs
Prob | Problem description structure. Should be created in the cls format. infSolve uses two special fields in Prob: | |
SolverInf | Name of solver used to solve the transformed problem. | |
Valid choices are conSolve, nlpSolve, sTrustr and clsSolve. | ||
If TOMLAB /SOL is installed: minos, snopt, npopt. | ||
InfType | 1 - constrained formulation (default). | |
2 - LS penalty approach (experimental). | ||
The remaining fields of Prob should be defined as required by the selected subsolver. | ||
PriLev | Print level in infSolve. | |
= 0 Silent except for error messages. | ||
> 0 Print summary information about problem transformation. | ||
Calls PrintResult with specified PriLev. | ||
= 2Standard output from PrintResult (default). |
Description of Outputs
Result | Structure with results from optimization. Output depends on the solver used. | |
The fields x_k, r_k, J_k, c_k, cJac, x_0, xState, cState, v_k are transformed back to match the original problem. | ||
g_k is calculated as 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 \VAR{J\_k} 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 $^T$} 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 }} 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 $\cdot$} 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 \VAR{r\_k}} . | ||
The output in Result.Prob is the result after infSolve transformed the problem, i.e. the altered Prob structure |
Description
The minimax problem is solved in infSolve by rewriting the problem as a general constrained optimization problem. One additional variable 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 $z\in \MATHSET{R}$} , stored as 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 $x_{n+1}$} is added and the problem is rewritten as:
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 \begin{array}{cccccc} \multicolumn{6}{l}{\min\limits_x z}\\\\\mbox{subject to} & x_L & \leq & (x_1,x_2,\ldots,x_n)^T & \leq & x_U \\& -\infty & \leq & z & \leq & \infty \\& b_L & \leq & A x & \leq & b_U \\& c_L & \leq & c(x) & \leq & c_U \\& -\infty & \leq & r(x) - z e & \leq & 0 \\\end{array} }
where 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 $e \in \Rdim{N},\; e(i)=1 \ \forall i$}
.
To handle cases where an element 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 $r_i(x)$} in 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 $r(x)$} appears in absolute value: 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 $\min \max |r_i(x)|$} , expand the problem with extra residuals with the opposite sign: 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 $ [ r_i(x); -r_i(x) ] $}
Examples
minimaxDemo.m.
See Also
clsAssign.
linRatSolve
Purpose
Finds a linearly constrained solution of a function of the ratio of two linear functions with the use of any suitable TOMLAB solver. Binary and integer variables are not supported.
linRatSolve solves problems of the type:
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 \begin{array}{cccccc} \min\limits_x & \multicolumn{5}{l}{ \Large (c1 x) \over (c2 x) } \\\mbox{subject to} & x_L & \leq & x & \leq & x_U \\& b_L & \leq & Ax & \leq & b_U \\ \end{array} }
where 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 $c1,c2,x,x_L,x_U \in \Rdim{n}$} , 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 \Rdim{m_1}$} 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 $A \in \Rdim{m_1 \times n}$} .
Calling Syntax
Result=linRatSolve(Prob,PriLev)
Description of Inputs
Prob | Structure Prob. Prob must be defined. Best is to use Prob = lpAssign(.....), if using the TQ format. Prob.QP.c1/c2 matrices should then be set (Prob.QP.c ignored). | |
PriLev | Print level in linRatSolve. | |
= 0Silent except for error messages. | ||
> 0 Print summary information about problem transformation. | ||
Calls PrintResult with specified PriLev. | ||
= 2 Standard output from PrintResult (default). | ||
Extra fields used in Prob: | ||
SolverRat | Name of the TOMLAB solver. Valid names are: cplex, minos, snopt, xa and more. See SolverList('lp'); | |
QP.c1 | The numerator in the objective. | |
QP.c2 | The denominator in the objective. | |
z1_L | Lower bound for z1 (default 1e-5). See description below |
Description of Outputs
Result | Structure with results from optimization. Output depends on the solver used. |
The fields x_k, f_k, x_0, xState, bState, v_k are transformed back to match the original problem. | |
The output in Result.Prob is the result after linRatSolve transformed the problem, i.e. the altered Prob structure |
Description
The linear ratio problem is solved by linRatSolve by rewriting the problem as a linear constrained optimization problem. n+1 variables z1 and z2(2:n+1) are needed, stored as x(1:n+1). The n original variables are removed so one more variable exists in the final problem.
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 \begin{array}{ccc} \\ z1 & = & 1 / (c2 x) \\ z2 & = & x z1 \\ z1 (c1 x) & = & (c1 z1 x) = c1 z2\\ \end{array} }
The problem then becomes:
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 \begin{array}{cccccc} \multicolumn{6}{l}{\min\limits_x c1 z2}\\\\\mbox{subject to} & z1_L & \leq & z1 & \leq & \infty \\& 1 & \leq & c2 z2 & \leq & 1 \\& 0 & \leq & A z2 - z1 beq & \leq & 0 \\& -\infty & \leq & A z2 - z1 b_U & \leq & 0 \\& -\infty & \leq & - A z2 + z1 b_L & \leq & 0 \\\\& 0 & \leq & A1 z2 - z1 xeq & \leq & 0 \\& -\infty & \leq & A1 z2 - z1 x_U & \leq & 0 \\& -\infty & \leq & - A1 z2 + z1 x_L & \leq & 0 \\ \end{array} }
where 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 $A1 \in \Rdim{N},\; A1=speye(N)$} .
OBSERVE the denominator c2x must always be positive. It is normally a good a idea to run the problem with both signs (multiply each side by -1).
See Also
lpAssign.
lpSimplex
Purpose
Solve general linear programming problems.
lpSimplex solves problems of the form
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 \begin{array}{cccccl} \min\limits_{x} & f(x) & = & c^{T}x & & \\s/t & x_{L} & \leq & x & \leq & x_{U} \\& b_{L} & \leq & Ax & \leq & b_{U} \\ \end{array} }
where 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 $x,x_{L},x_{U}\in \MATHSET{R} ^{n}$}
, 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 $c \in \MATHSET{R}^{n}$}
, 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 $A\in \MATHSET{R}^{m\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}$}
.
Calling Syntax
Result = lpSimplex(Prob) or
Result = tomRun('lpSimplex', Prob, 1);
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
QP.c | Constant vector. | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
Solver.Alg | Variable selection rule to be used: | |
0: Minimum reduced cost. | ||
1: Bland's rule (default). | ||
2: Minimum reduced cost. Dantzig's rule. | ||
QP.B | Active set B 0 at start: | |
B(i) = 1: Include variable x(i) is in basic set. | ||
B(i) = 0: Variable x(i) is set on its lower bound. | ||
B(i) = -1: Variable x(i) is set on its upper bound. | ||
optParam | Structure with special fields for optimization parameters, see Table 141. | |
Fields used are: MaxIter, PriLev, wait, eps_f, eps_Rank, xTol and bTol. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
x_k | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum, c. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in Table 150. | |
ExitFlag | 0: Optimal solution found. | |
1: Maximal number of iterations reached. | ||
2: Unbounded feasible region. | ||
5: Too many active variables in given initial point. | ||
6: No feasible point found with Phase 1. | ||
10: Errors in input parameters. | ||
11: Illegal initial x as input. | ||
Inform | If ExitF lag > 0, I nf orm = ExitF lag. | |
QP.B | Optimal active set. See input variable QP.B. | |
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Iter | Number of iterations. | |
FuncEv | Number of function evaluations. Equal to Iter. ConstrEv Number of constraint evaluations. Equal to Iter. | |
Prob | Problem structure used. |
Description
The routine lpSimplex implements an active set strategy (Simplex method) for Linear Programming using an additional set of slack variables for the linear constraints. If the given starting point is not feasible then a Phase I objective is used until a feasible point is found.
M-files Used
ResultDef.m
See Also
qpSolve
L1Solve
Purpose
Find a constrained L1 solution of a function of several variables with the use of any suitable nonlinear TOMLAB solver.
L1Solve solves problems of the type:
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 \begin{array}{cccccc} \min\limits_x & \multicolumn{5}{l}{\sum_i |r_i(x)|} \\\mbox{subject to} & x_L & \leq & x & \leq & x_U \\{} & b_L & \leq & Ax & \leq & b_U \\{} & c_L & \leq & c(x) & \leq & c_U \\ \end{array} }
where 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 $x,x_L,x_U \in \Rdim{n}$}
, 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 $r(x) \in \Rdim{N}$}
, 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 $c(x),c_L,c_U\in \Rdim{m_1}$}
, 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 \Rdim{m_2}$}
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 $A\in \Rdim{m_2 \times n}$}
.
Calling Syntax
Result = L1Solve(Prob,PriLev)
Description of Inputs
Prob | Problem description structure. Prob should be created in the cls constrained nonlinear format. | |
L1Solve uses one special field in Prob: | ||
SolverL1 | Name of the TOMLAB solver used to solve the augmented general nonlinear problem generated by L1Solve. | |
Any other fields are passed along to the solver specified by Prob.SolverL1. In particular: | ||
A | Linear constraint matrix. | |
b_L | Lower bounds on variables. | |
b_U | Upper bounds on variables. | |
c_L | Lower bounds for nonlinear constraints. | |
c_U | Upper bounds for nonlinear constraints.. | |
x_L | Lower bounds on variables. | |
x_U | Upper bounds on variables. | |
x_0 | Starting point. | |
ConsPattern | Nonzero patterns of constraint and residual Jacobians. | |
JacPattern | Prob.LS.y must have the correct residual length if JacPattern is empty but ConsPattern is not. | |
L1Solve will create the new patterns for the sub-solver using the information supplied in these two fields. | ||
PriLev | Print level in L1Solve. | |
= 0 | silent except for error messages. | |
> 0 | print summary information about problem transformation. | |
Calls PrintResult with specified PriLev. | ||
= 2 | standard output from PrintResult. |
Description of Outputs
Result | Structure with results from optimization. Fields changed depends on which solver was used for the extended problem. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The fields x_k, r_k, J_k, c_k, cJac, x_0, xState, cState, v_k, are transformed back to the format of the original L1 problem. g k is calculated as 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 {J\_k}
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 $^T$}
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 }}
· r k. The returned problem structure Result.Prob is the result after L1Solve transformed the problem, i.e. the altered Prob structure.
Description L1Solve solves the L1 problem by reformulating it as the general constrained optimization problem
See Also infSolve
MILPSOLVEPurpose Solve mixed integer linear programming problems (MILP). MILPSOLVE solves problems of the form
Calling Syntax Result = tomRun('MILPSOLVE',Prob, 1); or Prob = ProbCheck(Prob, 'MILPSOLVE'); Result = milpsolveTL(Prob); PrintResult(Result,1); Description of Inputs
Description of Outputs
minlpSolvePurpose Branch & Bound algorithm for Mixed-Integer Nonlinear Programming (MINLP) with convex or nonconvex sub problems using NLP relaxation (Formulated as minlp-IP). The parameter Convex (see below) determines if to assume the NLP subproblems are convex or not. minlpSolve depends on a suitable NLP solver. minlpSolve solves problems of the form
Calling Syntax Result = tomRun('minlpSolve',Prob,...) Description of Inputs
Description of Outputs
Description To make a restart (warm start), just set the warm start flag, and call minlpSolve once again: Prob.WarmStart = 1; Result = tomRun('minlpSolve', Prob, 2); minlpSolve will read warm start information from the minlpSolveSave.mat file. Another warm start (with same MaxFunc) is made by just calling tomRun again: Result = tomRun('minlpSolve', Prob, 2); To make a restart from the warm start information in the Result structure, make a call to WarmDefGLOBAL before calling minlpSolve. WarmDefGLOBAL moves information from the Result structure to the Prob structure and sets the warm start flag, Prob.WarmStart = 1; Prob = WarmDefGLOBAL('minlpSolve', Prob, Result); where Result is the result structure returned by the previous run. A warm start (with same MaxIter) is done by just calling tomRun again: Result = tomRun('minlpSolve', Prob, 2); To make another warm start with new MaxIter 100, say, redefine MaxIter as: Prob.optParam.MaxIter = 100; Then repeat the two lines: Prob = WarmDefGLOBAL('minlpSolve', Prob, Result); Result = tomRun('minlpSolve', Prob, 2); mipSolvePurpose Solve mixed integer linear programming problems (MIP). mipSolve solves problems of the form
Starting with TOMLAB version 4.0, mipSolve accepts upper and lower bounds on the linear constraints like most other TOMLAB solvers. Thus it is no longer necessary to use slack variables to handle inequality constraints. Calling Syntax Result = tomRun('mipSolve',Prob,...) Description of Inputs
Description of Outputs
Description The routine mipSolve is an implementation of a branch and bound algorithm from Nemhauser and Wolsey \[58, chap. 8.2\]. mipSolve normally uses the linear programming routines lpSimplex and DualSolve to solve relaxed subproblems. mipSolve calls the general interface routines SolveLP and SolveDLP. By changing the setting of the structure fields Prob.Solver.SolverLP and Prob.Solver.SolverDLP, different sub-solvers are possible to use, see the help for the interface routines. Algorithm See \[58, chap. 8.2\] and the code in mipSolve.m. Examples See exip39, exknap, expkorv. M-files Used lpSimplex.m, DualSolve.m, GetSolver.m, tomSolve.m See Also cutplane, balas, SolveLP, SolveDLP multiMinPurpose multiMin solves general constrained mixed-integer global optimization problems. It tries to find all local minima by a multi-start method using a suitable nonlinear programming subsolver. multiMin solves problems of the form
where 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 x,x_{L},x_{U}\in \MATHSET{R}^{n}} , 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 c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}} , 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 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}}} . The variables 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 x \in I} , the index subset of 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 1,...,n} are restricted to be integers. The integer components of every x_0 is rounded to the nearest integer value inside simple bounds, and these components are fixed during the nonlinear local search. If generating random points and there are linear constraints, multiMin checks feasibility with respect to the linear constraints, and for each initial point tries 100 times to get linear feasibility before accepting the initial point. Calling Syntax Result = multiMin(Prob, xInit) Result = tomRun('multiMin', Prob, PriLev) (driver call) Description of Inputs 3 = tomRun (PrintResult) output from every optimization, print level 1.
Description of Outputs
multiMINLPPurpose multiMINLP solves general constrained mixed-integer global nonlinear optimization problems. It is aimed for problems where the number of integer combinations nMax is huge and relaxation of the integer constraint is possible. If no integer variables, multiMINLP calls multiMin. If nMax <= min(Prob.optParam.MaxFunc,5000), glcDirect is used. Otherwise, multiMINLP first finds a set M of local minima calling multiMin with no integer restriction on any variable. The best local minimum is selected. glcDirect is called to find the best integer feasible solution fIP in a small area (< +- 2 units) around the best local minimum found. The other local minima are pruned, if fOpt(i) > fIP, no integer feasible solution could be found close to this local minimum i. The area close to the remaining candidate local minima are searched one by one by calling glcDirect to find any fIPi < fIP. multiMINLP solves problems of the form
where 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 x,x_{L},x_{U}\in \MATHSET{R}^{n}} , 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 c(x),c_{L},c_{U}\in \MATHSET{R}^{m_{1}}} , 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 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}}} . The variables 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 x \in I} , the index subset of 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 1,...,n} are restricted to be integers. Calling Syntax Result = tomRun('multiMINLP',Prob,...) Description of Inputs
Description of Outputs
nlpSolvePurpose Solve general constrained nonlinear optimization problems. nlpSolve solves problems of the form
Calling Syntax Result = nlpSolve(Prob, varargin) Result = tomRun('nlpSolve', Prob); Description of Inputs
Description of Outputs
Description The routine nlpSolve implements the Filter SQP by Roger Fletcher and Sven Leyffer presented in the paper \[21\]. M-files Used tomSolve.m, ProbCheck.m, iniSolve.m, endSolve.m See Also conSolve, sTrustr pdcoTLPurpose pdcoTL solves linearly constrained convex nonlinear optimization problems of the kind
Calling Syntax Result=tomRun('pdco',Prob,...); Description of Inputs
Description of Outputs
Description pdco implements an primal-dual barrier method developed at Stanford Systems Optimization Laboratory (SOL). The problem (19) is first reformulated into SOL PDCO form:
In particular, 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 d_2} indicates the accuracy required for satisfying each row of 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 Ax=b} . See pdco for a detailed discussion of 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 D_1} 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 D_2} . Note that in pdco, the objective 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 f(x)} is denoted 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 \phi(x)} , 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 bl == x\_L} 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 bu == x\_U} . Examples Problem 14 and 15 in tomlab/testprob/con prob.m.m are good examples of the use of pdcoTL. M-files Used pdcoSet.m, pdco.m, Tlsqrmat.m See Also pdscoTL.m pdscoTLPurpose pdscoTL solves linearly constrained convex nonlinear optimization problems of the kind
where 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 f(x)} is a convex separable nonlinear function, 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 x,x_L,x_U \in \RR^n} , 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 A\in \RR^{m \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\RR^m} . Calling Syntax Result=tomRun('pdsco',Prob,...); Description of Inputs
Description of Outputs
Description pdsco implements an primal-dual barrier method developed at Stanford Systems Optimization Laboratory (SOL). The problem (20) is first reformulated into SOL PDSCO form:
With positive 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 \gamma,\delta} the primal-dual solution 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 (x,y,z)} is bounded and unique. See pdsco for a detailed discussion of </math>\gamma</math> 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 \delta} . Note that in pdsco, the objective 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 f(x)} is denoted 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 \phi(x)} , 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 bl == x\_L} 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 bu == x\_U} . Examples Problem 14 and 15 in tomlab/testprob/con prob.m are good examples of the use of pdscoTL. M-files Used pdscoSet.m, pdsco.m, Tlsqrmat.m See Also pdcoTL.m qpSolvePurpose Solve general quadratic programming problems. qpSolve solves problems of the form
Calling Syntax Result = qpSolve(Prob) or Result = tomRun('qpSolve', Prob, 1); Description of Inputs
Description of Outputs
Description Implements an active set strategy for Quadratic Programming. For negative definite problems it computes eigen- values and is using directions of negative curvature to proceed. To find an initial feasible point the Phase 1 LP problem is solved calling lpSimplex. The routine is the standard QP solver used by nlpSolve, sTrustr and conSolve. M-files Used ResultDef.m, lpSimplex.m, tomSolve.m, iniSolve.m, endSolve.m See Also qpBiggs, qpe, qplm, nlpSolve, sTrustr and conSolve slsSolvePurpose Find a Sparse Least Squares (sls) solution to a constrained least squares problem with the use of any suitable TOMLAB NLP solver. slsSolve solves problems of the type:
The use of slsSolve is mainly for large, sparse problems, where the structure in the Jacobians of the residuals and the nonlinear constraints are utilized by a sparse NLP solver, e.g. SNOPT. Calling Syntax Result=slsSolve(Prob,PriLev) Description of Inputs
Description of Outputs
Description The constrained least squares problem is solved in slsSolve by rewriting the problem as a general constrained optimization problem. A set of m (the number of residuals) extra variables 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 z=(z_1,z_2,\ldots,z_m)} are added at the end of the vector of unknowns. The reformulated problem
Examples slsDemo.m M-files Used iniSolve.m, GetSolver.m sTrustrPurpose Solve optimization problems constrained by a convex feasible region. sTrustr solves problems of the form
Calling Syntax Result = sTrustr(Prob, varargin) Description of Inputs
Description of Outputs
Description The routine sTrustr is a solver for general constrained optimization, which uses a structural trust region algorithm combined with an initial trust region radius algorithm (itrr). The feasible region defined by the constraints must be convex. The code is based on the algorithms in \[13\] and \[67\]. BFGS or DFP is used for the Quasi-Newton update, if the analytical Hessian is not used. sTrustr calls internal routine itrr. M-files Used qpSolve.m, tomSolve.m, iniSolve.m, endSolve.m See Also conSolve, nlpSolve, clsSolve TfminPurpose Minimize function of one variable. Find miniumum x in [x_L, x_U] for function Func within tolerance xTol. Solves using Brents minimization algorithm. Reference: "Computer Methods for Mathematical Computations", Forsythe, Malcolm, and Moler, Prentice-Hall, 1976.
[x, nFunc] = Tfmin(Func, x_L, x_U, xTol, Prob) Description of Inputs
Description of Outputs
TfzeroPurpose Tfzero, TOMLAB fzero routine. Tfzero, TOMLAB fzero routine.\\ \\Find a zero for 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 f(x)} in the interval 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 [x_L, x_U]} . Tfzero searches for a zero of a function 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 f(x)} between the given scalar values 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 x_L} 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 x_U} until the width of the interval (xLow, xUpp) has collapsed to within a tolerance specified by the stopping criterion, 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 abs(xLow-xUpp) <= 2.*(RelErr*abs(xLow)+AbsErr)} . The method used is an efficient combination of bisection and the secant rule and is due to T. J. Dekker. Calling Syntax [xLow, xUpp, ExitFlag] = Tfzero(x L, x U, Prob, x 0, RelErr, AbsErr) Description of Inputs
Description of Outputs
ucSolvePurpose Solve unconstrained nonlinear optimization problems with simple bounds on the variables. ucSolve solves problems of the form
Calling Syntax Result = ucSolve(Prob, varargin) Description of Inputs
Description of Outputs
Description The solver ucSolve includes several of the most popular search step methods for unconstrained optimization. The search step methods included in ucSolve are: the Newton method, the quasi-Newton BFGS and DFP methods, the Fletcher-Reeves and Polak-Ribiere conjugate-gradient method, and the Fletcher conjugate descent method. The quasi-Newton methods may either update the inverse Hessian (standard) or the Hessian itself. The Newton method and the quasi-Newton methods updating the Hessian are using a subspace minimization technique to handle rank problems, see Lindstr¨om \[53\]. The quasi-Newton algorithms also use safe guarding techniques to avoid rank problem in the updated matrix. The line search algorithm in the routine LineSearch is a modified version of an algorithm by Fletcher \[20\]. Bound constraints are treated as described in Gill, Murray and Wright \[28\]. The accuracy in the line search is critical for the performance of quasi-Newton BFGS and DFP methods and for the CG methods. If the accuracy parameter Prob.LineParam.sigma is set to the default value 0.9, ucSolve changes it automatically according to:
M-files Used ResultDef.m, LineSearch.m, iniSolve.m, tomSolve.m, endSolve.m See Also clsSolve c Additional solversDocumentation for the following solvers is only available at http://tomopt.com and in the m-file help.
|