[37] | 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 > eye(n),'Normalize'); |
---|
| 47 | F = F + set(A'*P+P*A < 0,'Lyapunov'); |
---|
| 48 | solution = 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>I</font></b> and <b> |
---|
| 54 | <font face="Tahoma">A<sup>T</sup>P+PA< |
---|
| 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')) |
---|
| 61 | Z2 = 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)) |
---|
| 70 | Z2 = 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))) |
---|
| 81 | trace(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); |
---|
| 99 | Y = sdpvar(3,3); |
---|
| 100 | obj = trace(X)+trace(Y); |
---|
| 101 | F = set(X>0) + set(Y>0); |
---|
| 102 | F = 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 471 equality |
---|
| 119 | constraint, 2 semidefinite cones and 3 free variables in the |
---|
| 120 | primal form. 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); |
---|
| 153 | for 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); |
---|
| 174 | t = sdpvar(2,1); |
---|
| 175 | Y = sdpvar(3,3); |
---|
| 176 | obj = trace(X)+trace(Y)+5*sum(t); |
---|
| 177 | |
---|
| 178 | F = set(sum(X) == 6+pi*t(1)) + set(diag(Y) == -2+exp(1)*t(2)) |
---|
| 179 | F = F + set(Y>0) + set(X>0); |
---|
| 180 | |
---|
| 181 | solvesdp(F,obj); |
---|
| 182 | double(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); |
---|
| 204 | assign(free,dual(Fd(end))) |
---|
| 205 | double(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)); |
---|
| 219 | double(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)≥0 </b>are automatically changed to |
---|
| 230 | <b>S(y)-X=0</b>, <b>X≥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≥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≥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≥-L}</b>) will be converted to <b>{min c<sup>T</sup>z, |
---|
| 247 | Az=b+AL, z≥0}</b>) with the dual <b>{min (b+AL)<sup>T</sup>y, A<sup>T</sup>y<font face="Times New Roman">≤</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>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); |
---|
| 285 | A1 = randn(2,2);A1 = A1*A1'; |
---|
| 286 | A2 = randn(2,2);A2 = A2*A2'; |
---|
| 287 | A3 = randn(2,2);A3 = A3*A3'; |
---|
| 288 | y = sdpvar(3,1); |
---|
| 289 | |
---|
| 290 | obj = -sum(y) % Maximize sum(y) i.e. minimize -sum(y) |
---|
| 291 | F = set(C-A1*y(1)-A2*y(2)-A3*y(3) > 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); |
---|
| 319 | assign(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; |
---|
| 346 | A = randn(n);A = A - max(real(eig(A)))*eye(n)*1.5; % Stable dynamics |
---|
| 347 | B = randn(n,1); |
---|
| 348 | C = randn(1,n); |
---|
| 349 | |
---|
| 350 | t = sdpvar(1,1); |
---|
| 351 | P = sdpvar(n,n); |
---|
| 352 | |
---|
| 353 | obj = t; |
---|
| 354 | F = set(kyp(A,B,P,blkdiag(C'*C,-t)) < 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> |
---|
| 372 | length(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> |
---|