source: proiecte/pmake3d/make3d_original/Make3dSingleImageStanford_version0.1/third_party/opt/yalmip/htmldata/dual.htm @ 37

Last change on this file since 37 was 37, checked in by (none), 14 years ago

Added original make3d
File size: 19.6 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2<html>
3
4<head>
5<meta http-equiv="Content-Language" content="en-us">
6<title>YALMIP Example : Dual variables</title>
7<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
8<meta content="Microsoft FrontPage 6.0" name="GENERATOR">
9<meta name="ProgId" content="FrontPage.Editor.Document">
10<link href="yalmip.css" type="text/css" rel="stylesheet">
11<base target="_self">
12</head>
13
14<body leftMargin="0" topMargin="0">
15
16<div align="left">
17
18<table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%">
19  <tr>
20    <td width="100%" align="left" height="100%" valign="top">
21           <h2>Duality</h2>
22    <hr noShade SIZE="1">
23    <p>Problems in YALMIP are internally written in the following format (this
24    will be referred to the dual form, or dual type representation)</p>
25    <strong>
26    <blockquote dir="ltr" style="MARGIN-RIGHT: 0px">
27      <p><img border="0" src="dualform.gif" width="231" height="124"></p>
28    </blockquote>
29    </strong>
30    <p>The dual to this problem is (called the primal form)</p>
31           <div align="left">
32    <img border="0" src="primalform.gif" width="243" height="78"></div>
33    <strong>
34    </strong>
35           <h3>Dual variables</h3>
36                        <p>The dual (dual in the sense that it is the dual related to a user
37                        defined constraint) variable <b>
38                 <font face="Tahoma,Arial,sans-serif">X </font></b>can be obtained using YALMIP. Consider the following
39    version of the
40    <a href="lyapunov.htm">
41    Lyapunov stability</a> example (of-course, dual variables in LP, QP and SOCP
42    problems can also be extracted)</p>
43    <table cellPadding="10" width="100%">
44      <tr>
45        <td class="xmpcode">
46        <pre>F = set(P &gt; eye(n),'Normalize');
47F = F + set(A'*P+P*A &lt; 0,'Lyapunov');
48solution = solvesdp(F,trace(P));</pre>
49        </td>
50      </tr>
51    </table>
52    <p>The dual variables related to the constraints <b>
53    <font face="Tahoma,Arial,sans-serif">P&gt;I</font></b> and <b>
54    <font face="Tahoma">A<sup>T</sup>P+PA&lt; 
55    0</font></b> can be
56    obtained by using the command dual and indexing of lmi-objects.</p>
57    <table cellPadding="10" width="100%">
58      <tr>
59        <td class="xmpcode">
60        <pre>Z1 = dual(F('Normalize'))
61Z2 = dual(F('Lyapunov'))</pre>
62        </td>
63      </tr>
64    </table>
65    <p>Standard indexing can also be used.</p>
66    <table cellPadding="10" width="100%">
67      <tr>
68        <td class="xmpcode">
69        <pre>Z1 = dual(F(1))
70Z2 = dual(F(2))</pre>
71        </td>
72      </tr>
73    </table>
74    <p>Complementary slackness can easily be checked since
75    <a href="reference.htm#double">double</a> is overloaded
76    on lmi-objects..</p>
77    <table cellPadding="10" width="100%">
78      <tr>
79        <td class="xmpcode">
80        <pre>trace(dual(F(1))*double(F(1)))
81trace(dual(F(2))*double(F(2)))</pre>
82        </td>
83      </tr>
84    </table>
85    <p>Notice, <code>double(F(1))</code> returns <code>double(0-(A'*P+P*A))</code>.<h3>
86           <a name="dualize"></a>Dualize
87                        </h3>
88           <p>Important to note is that problems in YALMIP are modeled
89           internally in the dual format (your primal <i>problem</i> is in dual <i>
90           form</i>). In control theory and many other fields, this is the
91           natural representation (we have a number of variables on which we
92           have inequality constraints), but in some fields (combinatorial
93           optimization), the primal form is often more natural.<p>Due to the choice
94           to work in the dual form, some problems are treated very
95           inefficiently in YALMIP. Consider the following problem in YALMIP.<table cellpadding="10" width="100%">
96                <tr>
97                  <td class="xmpcode">
98                  <pre>X = sdpvar(30,30);
99Y = sdpvar(3,3);
100obj = trace(X)+trace(Y);
101F = set(X&gt;0) + set(Y&gt;0);
102F = F + set(X(1,3)==9) + set(Y(1,1)==X(2,2)) + set(sum(sum(X))+sum(sum(Y)) == 20)
103<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
104|   ID|      Constraint|                      Type|
105+++++++++++++++++++++++++++++++++++++++++++++++++++
106|   #1|   Numeric value|   Matrix inequality 30x30|
107|   #2|   Numeric value|     Matrix inequality 3x3|
108|   #3|   Numeric value|   Equality constraint 1x1|
109|   #4|   Numeric value|   Equality constraint 1x1|
110|   #5|   Numeric value|   Equality constraint 1x1|
111+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
112                  </td>
113                </tr>
114              </table>
115              <p>YALMIP will <i>explicitly</i> parameterize the variable <b>X</b> 
116              with free 465 variables, <b>Y</b> with 6 free variables, create
117              two semidefinite constraints and introduce 3 equality constraints
118              in the dual form representation, corresponding to&nbsp; 471 equality
119              constraint, 2 semidefinite cones and 3 free variables in the
120              primal form.&nbsp; If we instead would have solved this
121              directly in the stated primal form, we have 3 equality
122              constraints, 2 semidefinite cones and no free variables,
123              corresponding to a dual form with 3 variables and two
124              semidefinite constraints. The computational effort is mainly
125              affected by the number of variables in the dual form and the size of the
126              semidefinite cones. Moreover, many solvers have robustness
127              problems with free variables in the primal form (equalities in the
128              dual form). Hence, in this case, this problem can probably be solved
129              much more efficiently if we could use an alternative model.<p>The
130           command <a href="reference.htm#dualize">dualize</a> can be used to
131           extract the primal form, and return the dual of
132           this problem in YALMIPs preferred dual form.<table cellpadding="10" width="100%">
133                <tr>
134                  <td class="xmpcode">
135                  <pre>[Fd,objd,primals] = dualize(F,obj);Fd
136<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
137|   ID|      Constraint|                      Type|
138+++++++++++++++++++++++++++++++++++++++++++++++++++
139|   #1|   Numeric value|   Matrix inequality 30x30|
140|   #2|   Numeric value|     Matrix inequality 3x3|
141+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
142                  </td>
143                </tr>
144              </table>
145              <p>If we solve this problem in dual form, the duals to the
146              constraints in <b>Fd</b> will correspond
147              to the original variables <b>X</b> and <b>Y</b>. The optimal values of these
148              variables can be reconstructed easily (note that the dual problem
149              is a maximization problem)<table cellpadding="10" width="100%">
150                <tr>
151                  <td class="xmpcode">
152                  <pre>solvesdp(Fd,-objd);
153for i = 1:length(primals);assign(primals{i},dual(Fd(i)));end</pre>
154                  </td>
155                </tr>
156              </table>
157              <p>Variables are actually automatically updated, so the second
158                                line in the code above is not needed (but can be useful to
159                                understand what is happening). Hence, the following code is
160                                equivalent.</p><table cellpadding="10" width="100%" id="table1">
161                <tr>
162                  <td class="xmpcode">
163                  <pre>solvesdp(Fd,-objd);</pre>
164                  </td>
165                </tr>
166              </table>
167              <p>The procedure can be applied also to problems with free
168              variables in the primal form, corresponding to equality
169              constraints in the dual form.</p>
170           <table cellpadding="10" width="100%">
171                <tr>
172                  <td class="xmpcode">
173                  <pre>X = sdpvar(2,2);
174t = sdpvar(2,1);
175Y = sdpvar(3,3);
176obj = trace(X)+trace(Y)+5*sum(t);
177
178F = set(sum(X) == 6+pi*t(1)) + set(diag(Y) == -2+exp(1)*t(2))
179F = F + set(Y&gt;0) + set(X&gt;0);
180
181solvesdp(F,obj);
182double(t)
183<font color="#000000">ans =</font></pre>
184                  <pre><font color="#000000">   -1.9099
185    0.7358</font></pre>
186                  <pre>[Fd,objd,primals,free] = dualize(F,obj);Fd
187<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
188|   ID|      Constraint|                      Type|
189+++++++++++++++++++++++++++++++++++++++++++++++++++
190|   #1|   Numeric value|     Matrix inequality 3x3|
191|   #2|   Numeric value|     Matrix inequality 2x2|
192|   #3|   Numeric value|   Equality constraint 2x1|
193+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
194                  </td>
195                </tr>
196              </table>
197              <p>The detected free variables are returned as the 4th output, and
198                                can be recovered from the dual to the equality constraints (this
199                                is also done automatically by YALMIP in practice, see above).</p>
200           <table cellpadding="10" width="100%">
201                <tr>
202                  <td class="xmpcode">
203                  <pre>solvesdp(Fd,-objd);
204assign(free,dual(Fd(end)))
205double(t)
206<font color="#000000">ans =</font></pre>
207                  <pre><font color="#000000">   -1.9099
208    0.7358</font></pre>
209                  </td>
210                </tr>
211              </table>
212              <p>To simplify things even further, you can tell YALMIP to
213                                dualize, solve the dual, and recover the primal variables, by
214                                using the associated option.</p>
215           <table cellpadding="10" width="100%" id="table3">
216                <tr>
217                  <td class="xmpcode">
218                  <pre>solvesdp(F,obj,sdpsettings('dualize',1));
219double(t)
220<font color="#000000">ans =</font></pre>
221                  <pre><font color="#000000">   -1.9099
222    0.7358</font></pre>
223                  </td>
224                </tr>
225              </table>
226              <p>
227          <img border="0" src="demoicon.gif" width="16" height="16"> Mixed problems can be dualized also, i.e.
228              problems involving constraints of both dual and primal form.
229              Constraint in dual form <b>S(y)&ge;0 </b>are automatically changed to
230              <b>S(y)-X=0</b>, <b>X&ge;0</b>, and the dualization algorithm is
231              applied to this new problem. Note that problems involving
232              dual form semidefinite constraints typically not gain from being
233              dualized, unless the dual form constraints are few and small
234              compared to the primal form constraints.<p>
235          <img border="0" src="demoicon.gif" width="16" height="16"> A problem
236                        involving translated cones <b>X&ge;C</b> where <b>C</b> is a
237                        constant is automatically converted to a problem in standard primal
238                        form, with no additional slacks variables. Hence, a lower bound on a
239                        variable will typically reduce the size of a dualized problem, since
240                        no free variables or slacks will be needed to model this cone.
241                        Practice has shown that simple bound constraints of the type <b>x&#8805;L</b> 
242                        where <b>L</b> is a large negative number can lead to problems if one tries
243                        to perform the associated variable change in order to write it as a
244                        simple LP cone. Essentially, the dual cost will contain large
245                        numbers. With a primal problem <b>{min
246                        c<sup>T</sup>x, Ax=b, x&#8805;-L}</b>) will be converted to <b>{min c<sup>T</sup>z,
247                        Az=b+AL, z&#8805;0}</b>) with the dual <b>{min (b+AL)<sup>T</sup>y, A<sup>T</sup>y<font face="Times New Roman">&#8804;</font>c}</b>.
248                        If you want to avoid detection of translated LP cones (and thus
249                        treat the involved variables as free variables), set the 4th
250                        argument in <a href="reference.htm#dualize">dualize</a>.<p>
251          <img border="0" src="demoicon.gif" width="16" height="16"> Problems
252          involving second order cone constraints can also be dualized. A constraint
253          of the type <code>x = sdpvar(n,1);F = set(cone(x(2:end),x(1)));</code> is a second
254          order constraint in standard primal form. If your cone constraint violates this
255          form, slacks will be introduced, except for translated second order
256                        cones, just as in the semidefinite case. Note
257          that you need a primal-dual solver that can solve second order cone
258          constraints natively in order to recover the original variables
259          (currently
260              <a href="solvers.htm#sedumi">SeDuMi</a> and
261              <a href="solvers.htm#sdpt3">SDPT3</a> for mixed semidefinite
262          second order cone problems, and
263              <a href="solvers.htm#mosek">MOSEK</a> for pure second order cone
264          problems).<p>
265    <img border="0" src="exclamationmark.jpg" align="left" width="16" height="16"> Your solver
266          has to be able to return both primal and dual variables for the reconstruction of
267          variables to work. All SDP solvers support this, except
268              <a href="solvers.htm#lmilab">LMILAB</a>.<p>
269    <img border="0" src="exclamationmark.jpg" align="left" width="16" height="16">Primal matrices (<b>X</b></b> and <b>Y</b> in the examples above) must
270           be defined in one simple call in order to enable detection of the primal
271           structure. In other words, a constraint <code>set(X&gt;0)</code> where
272          <b>X</b> is defined
273           with the code <code>x = sdpvar(10,1);X =
274           [x(1) x(6);x(6) x(2)]</code> will not be categorized as a primal matrix, but
275           as matrix constraint in dual form with three free variables.<h3>
276          <a name="primalize"></a>Primalize</h3>
277           <p>
278          For completeness, a functionality called primalize is available. This
279          function takes an optimization problem in dual form and returns a
280          YALMIP model in primal form. Consider the following SDP with 3 free
281          variables, 1 equality constraint, and 1 SDP constraint of dimension 2.<table cellpadding="10" width="100%">
282                <tr>
283                  <td class="xmpcode">
284                  <pre>C = eye(2);
285A1 = randn(2,2);A1 = A1*A1';
286A2 = randn(2,2);A2 = A2*A2';
287A3 = randn(2,2);A3 = A3*A3';
288y = sdpvar(3,1);
289
290obj = -sum(y) % Maximize sum(y) i.e. minimize -sum(y)
291F = set(C-A1*y(1)-A2*y(2)-A3*y(3) &gt; 0) + set(y(1)+y(2)==1)</pre>
292                  </td>
293                </tr>
294              </table>
295           <p>A model in primal form is (note the negation of the objective
296           function, primalize assumes the objective function should be
297           maximized)</p>
298           <table cellpadding="10" width="100%">
299                <tr>
300                  <td class="xmpcode">
301                  <pre>[Fp,objp,free] = primalize(F,-obj);Fp
302<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++
303|   ID|      Constraint|                      Type|
304+++++++++++++++++++++++++++++++++++++++++++++++++++
305|   #1|   Numeric value|     Matrix inequality 2x2|
306|   #2|   Numeric value|   Equality constraint 3x1|
307+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
308                  </td>
309                </tr>
310              </table>
311           <p>
312          The problem can now be solved in the primal form, and the original
313          variables are reconstructed from the duals of the equality constraints
314          (placed last). Note that the primalize function returns an objective
315          function that should be minimized.<table cellpadding="10" width="100%">
316                <tr>
317                  <td class="xmpcode">
318                  <pre>solvesdp(Fp,objp);
319assign(free,dual(Fp(end)));</pre>
320                  </td>
321                </tr>
322              </table>
323           <p>Why not dualize the primalized model!</p>
324           <table cellpadding="10" width="100%">
325                <tr>
326                  <td class="xmpcode">
327                  <pre>[Fd,objd,X,free] = dualize(Fp,objp);Fd<font color="#000000">
328+++++++++++++++++++++++++++++++++++++++++++++++++++
329|   ID|      Constraint|                      Type|
330+++++++++++++++++++++++++++++++++++++++++++++++++++
331|   #1|   Numeric value|     Matrix inequality 2x2|
332|   #2|   Numeric value|   Equality constraint 1x1|
333+++++++++++++++++++++++++++++++++++++++++++++++++++</font></pre>
334                  </td>
335                </tr>
336              </table>
337           <p>The model obtained from the primalization is most often more
338           complex than the original model, so there is typically no reason
339           to primalize a model. </p>
340           <p>There are however some cases where it may make sense. Consider the
341           problem in the <a href="kyp.htm">KYP example</a></p>
342      <table cellPadding="10" width="100%">
343        <tr>
344          <td class="xmpcode">
345          <pre>n = 50;
346A = randn(n);A = A - max(real(eig(A)))*eye(n)*1.5; % Stable dynamics
347B = randn(n,1);
348C = randn(1,n);
349
350t = sdpvar(1,1);
351P = sdpvar(n,n);
352
353obj = t;
354F = set(kyp(A,B,P,blkdiag(C'*C,-t)) &lt; 0)</pre>
355          </td>
356        </tr>
357      </table>
358           <p>The original problem has 466 variables and one semidefinite
359           constraint. If we primalize this problem, a new problem with 1276
360           equality constraints and 1326 variables is obtained. This means that
361                        the effective number of variables is low (the degree of freedom).</p>
362      <table cellPadding="10" width="100%">
363        <tr>
364          <td class="xmpcode">
365          <pre>[Fp,objp] = primalize(F,-obj);Fp
366<font color="#000000">+++++++++++++++++++++++++++++++++++++++++++++++++++++
367|   ID|      Constraint|                        Type|
368+++++++++++++++++++++++++++++++++++++++++++++++++++++
369|   #1|   Numeric value|     Matrix inequality 51x51|
370|   #2|   Numeric value|  Equality constraint 1276x1|
371+++++++++++++++++++++++++++++++++++++++++++++++++++++</font>
372length(getvariables(Fp))
373<font color="#000000">ans =</font></pre>
374          <pre><font color="#000000">   1326</font></pre>
375          </td>
376        </tr>
377      </table>
378           <p>For comparison, let us first solve the original problem.</p>
379      <table cellPadding="10" width="100%">
380        <tr>
381          <td class="xmpcode">
382          <pre>solvesdp(F,obj)
383<font color="#000000">ans = </font></pre>
384          <pre><font color="#000000">    yalmiptime: 0.2410
385    solvertime: 32.4150
386          info: 'No problems detected (SeDuMi)'
387       problem: 0</font></pre>
388          </td>
389        </tr>
390      </table>
391           <p>The primalized takes approximately the same time to solve (this
392           can differ between problem instances though).</p>
393      <table cellPadding="10" width="100%">
394        <tr>
395          <td class="xmpcode">
396          <pre>solvesdp(Fp,objp)
397<font color="#000000">ans = </font></pre>
398          <pre><font color="#000000">    yalmiptime: 0.3260
399    solvertime: 32.2530
400          info: 'No problems detected (SeDuMi)'
401       problem: 0</font></pre>
402          </td>
403        </tr>
404      </table>
405           <p>So why would we want to perform the primalization? We let YALMIP
406                        remove the equalities constraints first!</p>
407      <table cellPadding="10" width="100%">
408        <tr>
409          <td class="xmpcode">
410          <pre>solvesdp(Fp,objp,sdpsettings('removeequalities',1))
411<font color="#000000">ans = </font></pre>
412          <pre><font color="#000000">    yalmiptime: 2.6240
413    solvertime: 1.1860
414          info: 'No problems detected (SeDuMi)'
415       problem: 0</font></pre>
416          </td>
417        </tr>
418      </table>
419           <p>The drastic reduction in actual solution-time of the semidefinite
420                        program comes at a price. Removing the equality constraints and
421                        deriving a reduced basis with a smaller number of variables requires
422                        computation of a QR factorization of a matrix of
423           dimension 1326 by 1276. The cost of doing this is roughly 2 seconds.
424                        The total saving in computation time is however still high enough to
425                        motivate the primalization.</p></td>
426  </tr>
427</table>
428
429</div>
430
431</body>
432
433</html>
Note: See TracBrowser for help on using the repository browser.