📄 dual.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<title>YALMIP Example : Dual variables</title>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
<meta content="Microsoft FrontPage 6.0" name="GENERATOR">
<meta name="ProgId" content="FrontPage.Editor.Document">
<link href="yalmip.css" type="text/css" rel="stylesheet">
<base target="_self">
</head>
<body leftMargin="0" topMargin="0">
<div align="left">
<table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%">
<tr>
<td width="100%" align="left" height="100%" valign="top">
<h2>Duality</h2>
<hr noShade SIZE="1">
<p>Problems in YALMIP are internally written in the following format (this
will be referred to the dual form, or dual type representation)</p>
<strong>
<blockquote dir="ltr" style="MARGIN-RIGHT: 0px">
<p><img border="0" src="dualform.gif" width="231" height="124"></p>
</blockquote>
</strong>
<p>The dual to this problem is (called the primal form)</p>
<div align="left">
<img border="0" src="primalform.gif" width="243" height="78"></div>
<strong>
</strong>
<p>The dual (dual in the sense that it is the dual related to a user
defined constraint) variable <b>
<font face="Tahoma,Arial,sans-serif">X </font></b>can be obtained using YALMIP. Consider the following
version of the
<a href="lyapunov.htm">
Lyapunov stability</a> example (of-course, dual variables in LP, QP and SOCP
problems can also be extracted)</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>F = set(P > eye(n),'Normalize');
F = F + set(A'*P+P*A < 0,'Lyapunov');
solution = solvesdp(F,trace(P));</pre>
</td>
</tr>
</table>
<p>The dual variables related to the constraints <b>
<font face="Tahoma,Arial,sans-serif">P>I</font></b> and <b>
<font face="Tahoma">A<sup>T</sup>P+PA<
0</font></b> can be
obtained by using the command dual and indexing of lmi-objects.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>Z1 = dual(F('Normalize'))
Z2 = dual(F('Lyapunov'))</pre>
</td>
</tr>
</table>
<p>Standard indexing can also be used.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>Z1 = dual(F(1))
Z2 = dual(F(2))</pre>
</td>
</tr>
</table>
<p>Complementary slackness can easily be checked since
<a href="reference.htm#double">double</a> is overloaded
on lmi-objects..</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>trace(dual(F(1))*double(F(1)))
trace(dual(F(2))*double(F(2)))</pre>
</td>
</tr>
</table>
<p>Notice, <code>double(F(1))</code> returns <code>double(0-(A'*P+P*A))</code>.<h3>
<a name="dualize"></a>Dualize</h3>
<p>Important to note is that problems in YALMIP are modeled
internally in the dual format (your primal <i>problem</i> is in dual <i>
form</i>). In control theory and many other fields, this is the
natural representation (we have a number of variables on which we
have inequality constraints), but in some fields (combinatorial
optimization), the primal form is often more natural.<p>Due to the choice
to work in the dual form, some problems are treated very
inefficiently in YALMIP. Consider the following problem in YALMIP.<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>X = sdpvar(30,30);
Y = sdpvar(3,3);
obj = trace(X)+trace(Y);
F = set(X>0) + set(Y>0);
F = F + set(X(1,3)==9) + set(Y(1,1)==X(2,2)) + set(sum(sum(X))+sum(sum(Y)) == 20)
<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality 30x30|
| #2| Numeric value| Matrix inequality 3x3|
| #3| Numeric value| Equality constraint 1x1|
| #4| Numeric value| Equality constraint 1x1|
| #5| Numeric value| Equality constraint 1x1|
+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
</td>
</tr>
</table>
<p>YALMIP will <i>explicitly</i> parameterize the variable <b>X</b>
with free 465 variables, <b>Y</b> with 6 free variables, create
two semidefinite constraints and introduce 3 equality constraints
in the dual form representation, corresponding to 471 equality
constraint, 2 semidefinite cones and 3 free variables in the
primal form. If we instead would have solved this
directly in the stated primal form, we have 3 equality
constraints, 2 semidefinite cones and no free variables,
corresponding to a dual form with 3 variables and two
semidefinite constraints. The computational effort is mainly
affected by the number of variables in the dual form and the size of the
semidefinite cones. Moreover, many solvers have robustness
problems with free variables in the primal form (equalities in the
dual form). Hence, in this case, this problem can probably be solved
much more efficiently if we could use an alternative model.<p>The
command <a href="reference.htm#dualize">dualize</a> can be used to
extract the primal form, and return the dual of
this problem in YALMIPs preferred dual form.<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>[Fd,objd,primals] = dualize(F,obj);Fd
<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality 30x30|
| #2| Numeric value| Matrix inequality 3x3|
+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
</td>
</tr>
</table>
<p>If we solve this problem in dual form, the duals to the
constraints in <b>Fd</b> will correspond
to the original variables <b>X</b> and <b>Y</b>. The optimal values of these
variables can be reconstructed easily (note that the dual problem
is a maximization problem)<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>solvesdp(Fd,-objd);
for i = 1:length(primals);assign(primals{i},dual(Fd(i)));end</pre>
</td>
</tr>
</table>
<p>Variables are actually automatically updated, so the second
line in the code above is not needed (but can be useful to
understand what is happening). Hence, the following code is
equivalent.</p><table cellpadding="10" width="100%" id="table1">
<tr>
<td class="xmpcode">
<pre>solvesdp(Fd,-objd);</pre>
</td>
</tr>
</table>
<p>The procedure can be applied also to problems with free
variables in the primal form, corresponding to equality
constraints in the dual form.</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>X = sdpvar(2,2);
t = sdpvar(2,1);
Y = sdpvar(3,3);
obj = trace(X)+trace(Y)+5*sum(t);
F = set(sum(X) == 6+pi*t(1)) + set(diag(Y) == -2+exp(1)*t(2))
F = F + set(Y>0) + set(X>0);</pre>
<pre>[Fd,objd,primals,free] = dualize(F,obj);Fd
<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
| ID| Constraint| Type|
+++++++++++++++++++++++++++++++++++++++++++++++++++
| #1| Numeric value| Matrix inequality 3x3|
| #2| Numeric value| Matrix inequality 2x2|
| #3| Numeric value| Equality constraint 2x1|
+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
</td>
</tr>
</table>
<p>The detected free variables are returned as the 4th output, and
can be recovered from the dual to the equality constraints (this
is also done automatically by YALMIP in practice).</p>
<table cellpadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>solvesdp(Fd,-objd);
assign(free,dual(Fd(end)))
double(t)
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> -1.9099
0.7358</font></pre>
</td>
</tr>
</table>
<p>
<img border="0" src="demoicon.gif" width="16" height="16"> Mixed problems can be dualized also, i.e.
problems involving constraints of both dual and primal form.
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -