TOMLAB Solver Reference: Difference between revisions
Line 99: | Line 99: | ||
*[[L1Solve]] | *[[L1Solve]] | ||
==== | ==MilpSolve== | ||
Solve mixed integer linear programming problems (MILP). | Solve mixed integer linear programming problems (MILP). | ||
*[[MilpSolve]] | |||
====minlpSolve==== | ====minlpSolve==== |
Revision as of 05:47, 11 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
Solve linear programming problems when a dual feasible solution is available.
expSolve
Solve exponential fitting problems for given number of terms p.
glbDirect
Solve box-bounded global optimization problems.
glbSolve
Solve box-bounded global optimization problems.
glcCluster
Solve general constrained mixed-integer global optimization problems using a hybrid algorithm.
glcDirect
Solve global mixed-integer nonlinear programming problems.
glcSolve
Solve general constrained mixed-integer global optimization problems.
infLinSolve
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.
infSolve
Find a constrained minimax solution with the use of any suitable TOMLAB solver.
linRatSolve
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.
lpSimplex
Solve general linear programming problems.
L1Solve
Find a constrained L1 solution of a function of several variables with the use of any suitable nonlinear TOMLAB solver.
MilpSolve
Solve mixed integer linear programming problems (MILP).
minlpSolve
Purpose
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
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}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \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 (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 , the
index subset of are restricted to be integers.
Calling Syntax
Result = tomRun('minlpSolve',Prob,...)
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
x_L | Lower bounds on x. | |
x_U | Upper bounds on x. | |
A | The linear constraint matrix. | |
b_L | Lower bounds on linear constraints. | |
b_U | Upper bounds on linear constraints. | |
c_L | Lower bounds on nonlinear constraints. | |
c_U | Upper bounds on nonlinear constraints. | |
x_0 | Starting point. | |
Convex | If Convex==1, assume NLP problems are convex, and only one local NLP solver call is used at each node. If Convex==0 (Default), multiMin is used to do many calls to a local solver to determine the global minima at each node. The global minimum with most components integer valued is chosen. | |
MaxCPU | Maximal CPU Time (in seconds) to be used by minlpSolve, stops with best point found | |
PriLev | Print level in minlpSolve (default 1). Also see optParam.IterPrint | |
PriLevOpt | Print level in sub solvers (SNOPT and other NLP solvers): | |
=0 No output; >0 Convergence results | ||
>1 Output every iteration, >2 Output each step in the NLP alg | ||
For other NLP solvers, see the documentation for the solver | ||
WarmStart | If true, >0, minlpSolve reads the output from the last run from Prob.minlpSolve, if it exists. If it doesn't exist, minlpSolve attempts to open and read warm start data from mat-file minlpSolveSave.mat. minlpSolve uses the warm start information to continue from the last run. The mat-file minlp- SolveSave.mat is saved every Prob.MIP.SaveFreq iteration. | |
SolverNLP | Name of the solver used for NLP subproblems. If empty, the default solver is found calling GetSolver('con',1); If TOMLAB /SOL installed, SNOPT is the default solver. If SolverNLP is a SOL solver (SNOPT, MINOS or NPSOL), the SOL.optPar and SOL.PrintFile is used: See help minosTL.m, npsolTL.m or snoptTL.m for how to set these parameters | |
RandState | If Convex == 0, RandState is sent to multiMin to initialize the random gen- erator. RandState is used as follows: | |
If > 0, rand('state',RandState) is set to initialize the pseudo-random generator | ||
if < 0, rand('state',sum(100\*clock)) is set to give a new set of random values each run | ||
if RandState == 0, rand('state',) is not called. Default RandState = -1 | ||
MIP | Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used: | |
IntVars | If empty, all variables are assumed non-integer. If islogical(IntVars) (=all el- ements are 0/1), then 1 = integer variable, 0 = continuous variable. If any element >1, IntVars is the indices for integer variables. | |
VarWeight | Weight for each variable in the variable selection phase. A lower value gives higher priority. Setting Prob.MIP.VarWeight might improve convergence. | |
DualGap | minlpSolve stops if the duality gap is less than DualGap. DualGap = 1, stop at first integer solution e.g. DualGap = 0.01, stop if solution < 1% from optimal solution. | |
fIP | An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. Used even if xIP not given. | |
xIP | The x-values giving the fIP value, if a solution (xIP,fIP) is known. | |
NodeSel | Node selection method in branch and bound | |
= 0 Depth First. Priority on nodes with more integer components | ||
= 1 Breadth First. Priority on nodes with more integer components | ||
= 2 Depth First. When integer solution found, use NodeSel = 1 (default) | ||
= 3 Pure LIFO (Last in, first out) Depth First | ||
= 4 Pure FIFO (First in, first out) Breadth First | ||
= 5 Pure LIFO Depth First. When integer solution found, use NodeSel 4 | ||
VarSel | Variable selection method in branch and bound: | |
= 1 Use variable with most fractional value | ||
= 2 Use gradient and distance to nearest integer value | ||
KNAPSACK | If = 1, use a knapsack heuristic. Default 0. | |
ROUNDH | If = 1, use a rounding heuristic. Default 0. | |
SaveFreq | Warm start info saved on minlpSolveSave.mat every SaveFreq iteration (default -1, i.e. no warm start info is saved) | |
optParam | Structure in Prob. Fields used in Prob.optParam, also in sub solvers: | |
MaxIter | Maximal number of iterations, default 10000 | |
IterPrint | Print short information each iteration (PriLev > 0 ==> IterPrint = 1). Iter- ation number: Depth in tree (symbol L\[\] - empty list, symbol Gap - Dual Gap convergence), fNLP (Optimal f(x) current node), fIPMin (Best integer feasi- ble f(x) found), LowBnd (Lower bound on optimal integer feasible f(x)), Dual Gap in absolut value and percent, The length of the node list L, -L-, The Inform and ExitFlag the solver returned at the current node, FuEv (Number of function evaluations used by solver at current node), date/time stamp. | |
bTol | Linear constraint violation convergence tolerance. | |
cTol | Constraint violation convergence tolerance. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
Iter | Number of iterations. | |
ExitFlag | 0: Global optimal solution found, or integer solution with duality gap less than user tolerance. | |
1: Maximal number of iterations reached. | ||
2: Empty feasible set, no integer solution found. | ||
4: No feasible point found running NLP relaxation. | ||
5: Illegal x 0 found in NLP relaxation. | ||
99: Maximal CPU Time used (cputime > Prob.MaxCPU). | ||
Inform | Code telling type of convergence, returned from subsolver. | |
ExitText | Text string giving ExitFlag and Inform information. | |
DualGap | Relative duality gap, max(0,fIPMin-fLB)/-fIPMin-, if fIPMin =0; max(0,fIPMin-fLB) if fIPMin == 0. If fIPMin =0: Scale with 100, 100\*Dual- Gap, to get the percentage duality gap. For absolute value duality gap: scale with fIPMin, fIPMin \* DualGap | |
x_k | Solution. | |
v_k | Lagrange multipliers. Bounds, Linear and Nonlinear Constraints, n + mLin + mNonLin. | |
f_k | Function value at optimum. | |
g_k | Gradient vector at optimum. | |
x_0 | Starting point x 0. | |
f_0 | Function value at start. | |
c_k | Constraint values at optimum. | |
cJac | Constraint derivative values at optimum. | |
xState | State of each variable, described in Table 150. | |
bState | State of each constraint, described in Table 151. | |
cState | State of each general constraint, described in Table 152. | |
Solver | Solver used ('mipSolve'). | |
SolverAlgorithm | Text description of solver algorithm used. | |
Prob | Problem structure used. | |
minlpSolve | A structure with warm start information. Use with WarmDefGLOBAL, see example below. |
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);
mipSolve
Purpose
Solve mixed integer linear programming problems (MIP).
mipSolve solves problems of the form
Failed to parse (unknown function "\multicolumn"): {\displaystyle \begin{array}{cccccc} \min\limits_{x} & f(x) & = & c^{T}x & \\s/t & x_{L} & \leq & x & \leq & x_{U} \\& b_{L} & \leq & Ax & \leq & b_{U} \\ & & & \multicolumn{3}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \in $I$} \\ \end{array} }
where Failed to parse (unknown function "\MATHSET"): {\displaystyle c, x, x_L, x_U \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_L, b_U \in\MATHSET{R}^{m}}
.The variables , the index subset of are restricted to beintegers.
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
Prob | Problem description structure. The following fields are used: | |
c | The vector c in . | |
A | Constraint matrix for linear constraints. | |
b_L | Lower bounds on the linear constraints. If empty, Prob.b U is used. | |
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. | |
MaxCPU | Maximal CPU Time (in seconds) to be used by mipSolve, stops with best point found. | |
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. | ||
SolverLP | Name of solver used for initial LP subproblem. Default solver is used if empty, see GetSolver.m and tomSolve.m. | |
SolverDLP | Name of solver used for the dual LP subproblems. Default solver is used if empty, see GetSolver.m and tomSolve.m. | |
PriLevOpt | Print level in lpSimplex and DualSolve: | |
0: No output; > 0: Convergence result; | ||
> 1: Output every iteration; > 2: Output each step in simplex algorithm. | ||
PriLev | Print level in mipSolve. | |
SOL.optPar | Parameters for the SOL solvers, if they are used as subsolvers. | |
SOL.PrintFile | Name of print file for SOL solvers, if they are used as subsolvers. | |
MIP | Structure with fields for integer optimization The following fields are used: | |
IntVars | The set of integer variables. | |
If empty, all variables are assumed non-integer (LP problem) | ||
VarWeight | Weight for each variable in the variable selection phase. | |
A lower value gives higher priority. Setting Prob.MIP.VarWeight = Prob.c improves convergence for knapsack problems. | ||
DualGap | mipSolve stops if the duality gap is less than DualGap. To stop at the first found integer solution, set DualGap =1. For example, DualGap = 0.01 makes the algorithm stop if the solution is < 1% from the optimal solution. | |
fIP | An upper bound on the IP value wanted. Makes it possible to cut branches and avoid node computations. | |
xIP | The x-value giving the fIP value. | |
KNAPSACK | If solving a knapsack problem, set to true (1) to use a knapsack heuristic. | |
optParam | Structure with special fields for optimization parameters, see Table 141.Fields used are: IterPrint, MaxIter, PriLev, wait, eps f and eps Rank. | |
Solver | Structure with fields for algorithm choices: | |
Alg | Node selection method: | |
0: Depth first | ||
1: Breadth first | ||
2: Depth first. When integer solution found, switch to Breadth. | ||
method | Rule to select new variables in DualSolve/lpSimplex: | |
0: Minimum reduced cost, sort variables increasing. (Default) | ||
1: Bland's rule (default). | ||
2: Minimum reduced cost. Dantzig's rule. |
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, \[Constraints + lower + upper bounds\]. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in Table 150, page 239. | |
Inform | If ExitF lag > 0, I nf orm = ExitF lag. | |
QP.B | Optimal active set. See input variable QP.B. | |
QP.y | Dual parameters y (also part of Result.v_k. | |
p_dx | Search steps in x. | |
alphaV | Step lengths for each search step. | |
ExitFlag | 0: OK. | |
1: Maximal number of iterations reached. | ||
2: Empty feasible set, no integer solution found. | ||
3: Rank problems. Can not find any solution point. | ||
4: No feasible point found running LP relaxation. | ||
5: Illegalx_0 found in LP relaxation. | ||
99: Maximal CPU Time used (cputime > Prob.MaxCPU). | ||
Iter | Number of iterations. | |
Solver | Solver used ('mipSolve'). | |
SolverAlgorithm | Text description of solver algorithm used. | |
Prob | Problem structure used. |
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
multiMin
Purpose
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
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}}} .
The variables , the index subset of 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.Prob | Problem description structure. The following fields are used: | |
xInit | Either, 1x1 number - The number of random initial points, default 10\*Prob.N dxm matrix - Every column is an initial point (of length d=Prob.N). May also be set as Prob.xInit. | |
fCut | If initial f(x_0) > fCut, no local optimization is done. | |
WarmStart | If true, > 0, multiMin assumes the field multiMin defined with the output from a previous run on the same problem. See the Output fields of Result.multiMin. Use WarmDefGLOBAL to set the correct fields in the Prob structure. Nec- essary fields are fOpt and xOpt. If any of the other fields are missing, the corresponding variables are initialized to 0. These other fields are: localTry, Iter, FuncEv, GradEv, HessEv, ConstrEv Inform (is set to zeros(length(fOpt,1) if not defined). | |
In WarmDefGLOBAL the Result structure for the optimal run will be fed back to multiMin as Prob.multiMin.ResOpt In case this field is not defined, and no better point is found during the runs, a special call to the localSolver is used to generate a proper Result structure. | ||
RandState | If WarmStart and isscalar(xInit), RandState is used as follows: If > 0, rand('state',RandState) is set to initialize the pseudo-random generator if < 0, rand('state',sum(100\*clock)) is set to give a new set of random values each run if RandState == 0, rand('state',) is not called Default RandState = -1 | |
xEqTol | Tolerance to test if new point x_k already defined as optimum: norm(xk - xOpt(:, i)) <= xEqTol * max(1, norm(xk)) If test fulfilled x_k is assumed to be too close to xOpt(:,i) Default xEqTol = 1E-5 | |
x_L | Lower bounds for each element in x. If generating random points, -inf elements of x L are set to -10000. | |
x_U | Upper bounds for each element in x. If generating random points, inf elements of x U are set to 10000. | |
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. | |
PriLevOpt | 0 = silent. | |
1 = Display one row for each unique local minima found. The minima are sorted, lowest value first (possibly the global minima) | ||
The following 4 information values are displayed: | ||
1. Order \# | ||
2. Function value f(x) at local minima | ||
3. Point x at local minima. Only up to 10 values are displayed | ||
4. Inform value returned from local Solver (normally 0) | ||
2 = One row of output from each multiMin local optimization trial | ||
The following 6 information values are displayed: | ||
1. Step \# | ||
2. Text Old (previously found local minima), FAIL (solver failed to verify local minima) or blank (solver success, new local minima found) | ||
3. Inform value from local solver | ||
4. f(x_0) - function value f(x_0) for initial x_0 | ||
5. f(x) - best f(x) value found in this local search | ||
6. x - point for which best f(x) value was found in this local search. Only up to 10 values are displayed. | ||
4 = tomRun (PrintResult) output from every optimization, print level 2. For constrained problems output of sum(-constr-) and information if optimal point was accepted w.r.t. feasibility. | ||
5 = tomRun (PrintResult) output from every optimization, print level 3. | ||
GO | Structure in Prob, Prob.GO. Fields used: | |
localSolver | The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0). | |
optParam | Defines optimization parameters. Fields used: | |
fGoal | Goal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done. | |
eps_f | Relative accuracy for function value, fTol == eps_f. Stop if abs(f-fGoal) <= abs(fGoal) \* fTol , if fGoal = 0. Stop if abs(f-fGoal) <= fTol , if fGoal ==0. | |
bTol | The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0). | |
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: | |
The following fields in Result are changed by multiMin before return: | ||
ExitFlag | = 0 normal output, of if fGoal set and found. | |
= 1 A solution reaching the user defined fGoal was not found | ||
The Solver, SolverAlgorithm and ExitText fields are also reset. | ||
A special field in Result is also returned, Result.multiMin: | ||
xOpt | Prob.N x k matrix with k distinct local optima, the test being norm(xk -xOpt(:, i)) <= xEqT ol * max(1, norm(xk )) that if fulfilled assumes x k to be to closeto xOpt(:,i) | |
fOpt | The k function values in the local optima xOpt(:,i),i=1,...,k. | |
Inform | The Inform value returned by the local solver when finding each of the local optima xOpt(:,i); i=1,...,k. The Inform value can be used to judge the validity of the local minimum reported. | |
localTry | Total number of local searches. | |
Iter | Total number of iterations. | |
FuncEv | Total number of function evaluations. | |
GradEv | Total number of gradient evaluations. | |
HessEv | Total number of Hessian evaluations. | |
ConstrEv | Total number of constraint function evaluations. | |
ExitText | Text string giving ExitFlag and Inform information. |
multiMINLP
Purpose
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
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}{l}{x_{j} \in \MATHSET{N} \ \ \forall j \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}}} . The variables , the index subset of are restricted to be integers.
Calling Syntax
Result = tomRun('multiMINLP',Prob,...)
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
Prob is a structure, defined as to solve a standard MINLP problem. The Prob structure is fed to the localSolver. See e.g. minlpAssign. | ||
See multiMin and glcDirect for input to the subsolvers e.g. Prob.xInit is used in multiMin (and fCut, RandState, xEQTol). | ||
x_L | Lower bounds for each element in x. If generating random points, -inf elements of x L are set to min(-L,xMin,x U-L) xMin is the minimum of the finite x L values. | |
x_U | Upper bounds for each element in x. If generating random points, inf elements of x U are set to max(L,xMax,x L+L) xMax is the maximum of the finite x U values. | |
L is 100 for nonlinear least squares, otherwise 1000. | ||
b_L | Lower bounds on linear constraints. | |
b_U | Upper bounds on linear constraints. | |
A | The linear constraint matrix. | |
c_L | Lower bounds on nonlinear constraints. | |
c_U | Upper bounds on nonlinear constraints. | |
PriLev | Print Level: | |
0 = Silent | ||
1 = Display 2 summary rows | ||
2 = Display some extra summary rows | ||
5 = Print level 1 in tomRun call | ||
6 = Print level 2 in tomRun call | ||
7 = Print level 3 in tomRun call | ||
xInit | Used in multiMin. See help for multiMin. | |
GO.localSolver | The local solver used to run all local optimizations. Default is the license dependent output of GetSolver('con',1,0). | |
optParam | Structure in Prob, Prob.optParam. Defines optimization parameters. Fields used: | |
MaxFunc | Max number of function evaluations in each subproblem | |
fGoal | Goal for function value f(x), if empty not used. If fGoal is reached, no further local optimizations are done | |
eps_f | Relative accuracy for function value, fTol == eps_f. Stop if abs(f-fGoal) <= abs(fGoal) \* fTol , if fGoal = 0. Stop if abs(f-fGoal) <= fTol , if fGoal ==0. Default 1e-8. | |
bTol | Linear constraint feasibility tolerance. Default 1e-6 | |
cTol | Nonlinear constraint feasibility tolerance. Default 1e-6 | |
MIP | Structure in Prob, Prob.MIP. Defines integer optimization parameters. Fields used: | |
IntVars | If empty, all variables are assumed non-integer. If islogical(IntVars) (=all el- ements are 0/1), then 1 = integer variable, 0 = continuous variable. If any element >1, IntVars is the indices for integer variables. | |
nMax | Number of integer combinations possible, if empty multiMINLP computes nMax. | |
Rfac | Reduction factor for real variables in MINLP subproblem close to local multiMINLP minimum. Bounds set to x_L = max(x_L,x-Rfac\*(x_U-x_L)) and x_U= min(x_U,x+Rfac\*(x_U-x_L)). Default 0.25. |
Description of Outputs
Result | Structure with result from optimization. The following fields are changed: | |
Result structure from the last good optimization step giving the best f(x) value, the possible global MINLP minimum. | ||
The following fields in Result are changed by multiMINLP before return: | ||
ExitFlag | = 0 normal output, of if fGoal set and found. | |
= 1 A solution reaching the user defined fGoal was not found. | ||
= 2 Unbounded problem. | ||
=4 Infeasible problem. | ||
The Solver, SolverAlgorithm and ExitText fields are also reset. | ||
A special field in Result is also returned, Result.multiMINLP: | ||
xOpt | Prob.N x k matrix with k distinct local optima, the test being norm(x k- xOpt(:,i)) <= xEqTol\*max(1,norm(x k)) that if fulfilled assumes x_k to be to close to xOpt(:,i). | |
fOpt | The k function values in the local optima xOpt(:,i),i=1,...,k. | |
Inform | The Inform value returned by the local solver when finding each of the local optima xOpt(:,i); i=1,...,k. The Inform value can be used to judge the validity of the local minimum reported. | |
localTry | Total number of local searches. | |
Iter | Total number of iterations. | |
FuncEv | Total number of function evaluations. | |
GradEv | Total number of gradient evaluations. | |
HessEv | Total number of Hessian evaluations. | |
ConstrEv | Total number of constraint function evaluations. | |
ExitText | Text string giving Inform information. |
nlpSolve
Purpose
Solve general constrained nonlinear optimization problems.
nlpSolve 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 (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}}}
.
Calling Syntax
Result = nlpSolve(Prob, varargin)
Result = tomRun('nlpSolve', 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. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
PriLevOpt | Print level: 0 Silent, 1 Final result, 2 Each iteration, short, 3 Each iteration, more info, 4 Matrix update information. | |
FUNCS.f | Name of m-file computing the objective function f (x). | |
FUNCS.g | Name of m-file computing the gradient vector g(x). | |
FUNCS.H | Name of m-file computing the Hessian matrix H (x). | |
FUNCS.c | Name of m-file computing the vector of constraint functions c(x). | |
FUNCS.dc | Name of m-file computing the matrix of constraint normals ?c(x)/dx. | |
FUNCS.d2c | Name of m-file computing the second derivatives of the constraints, weighted by an input Lagrange vector | |
NumDiff | How to obtain derivatives (gradient, Hessian). | |
ConsDiff | How to obtain the constraint derivative matrix. | |
SolverQP | Name of the solver used for QP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m. | |
SolverFP | Name of the solver used for FP subproblems. If empty, the default solver is used. See GetSolver.m and tomSolve.m. | |
optParam | Structure with special fields for optimization parameters, see Table 141. | |
Fields used are: eps_g, eps_x, MaxIter, wait, size_x, method, IterPrint, xTol, bTol, cTol, and QN InitMatrix. | ||
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 | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum. | |
c_k | Value of constraints at optimum. | |
H_k | Hessian value at optimum. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
cJac | Constraint Jacobian at optimum. | |
xState | State of each variable, described in Table 150. | |
bState | State of each linear constraint, described in Table 151. | |
cState | State of each general constraint. | |
Inform | Type of convergence. | |
ExitFlag | Flag giving exit status. | |
ExitText | 0: Convergence. Small step. Constraints fulfilled. | |
1: Infeasible problem? | ||
2: Maximal number of iterations reached. | ||
3: No progress in either function value or constraint reduction. | ||
Inform | 1: Iteration points are close. | |
2: Small search direction | ||
3: Function value below given estimate. Restart with lower fLow if minimum not reached. | ||
4: Projected gradient small. | ||
10: Karush-Kuhn-Tucker conditions fulfilled. | ||
Iter | Number of iterations. | |
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Prob | Problem structure used. |
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
pdcoTL
Purpose
pdcoTL solves linearly constrained convex nonlinear optimization problems of the kind
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) \\ \mathrm{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 f(x)}
is a convex 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('pdco',Prob,...);
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
x_0 | Initial x vector, used if non-empty. | |
A | The linear constraint matrix. | |
b_L,b_U | Lower and upper bounds for the linear constraints. | |
PriLevOpt | Print level in pdsco solver. If > 0: prints summary information. | |
SOL | Structure with SOL special parameters: | |
pdco | Options structure with fields as defined by pdcoSet. | |
d1 | Primal regularization vector. Must be a positive vector (length n) or scalar, in which case D1 = diag(d1) is used. Default: 10-4 . | |
d2 | Dual regularization vector. Must be a positive vector (length m) or a scalar value, in which case D2 = diag(d2) is used. Default: 10-4 . | |
y0 | Initial dual parameters for linear constraints (default 0) | |
z0 | Initial dual parameters for simple bounds (default 1/N )
xsize,zsize are used to scale (x, y, z). Good estimates should improve the performance of the barrier method. | |
xsize | Estimate of the biggest x at the solution. (default 1/N ) | |
zsize | Estimate of the biggest z at the solution. (default 1/N ) | |
optParam | Structure with optimization parameters. The following fields are used: | |
MaxIter | Maximum number of iterations. (Prob.SOL.pdco.MaxIter). | |
MinorIter | Maximum number of iterations in LSQR (Prob.SOL.pdco.LSQRMaxIter). | |
eps_x | Accuracy for satisfying x1 . * z1 = 0, x2 .z1 = 0, where z = z1 - z2 and z1 , z2 > 0.(Prob.SOL.pdco.OptTol) | |
bTol | Accuracy for satisfying Ax + D2 r = b, AT y + z = ?f (x) and x - x1 = bL , x +x2 = bU , where x1 , x2 > 0 (Prob.SOL.pdco.FeaTol) | |
wait | 0 - solve the problem with default internal parameters; 1 - pause: allows interactive resetting of parameters. (Prob.SOL.pdco.wait) |
Description of Outputs
Result | Structure with result from optimization. The following fields are set by pdcoTL | |
x_k | Solution vector | |
f_k | Function value at optimum | |
g_k | Gradient of the function at the solution | |
H_k | Hessian of the function at the solution, diagonal only | |
x_0 | Initial solution vector | |
f_0 | Function value at start, x = x_0 | |
xState | State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; | |
bState | State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; | |
v_k | Lagrangian multipliers (orignal bounds + constraints ) | |
y_k | Lagrangian multipliers (for bounds + dual solution vector) The full \[z; y\] vec- tor as returned from pdco, including slacks and extra linear constraints after rewriting constraints: -inf < b L < A * x < b U < inf ; non-inf lower AND upper bounds | |
ExitFlag | Tomlab Exit status from pdco MEX | |
Inform | pdcoinformation parameter: 0 = Solution found; | |
0 | Solution found | |
1 | Too many iterations | |
2 | Linesearch failed too often | |
Iter | Number of iterations | |
FuncEv | Number of function evaluations | |
GradEv | Number of gradient evaluations | |
HessEv | Number of Hessian evaluations | |
Solver | Name of the solver ('pdco') | |
SolverAlgorithm | Description of the solver |
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:
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) \\ \mathrm{s/t} & x_L & \leq & x & \leq & x_U \\ {} & & & Ax & = & b \\ {} & \multicolumn{5}{l}{r \mathrm{\ unconstrained}} \\ \end{array} }
The problem actually solved by pdco is
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}{lllcll} \min\limits_{x,r} & \multicolumn{5}{l}{\phi(x) + \frac{1}{2}\|D_1 x\|^2 + \frac{1}{2}\|r\|^2 } \\ \\ \mathrm{s/t} & x_L & \leq & x & \leq & x_U \\ {} & Ax & + & D_{2}r & = & b \\ \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 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}
are positive-definite diagonal matrices defined from 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}
, 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}
given in Prob.SOL.d1 and Prob.SOL.d2.
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
pdscoTL
Purpose
pdscoTL solves linearly constrained convex nonlinear optimization problems of the kind
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) \\ \mathrm{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 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
Prob | Problem description structure. The following fields are used: | |
x_0 | Initial x vector, used if non-empty. | |
A | The linear constraints coefficient matrix. | |
b_L,b_U | Lower and upper bounds for the linear constraints. | |
HessPattern | Non-zero pattern for the objective function. Only the diagonal is needed. Default if empty is the unit matrix. | |
PriLevOpt | Print level in pdsco solver. If > 0: prints summary information. | |
SOL | Structure with SOL special parameters: | |
pdco | Options structure with fields as defined by pdscoSet. | |
gamma | Primal regularization parameter. | |
delta | Dual regularization parameter. | |
y0 | Initial dual parameters for linear constraints (default 0) | |
z0 | Initial dual parameters for simple bounds (default 1/N ) | |
xsize,zsize are used to scale (x, y, z). Good estimates should improve the performance of the barrier method. | ||
xsize | Estimate of the biggest x at the solution. (default 1/N ) | |
zsize | Estimate of the biggest z at the solution. (default 1/N ) | |
optParam | Structure with optimization parameters. The following fields are used: | |
MaxIter | Maximum number of iterations. (Prob.SOL.pdco.MaxIter). | |
MinorIter | Maximum number of iterations in LSQR (Prob.SOL.pdco.LSQRMaxIter). | |
eps_x | Accuracy for satisfying x. * z = 0 | |
bTol | Accuracy for satisfying Ax + r = b, AT y + z = ?f (x) and x - x1 = bL , x + x2 =bU, where x1 , x2 > 0. (Prob.SOL.pdco.FeaTol) | |
wait | 0 - solve the problem with default internal parameters; 1 - pause: allows interactive resetting of parameters. (Prob.SOL.pdco.wait) |
Description of Outputs
Result | Structure with result from optimization. The following fields are set by pdscoTL: | |
x_k | Solution vector | |
f_k | Function value at optimum | |
g_k | Gradient of the function at the solution | |
H_k | Hessian of the function at the solution, diagonal only | |
x_0 | Initial solution vector | |
f_0 | Function value at start, x = x_0 | |
xState | State of variables. Free == 0; On lower == 1; On upper == 2; Fixed == 3; | |
bState | State of linear constraints. Free == 0; Lower == 1; Upper == 2; Equality == 3; | |
v_k | Lagrangian multipliers (orignal bounds + constraints ) | |
y k | Lagrangian multipliers (for bounds + dual solution vector) The full \[z; y\] vec- tor as returned from pdsco, including slacks and extra linear constraints after rewriting constraints: -inf < b L < A * x < b U < inf ; non-inf lower AND upper bounds | |
ExitFlag | Tomlab Exit status from pdsco MEX | |
Inform | pdsco information parameter: 0 = Solution found; | |
0 | Solution found | |
1 | Too many iterations | |
2 | Linesearch failed too often | |
Iter | Number of iterations | |
FuncEv | Number of function evaluations | |
GradEv | Number of gradient evaluations | |
HessEv | Number of Hessian evaluations | |
Solver | Name of the solver ('pdsco') | |
SolverAlgorithm | Description of the solver |
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:
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}{clll} \min\limits_x & f(x) \\ \mathrm{s/t} & x & \geq & x_U \\ {} & Ax & = & b. \\ \end{array} }
The problem actually solved by pdsco is
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}{lllcll} \min\limits_{x,r} & \multicolumn{5}{l}{f(x) + \frac{1}{2}\|\gamma x\|^2 + \frac{1}{2}\|r / \delta \|^2 } \\ \\ \mathrm{s/t} & & & x & \geq & 0 \\ {} & Ax & + & r & = & b \\ {} & \multicolumn{5}{l}{r \mathrm{\ unconstrained}} \\ \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 \gamma}
is the primal regularization parameter, typically small but 0 is allowed. Furthermore, 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}
is the dual regularization parameter, typically small or 1; must be strictly greater than zero.
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
qpSolve
Purpose
Solve general quadratic programming problems.
qpSolve 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) & = & \frac{1}{2}(x)^{T}Fx + 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 F\in \MATHSET{R}^{n\times 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 = qpSolve(Prob) or
Result = tomRun('qpSolve', Prob, 1);
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
QP.F | Constant matrix, the Hessian. | |
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. | |
optParam | Structure with special fields for optimization parameters, see Table 141.Fields used are: eps f, eps Rank, MaxIter, wait, bTol and PriLev. |
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. | |
H_k | Hessian value at optimum. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in Table 150 . | |
Iter | Number of iterations. | |
ExitFlag | 0: OK, see Inform for type of convergence. | |
2: Can not find feasible starting point x_0. | ||
3: Rank problems. Can not find any solution point. | ||
4: Unbounded solution. | ||
10: Errors in input parameters. | ||
Inform | If ExitF lag > 0, I nf orm = ExitF lag, otherwise I nf orm show type of convergence: | |
0: Unconstrained solution. | ||
1: ? = 0. | ||
2: ? = 0. No second order Lagrange mult. estimate available. | ||
3: ? and 2nd order Lagr. mult. positive, problem is not negative definite. | ||
4: Negative definite problem. 2nd order Lagr. mult. positive, but releasing variables leads to the same working set. | ||
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Prob | Problem structure used. |
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
slsSolve
Purpose
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:
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 & \frac{1}{2}r(x)^T 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{m}}
, 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,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 c(x),c_L,c_U \in\Rdim{m_2}}
.
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
Prob | Problem description structure. Should be created in the cls format, preferably by callingProb=clsAssign(...) if using the TQ format. | |
slsSolve uses two special fields in Prob: | ||
SolverL2 | Text string with name of the NLP solver used for solving the reformulated problem. Valid choices are conSolve, nlpSolve, sTrustr, clsSolve. Suitable SOL solvers, if available: minos, snopt, npopt. | |
L2Type | Set to 1 for standard constrained formulation. Currently this is the only allowed choice. | |
All other fields should be set as expected by the nonlinear solver selected. In particular: | ||
A | Linear constraint matrix. | |
b_L | Lower bounds on the linear constraints. | |
b_U | Upper bounds on the linear constraints. | |
c_L | Upper bounds on the nonlinear constraints. | |
c_U | Lower bounds on the nonlinear constraints. | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
ConsPattern | The nonzero pattern of the constraint Jacobian. | |
JacPattern | The nonzero pattern of the residual Jacobian. | |
Note that Prob.LS.y must be of correct length if JacPattern is empty (but ConsPattern is not). slsSolve will create the new Prob.ConsPattern to be used by the nonlinear solver using the information in the supplied ConsPattern and JacPattern. | ||
PriLev | Print level in slsSolve. Default value is 2. | |
0 | Silent except for error messages. | |
> 1 | Print summary information about problem transformation. slsSolve calls Print- Result(Result,PriLev). | |
2 | Standard output in PrintResult. |
Description of Outputs
Result | Structure with results from optimization. The contents of Result depend on which nonlinear solver was used to solved | |
slsSolve transforms the following fields of Result back to the format of the original problem: | ||
x_k | Optimal point. | |
r_k | Residual at optimum. | |
J_k | Jacobian of residuals at optimum. | |
c_k | Nonlinear constraint vector at optimum. | |
v_k | Lagrange multipliers. | |
g_k | The gradient vector is calculated as J kT · r k. | |
cJac | Jacobian of nonlinear constraints at optimum. | |
x_0 | Starting point. | |
xState | State of variables at optimum. | |
cState | State of constraints at optimum. | |
Result.Prob | The problem structure defining the reformulated problem. |
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
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}{\frac{1}{2} z^T z} \\ \mbox{subject to} & x_L & \leq & (x_1,x_2,\ldots,x_n) & \leq & x_U \\ {} & b_L & \leq & Ax & \leq & b_U \\ {} & c_L & \leq & c(x) & \leq & c_U \\ {} & 0 & \leq & r(x) - z & \leq & 0 \\ \end{array} }
is then solved by the solver given by Prob.SolverL2.
Examples
slsDemo.m
M-files Used
iniSolve.m, GetSolver.m
sTrustr
Purpose
Solve optimization problems constrained by a convex feasible region.
sTrustr 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} \\ \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}}}
.
Calling Syntax
Result = sTrustr(Prob, varargin)
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 on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
FUNCS.f | Name of m-file computing the objective function f (x). | |
FUNCS.g | Name of m-file computing the gradient vector g(x). | |
FUNCS.H | Name of m-file computing the Hessian matrix H (x). | |
FUNCS.c | Name of m-file computing the vector of constraint functions c(x). | |
FUNCS.dc | Name of m-file computing the matrix of constraint normals ?c(x)/dx. | |
optParam | Structure with special fields for optimization parameters, see Table 141. | |
Fields used are: eps f, eps g, eps c, eps x, eps Rank, MaxIter, wait, size x, size f, xTol, LowIts, PriLev, method and QN InitMatrix. | ||
PartSep | Structure with special fields for partially separable functions, see Table 142. | |
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 | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum. | |
c_k | Value of constraints at optimum. | |
H_k | Hessian value at optimum. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
cJac | Constraint Jacobian at optimum. | |
xState | State of each variable, described in Table 150. | |
Iter | Number of iterations. | |
ExitFlag | Flag giving exit status. | |
Inform | Binary code telling type of convergence: | |
1: Iteration points are close. | ||
2: Projected gradient small. | ||
3: Iteration points are close and projected gradient small. | ||
4: Relative function value reduction low for LowIts iterations. | ||
5: Iteration points are close and relative function value reduction low for LowIts iterations. | ||
6: Projected gradient small and relative function value reduction low for LowIts iterations. | ||
7: Iteration points are close, projected gradient small and relative function value reduction low for LowIts iterations. | ||
8: Too small trust region. | ||
9: Trust region small. Iteration points close. | ||
10: Trust region and projected gradient small. | ||
11: Trust region and projected gradient small, iterations close. | ||
12: Trust region small, Relative f(x) reduction low. | ||
13: Trust region small, Relative f(x) reduction low. Iteration points are close. | ||
14: Trust region small, Relative f(x) reduction low. Projected gradient small. | ||
15: Trust region small, Relative f(x) reduction low. Iteration points close, Projected gradient small. | ||
101: Maximum number of iterations reached. | ||
102: Function value below given estimate. | ||
103: Convergence to saddle point (eigenvalues computed). | ||
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Prob | Problem structure used. |
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
Tfmin
Purpose
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.
Calling Syntax
[x, nFunc] = Tfmin(Func, x_L, x_U, xTol, Prob)
Description of Inputs
Variable | Description |
Func | Function of x to be minimized. Func must be defined as: |
f = Func(x) if no 5th argument Prob is given or | |
f = Func(x, Prob) if 5th argument Prob is given. | |
x_L | Lower bound on x. |
x_U | Upper bound on x. |
xTol | Tolerance on accuracy of minimum. |
Prob | Structure (or any Matlab variable) sent to Func. If many parameters are to be sent to Func set them in Prob as a structure. Example for parameters a and b: |
Prob.user.a = a; Prob.user.b = b; | |
[x, nFunc] = Tfmin('myFunc',0,1,1E-5,Prob); In myFunc: | |
function f = myFunc(x, Prob) | |
a = Prob.user.a; | |
b = Prob.user.b; | |
f = "matlab expression dependent of x, a and b"; |
Description of Outputs
Variable | Description |
x | Solution. |
nFunc | Number of calls to Func. |
Tfzero
Purpose
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
Variable | Description |
x_L | Lower limit on the zero x to f(x). |
x_U | Upper limit on the zero x to f(x). |
Prob | Structure, sent to Matlab routine ZeroFunc. The function name should be set in Prob.FUNCS.f0. Only the function will be used, not the gradient. |
x_0 | An initial guess on the zero to f(x). If empty, x 0 is set as the middle point in [x_L, x_U]. |
RelErr | Relative error tolerance, default 1E-7. |
AbsErr | Absolute error tolerance, default 1E-14. |
Description of Outputs
Variable | Description |
xLow | Lower limit on the zero x to f(x). |
xUpp | Upper limit on the zero x to f(x). |
ExitFlag | Status flag 1,2,3,4,5. |
1: xLow is within the requested tolerance of a zero. The interval (xLow, xUpp) collapsed to the requested tolerance, the function changes sign in (xLow, xUpp), and f(x) decreased in magnitude as (xLow, xUpp) collapsed. | |
2: f(xLow) = 0. However, the interval (xLow, xUpp) may not have collapsed to the requested tolerance. | |
3: xLow may be near a singular point of f(x). The interval (xLow, xUpp) collapsed to the requested tolerance and the function changes sign in (xLow, xUpp), but f(x) increased in magnitude as (xLow, xUpp) collapsed, i.e. abs(f (xLow)) > max(abs(f (xLow - I N )), abs(f (xU pp - I N ))). | |
4: No change in sign of f(x) was found although the interval (xLow, xUpp) collapsed to the requested tolerance. The user must examine this case and decide whether xLow is near a local minimum of f(x), or xLow is near a zero of even multiplicity, or neither of these. | |
5: Too many (> 500) function evaluations used. |
ucSolve
Purpose
Solve unconstrained nonlinear optimization problems with simple bounds on the variables.
ucSolve 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} \\ \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}}
.
Calling Syntax
Result = ucSolve(Prob, varargin)
Description of Inputs
Prob | Problem description structure. The following fields are used: | |
x_L | Lower bounds on the variables. | |
x_U | Upper bounds on the variables. | |
x_0 | Starting point. | |
FUNCS.f | Name of m-file computing the objective function f (x). | |
FUNCS.g | Name of m-file computing the gradient vector g(x). | |
FUNCS.H | Name of m-file computing the Hessian matrix H (x). | |
f_Low | Lower bound on function value. | |
Solver.Alg | Solver algorithm to be run: | |
0: Gives default, either Newton or BFGS. | ||
1: Newton with subspace minimization, using SVD. | ||
2: Safeguarded BFGS with inverse Hessian updates (standard). | ||
3: Safeguarded BFGS with Hessian updates. | ||
4: Safeguarded DFP with inverse Hessian updates. | ||
5: Safeguarded DFP with Hessian updates. | ||
6: Fletcher-Reeves CG. | ||
7: Polak-Ribiere CG. | ||
8: Fletcher conjugate descent CG-method. | ||
Solver.Method | Method used to solve equation system: | |
0: SVD (default). | ||
1: LU-decomposition. | ||
2: LU-decomposition with pivoting. | ||
3: Matlab built in QR. | ||
4: Matlab inversion. | ||
5: Explicit inverse. | ||
Solver.Method | Restart or not for C-G method: | |
0: Use restart in CG-method each n:th step. | ||
1: Use restart in CG-method each n:th step. | ||
LineParam | Structure with line search parameters, see routine LineSearch and Table 140. | |
optParam | Structure with special fields for optimization parameters, see Table 141. | |
Fields used are: eps absf, eps f, eps g, eps x, eps Rank, MaxIter, wait, size x, xTol, size f, LineSearch, LineAlg, xTol, IterPrint and QN InitMatrix. | ||
PriLevOpt | Print level. | |
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 | Optimal point. | |
f_k | Function value at optimum. | |
g_k | Gradient value at optimum. | |
H_k | Hessian value at optimum. | |
B_k | Quasi-Newton approximation of the Hessian at optimum. | |
v_k | Lagrange multipliers. | |
x_0 | Starting point. | |
f_0 | Function value at start. | |
xState | State of each variable, described in Table 150. | |
Iter | Number of iterations. | |
ExitFlag | 0 if convergence to local min. Otherwise errors. | |
Inform | Binary code telling type of convergence: | |
1: Iteration points are close. | ||
2: Projected gradient small. | ||
4: Relative function value reduction low for LowIts iterations. | ||
101: Maximum number of iterations reached. | ||
102: Function value below given estimate. | ||
104: Convergence to a saddle point. | ||
Solver | Solver used. | |
SolverAlgorithm | Solver algorithm used. | |
Prob | Problem structure used. |
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:
Prob.Solver.Alg | Prob.LineParam.sigma |
4,5 (DFP) | 0.2 |
6,7,8 (CG) | 0.01 |
M-files Used
ResultDef.m, LineSearch.m, iniSolve.m, tomSolve.m, endSolve.m
See Also
clsSolve c
Additional solvers
Documentation for the following solvers is only available at http://tomopt.com and in the m-file help.
- goalSolve - For sparse multi-objective goal attainment problems, with linear and nonlinear constraints.
- Tlsqr - Solves large, sparse linear least squares problem, as well as unsymmetric linear systems.
- lsei - For linearly constrained least squares problem with both equality and inequality constraints.
- Tnnls - Also for linearly constrained least squares problem with both equality and inequality constraints.
- qld - For convex quadratic programming problem.