[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 : Determinant maximization</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 | <table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%"> |
---|
| 18 | <tr> |
---|
| 19 | <td width="100%" align="left" height="100%" valign="top"> |
---|
| 20 | <h2>Determinant maximization </h2> |
---|
| 21 | <hr noshade size="1"> |
---|
| 22 | <p>Let us solve a determinant maximization problem. Given two ellipsoids |
---|
| 23 | </p> |
---|
| 24 | <blockquote dir="ltr" style="MARGIN-RIGHT: 0px"> |
---|
| 25 | <p><span style="font-style: normal"><strong>E<sub>1</sub> = {x | x<sup>T</sup>P<sub>1</sub>x</strong></span><strong>≤</strong><strong><span style="font-style: normal">1}</span></strong></p> |
---|
| 26 | <p><span style="font-style: normal"><strong>E<sub>2</sub> = {x | x<sup>T</sup>P<sub>2</sub>x</strong></span><strong>≤</strong><span style="font-style: normal"><strong>1}</strong></span></p> |
---|
| 27 | </blockquote> |
---|
| 28 | <p>Find the ellipsoid <strong>E = {x | x</strong><span style="font-style: normal"><strong><sup>T</sup></strong></span><strong>Px≤1}</strong> |
---|
| 29 | with smallest possible volume that contain the union of <strong>E<sub>1</sub></strong> |
---|
| 30 | and <strong>E<sub>2</sub></strong>. By using the fact that the volume of the |
---|
| 31 | ellipsoid is proportional to <strong>-det P </strong>and applying the S-procedure, |
---|
| 32 | it can be shown that this problem can be written as</p> |
---|
| 33 | <p><img border="0" src="ellips5.gif" hspace="45"></p> |
---|
| 34 | <p>The objective function <b>-det P</b> (which is minimized) is not |
---|
| 35 | convex, but monotonic transformations can render this problem convex. One |
---|
| 36 | alternative is the logarithmic transform, leading to minimization of <b>-log |
---|
| 37 | det P</b> instead. This operator was used in previous version of YALMIP, |
---|
| 38 | but is not recommended any more. </p> |
---|
| 39 | <p>Instead, YALMIP uses <b>-(det P)<sup>1/m</sup></b> where <b>m</b> is dimension of <b>P </b>(in other words, the geometric mean of the eigenvalues). The |
---|
| 40 | concave function <b>(det |
---|
| 41 | P)<sup>1/m</sup></b>, available by applying <b>geomean</b> on a Hermitian |
---|
| 42 | matrix in YALMIP, can be modeled using semidefinite and second order |
---|
| 43 | cones, hence any SDP solver can be used for solving determinant |
---|
| 44 | maximization problems. See <a href="readmore.htm#NESNEM94">[Nesterov and |
---|
| 45 | Nemirovskii]</a> for details.</p> |
---|
| 46 | <table cellpadding="10" width="100%"> |
---|
| 47 | <tr> |
---|
| 48 | <td class="xmpcode"><font face="Courier New" color="#0000c0">n = 2;<br> |
---|
| 49 | P1 = randn(2);P1 = P1*P1'; % Generate random ellipsoid<br> |
---|
| 50 | P2 = randn(2);P2 = P2*P2'; % Generate random ellipsoid<br> |
---|
| 51 | t = sdpvar(2,1);<br> |
---|
| 52 | P = sdpvar(n,n);<br> |
---|
| 53 | F = set(1 > t > 0);<br> |
---|
| 54 | F = F + set(t(1)*P1-P > 0);<br> |
---|
| 55 | F = F + set(t(2)*P2-P > 0);<br> |
---|
| 56 | sol = solvesdp(F,-geomean(P));<br> |
---|
| 57 | ellipplot(double(P));hold on;<br> |
---|
| 58 | ellipplot(double(P1));<br> |
---|
| 59 | ellipplot(double(P2));</font></td> |
---|
| 60 | </tr> |
---|
| 61 | </table> |
---|
| 62 | <p>If you have |
---|
| 63 | the dedicated solver |
---|
| 64 | <a href="solvers.htm#maxdet">MAXDET</a> installed and want to use it, you must use the dedicated command |
---|
| 65 | <a href="reference.htm#logdet">logdet</a> for the objective and explicitly select |
---|
| 66 | <a href="solvers.htm#maxdet">MAXDET</a>. This command can not be used |
---|
| 67 | in any other construction than in the objective function, compared to the <b>geomean</b> operator that can be used as any other variable in YALMIP, since it |
---|
| 68 | a so called <a href="extoperators.htm">extended operator</a>. </p> |
---|
| 69 | <table cellpadding="10" width="100%"> |
---|
| 70 | <tr> |
---|
| 71 | <td class="xmpcode"><font face="Courier New" color="#0000c0">solvesdp(F,-logdet(P),sdpsettings('solver','maxdet'));<br> |
---|
| 72 | ellipplot(double(P));hold on;<br> |
---|
| 73 | ellipplot(double(P1));<br> |
---|
| 74 | ellipplot(double(P2));</font></td> |
---|
| 75 | </tr> |
---|
| 76 | </table> |
---|
| 77 | <p> |
---|
| 78 | <img border="0" src="demoicon.gif" width="16" height="16"> Note that |
---|
| 79 | if you use the |
---|
| 80 | <a href="reference.htm#logdet">logdet</a> command, if |
---|
| 81 | <a href="solvers.htm#maxdet">MAXDET</a> not is |
---|
| 82 | explicitly selected, YALMIP will use <b>-(det P)<sup>1/m</sup></b> as objective |
---|
| 83 | function instead. |
---|
| 84 | This will not cause any problems if your objective function is a simple |
---|
| 85 | <a href="reference.htm#logdet">logdet</a> expression (since the two functions |
---|
| 86 | are monotonically related). However, if you have a mixed objective |
---|
| 87 | function such as <b>tr(P)-logdet(P)</b>, the conversion will change your |
---|
| 88 | optimal solution. Hence, if you really want to optimize the mixed |
---|
| 89 | expression, you must explicitly select |
---|
| 90 | <a href="solvers.htm#maxdet">MAXDET</a>. Otherwise, YALMIP will change |
---|
| 91 | your objective to <b>tr(P)-(det P)<sup>1/m</sup></b>.</td> |
---|
| 92 | </tr> |
---|
| 93 | </table> |
---|
| 94 | </div> |
---|
| 95 | |
---|
| 96 | </body> |
---|
| 97 | |
---|
| 98 | </html> |
---|