PdcoTL: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
[[Category:Solvers]] | [[Category:Solvers]] | ||
==Purpose== | ==Purpose== | ||
''pdcoTL ''solves linearly constrained convex nonlinear optimization problems of the kind | ''pdcoTL ''solves linearly constrained convex nonlinear optimization problems of the kind | ||
<equation id="eqn:pdco"> | |||
<math> | <math> | ||
\begin{array}{cccccc} | \begin{array}{cccccc} | ||
Line 14: | Line 12: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
</equation> | |||
where <math>f(x)</math> is a convex nonlinear function, <math>x,x_L,x_U \in \MATHSET{R}^{n}</math> , <math>A\in \MATHSET{R}^{m \times n}</math> and <math>b_L, b_U \in \MATHSET{R}^{m}</math>. | |||
where <math>f(x)</math> is a convex nonlinear function, <math>x,x_L,x_U \in \ | |||
==Calling Syntax== | ==Calling Syntax== | ||
<syntaxhighlight lang="matlab"> | |||
Result=tomRun('pdco',Prob,...); | Result=tomRun('pdco',Prob,...); | ||
</syntaxhighlight> | |||
== | ==Inputs== | ||
{| | {| class="wikitable" | ||
!''Prob''||colspan="2"|Problem description structure. The following fields are used: | |||
|- | |- | ||
|||''x_0''||Initial ''x ''vector, used if non-empty. | |||''x_0''||Initial ''x ''vector, used if non-empty. | ||
Line 60: | Line 60: | ||
|||''eps_x''||Accuracy for satisfying ''x''1 ''. * z''1 = 0'', x''2 ''.z''1 = 0, where ''z ''= ''z''1 ''- z''2 and ''z''1 '', z''2 ''> ''0.(''Prob.SOL.pdco.OptTol'') | |||''eps_x''||Accuracy for satisfying ''x''1 ''. * z''1 = 0'', x''2 ''.z''1 = 0, where ''z ''= ''z''1 ''- z''2 and ''z''1 '', z''2 ''> ''0.(''Prob.SOL.pdco.OptTol'') | ||
|-valign="top" | |-valign="top" | ||
|||''bTol''||Accuracy for satisfying ''Ax ''+ ''D''2 ''r ''= ''b'', '' | |||''bTol''||Accuracy for satisfying ''Ax ''+ ''D''<sub>2</sub>''r ''= ''b'', ''A<sup>T</sup> y ''+ ''z ''= ''Δf ''(''x'') and ''x - x''1 = ''bL , x ''+''x''2 = ''bU '', where ''x''<sub>1</sub> '', x''<sub>2</sub> ''> ''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'') | |||''wait''||0 - solve the problem with default internal parameters; 1 - pause: allows interactive resetting of parameters. (''Prob.SOL.pdco.wait'') | ||
|} | |} | ||
== | ==Outputs== | ||
{| | {| class="wikitable" | ||
!''Result''||colspan="2"|Structure with result from optimization. The following fields are set by ''pdcoTL'' | |||
|- | |- | ||
|||''x_k''||Solution vector | |||''x_k''||Solution vector | ||
Line 88: | Line 88: | ||
|||''v_k''||Lagrangian multipliers (orignal bounds + constraints ) | |||''v_k''||Lagrangian multipliers (orignal bounds + constraints ) | ||
|-valign="top" | |-valign="top" | ||
|||''y_k''||Lagrangian multipliers (for bounds + dual solution vector) The full | |||''y_k''||Lagrangian multipliers (for bounds + dual solution vector) The full [''z''; ''y''] vector 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 | |||''ExitFlag''||Tomlab Exit status from ''pdco ''MEX | ||
Line 117: | Line 117: | ||
''pdco ''implements an primal-dual barrier method developed at Stanford Systems Optimization Laboratory (SOL). | ''pdco ''implements an primal-dual barrier method developed at Stanford Systems Optimization Laboratory (SOL). | ||
The problem ( | The problem (<xr id="eqn:pdco" />) is first reformulated into SOL PDCO form: | ||
Line 146: | Line 146: | ||
where <math>D_1</math> and <math>D_2</math> are positive-definite diagonal matrices defined from <math>d_1</math>, <math>d_2</math> given in Prob.SOL.d1 and Prob.SOL.d2. | where <math>D_1</math> and <math>D_2</math> are positive-definite diagonal matrices defined from <math>d_1</math>, <math>d_2</math> given in Prob.SOL.d1 and Prob.SOL.d2. | ||
In particular, <math>d_2</math> indicates the accuracy required for satisfying each row of <math>Ax=b</math>. See ''pdco'' for a detailed discussion of <math>D_1</math> and <math>D_2</math>. Note that in ''pdco'', the objective <math>f(x)</math> is denoted <math>\phi(x)</math>, <math>bl == x\_L</math> and <math>bu == x\_U</math>. | In particular, <math>d_2</math> indicates the accuracy required for satisfying each row of <math>Ax=b</math>. See ''pdco.m'' for a detailed discussion of <math>D_1</math> and <math>D_2</math>. Note that in ''pdco'', the objective <math>f(x)</math> is denoted <math>\phi(x)</math>, <math>bl == x\_L</math> and <math>bu == x\_U</math>. | ||
==Examples== | ==Examples== | ||
Problem 14 and 15 in ''tomlab/testprob/con prob | Problem 14 and 15 in ''tomlab/testprob/con prob.m ''are good examples of the use of ''pdcoTL''. | ||
==M-files Used== | ==M-files Used== |
Revision as of 06:01, 21 July 2011
Purpose
pdcoTL solves linearly constrained convex nonlinear optimization problems of the kind
<equation id="eqn:pdco"> </equation>
where is a convex nonlinear function, Failed to parse (unknown function "\MATHSET"): {\displaystyle 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}} .
Calling Syntax
Result=tomRun('pdco',Prob,...);
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 + D2r = 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) |
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] vector 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 (<xr id="eqn:pdco" />) is first reformulated into SOL PDCO form:
Failed to parse (unknown function "\multicolumn"): {\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 (unknown function "\multicolumn"): {\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 and are positive-definite diagonal matrices defined from , given in Prob.SOL.d1 and Prob.SOL.d2.
In particular, indicates the accuracy required for satisfying each row of . See pdco.m for a detailed discussion of and . Note that in pdco, the objective is denoted , and .
Examples
Problem 14 and 15 in tomlab/testprob/con prob.m are good examples of the use of pdcoTL.
M-files Used
pdcoSet.m, pdco.m, Tlsqrmat.m
See Also
pdscoTL.m