PdscoTL: Difference between revisions
(Created page with "==Purpose== ''pdscoTL ''solves linearly constrained convex nonlinear optimization problems. <math> \begin{array}{cccccc} \min\limits_x & f(x) \\ \mathrm{s/t} & x_L & \leq & x ...") |
No edit summary |
||
(5 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
[[Category:Solvers]] | |||
==Purpose== | ==Purpose== | ||
Line 4: | Line 5: | ||
<equation id="eqn:pdsco"> | |||
<math> | <math> | ||
\begin{array}{cccccc} | \begin{array}{cccccc} | ||
Line 11: | Line 13: | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
</equation> | |||
where <math>f(x)</math> is a convex separable nonlinear function, <math>x,x_L,x_U | where <math>f(x)</math> is a convex separable nonlinear function, <math>x,x_L,x_U | ||
\in \ | \in \mathbb{R}^{n}</math> , <math>A\in \mathbb{R}^{m \times n}</math> and <math>b_L, b_U \in\mathbb{R}^{m}</math>. | ||
==Calling Syntax== | ==Calling Syntax== | ||
<source lang="matlab"> | |||
Result=tomRun('pdsco',Prob,...); | Result=tomRun('pdsco',Prob,...); | ||
</source> | |||
==Inputs== | |||
{| class="wikitable" | |||
{| | |||
|''Prob''||colspan="2"|Problem description structure. The following fields are used: | |''Prob''||colspan="2"|Problem description structure. The following fields are used: | ||
|- | |- | ||
Line 42: | Line 49: | ||
|- | |- | ||
|||''y0''||Initial dual parameters for linear constraints (default 0) | |||''y0''||Initial dual parameters for linear constraints (default 0) | ||
|- | |-valign="top" | ||
|||''z0''||Initial dual parameters for simple bounds (default 1''/N '') | |||''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 '') | |||''xsize''||Estimate of the biggest ''x ''at the solution. (default 1''/N '') | ||
Line 59: | Line 66: | ||
|||''eps_x''||Accuracy for satisfying ''x. * z ''= 0 | |||''eps_x''||Accuracy for satisfying ''x. * z ''= 0 | ||
|-valign="top" | |-valign="top" | ||
|||''bTol''||Accuracy for satisfying ''Ax ''+ ''r ''= ''b'', '' | |||''bTol''||Accuracy for satisfying ''Ax ''+ ''r ''= ''b'', ''A<sup>T</sup>y ''+ ''z ''= ''∇f ''(''x'') and ''x - x''1 = ''b<sub>L</sub> , x ''+ ''x''2 =''b<sub>U</sub>'', where ''x''<sub>1</sub> '', x''<sub>2</sub> ''> ''0. (''Prob.SOL.pdco.FeaTol'') | ||
|-valign="top" | |-valign="top" | ||
|||''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 ''pdscoTL'': | |''Result''||colspan="2"|Structure with result from optimization. The following fields are set by ''pdscoTL'': | ||
|- | |- | ||
Line 87: | Line 94: | ||
|||''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 [''z''; ''y''] vector 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 | |||''ExitFlag''||Tomlab Exit status from ''pdsco ''MEX | ||
|- | |-valign="top" | ||
|||''Inform''||''pdsco ''information parameter: | |||''Inform''||''pdsco ''information parameter: | ||
0 == Solution found | |||
1 == Too many iterations | |||
2 == Linesearch failed too often | |||
|- | |- | ||
|||''Iter''||Number of iterations | |||''Iter''||Number of iterations | ||
Line 114: | Line 121: | ||
==Description== | ==Description== | ||
''pdsco ''implements an primal-dual barrier method developed at Stanford Systems Optimization Laboratory (SOL). The problem ( | ''pdsco ''implements an primal-dual barrier method developed at Stanford Systems Optimization Laboratory (SOL). The problem ([[#Equation: pdsco]]) is first reformulated into SOL PDSCO form: | ||
====Equation: pdsco==== | |||
<math> | <math> | ||
Line 132: | Line 140: | ||
\begin{array}{lllcll} | \begin{array}{lllcll} | ||
\min\limits_{x,r} & | \min\limits_{x,r} & | ||
{f(x) + | |||
\frac{1}{2}\|\gamma x\|^2 + \frac{1}{2}\|r / \delta \|^2 } \\ | \frac{1}{2}\|\gamma x\|^2 + \frac{1}{2}\|r / \delta \|^2 } \\ | ||
\\ | \\ | ||
\mathrm{s/t} & & & x & \geq & 0 \\ | \mathrm{s/t} & & & x & \geq & 0 \\ | ||
{} & Ax & + & r & = & b \\ | {} & Ax & + & r & = & b \\ | ||
{} & | {} & {r \mathrm{\ unconstrained}} \\ | ||
\end{array} | \end{array} | ||
</math> | </math> | ||
Line 146: | Line 154: | ||
With positive <math>\gamma,\delta</math> the primal-dual solution <math>(x,y,z)</math> is bounded and unique. | With positive <math>\gamma,\delta</math> the primal-dual solution <math>(x,y,z)</math> is bounded and unique. | ||
See ''pdsco'' for a detailed discussion of < | See ''pdsco.m'' for a detailed discussion of <math>\gamma</math> and <math>\delta</math>. Note that in ''pdsco.m'', 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== | ||
Line 152: | Line 160: | ||
Problem 14 and 15 in tomlab/testprob/con prob.m are good examples of the use of ''pdscoTL''. | Problem 14 and 15 in tomlab/testprob/con prob.m are good examples of the use of ''pdscoTL''. | ||
==M-files | ==M-files Used== | ||
''pdscoSet.m'', ''pdsco.m'', ''Tlsqrmat.m'' | ''pdscoSet.m'', ''pdsco.m'', ''Tlsqrmat.m'' |
Latest revision as of 08:17, 16 January 2012
Purpose
pdscoTL solves linearly constrained convex nonlinear optimization problems.
<equation id="eqn:pdsco">
</equation>
where is a convex separable nonlinear function, , and .
Calling Syntax
Result=tomRun('pdsco',Prob,...);
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, ATy + 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 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] vector 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 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 (#Equation: pdsco) is first reformulated into SOL PDSCO form:
Equation: pdsco
The problem actually solved by pdsco is
where is the primal regularization parameter, typically small but 0 is allowed. Furthermore, is the dual regularization parameter, typically small or 1; must be strictly greater than zero.
With positive the primal-dual solution is bounded and unique.
See pdsco.m for a detailed discussion of and . Note that in pdsco.m, the objective is denoted , and .
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