[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 : Geometric programming</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>Geometric programming</h2> |
---|
| 21 | <hr noShade SIZE="1"> |
---|
| 22 | <p> |
---|
| 23 | <img border="0" src="exclamationmark.jpg" align="left" width="16" height="16">This |
---|
| 24 | example requires <a href="solvers.htm#mosek">MOSEK</a>, |
---|
| 25 | <a href="solvers.htm#GPPOSY">GPPOSY</a> or |
---|
| 26 | <a href="solvers.htm#fmincon">fmincon</a><br> |
---|
| 27 | <br> |
---|
| 28 | Nonlinear terms can be defined also with negative and non-integer powers. |
---|
| 29 | This can be used to define geometric optimization problems.<br> |
---|
| 30 | <img border="0" src="gemoetric.gif" width="144" height="102" hspace="77" vspace="10"></p> |
---|
| 31 | <p>Geometric programming solvers are capable of |
---|
| 32 | solving a sub-class of geometric problems where <b>c<font face="Times New Roman">≥0</font></b> |
---|
| 33 | with the additional constraint <b>t<font face="Times New Roman">≥0, </font> |
---|
| 34 | </b>so called posynomial geometric programming. The following example is |
---|
| 35 | taken from the <a href="solvers.htm#mosek">MOSEK</a> manual. (note, |
---|
| 36 | the positivity constraint on <b><font face="Times New Roman">t </font></b> |
---|
| 37 | will be added automatically)</p> |
---|
| 38 | <table cellPadding="10" width="100%"> |
---|
| 39 | <tr> |
---|
| 40 | <td class="xmpcode"> |
---|
| 41 | <pre>t1 = sdpvar(1,1); |
---|
| 42 | t2 = sdpvar(1,1); |
---|
| 43 | t3 = sdpvar(1,1); |
---|
| 44 | obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3); |
---|
| 45 | F = set((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 < 1); |
---|
| 46 | solvesdp(F,obj);</pre> |
---|
| 47 | </td> |
---|
| 48 | </tr> |
---|
| 49 | </table> |
---|
| 50 | <p>If the geometric program violates the posynomial assumption, an error |
---|
| 51 | will be issued.</p> |
---|
| 52 | <table cellPadding="10" width="100%"> |
---|
| 53 | <tr> |
---|
| 54 | <td class="xmpcode"> |
---|
| 55 | <pre>solvesdp(F + set(t1-t2 < 1),obj) |
---|
| 56 | Warning: Solver not applicable |
---|
| 57 | <font color="#000000"> ans = |
---|
| 58 | yalmiptime: 0.0600 |
---|
| 59 | solvertime: 0 |
---|
| 60 | info: 'Solver not applicable' |
---|
| 61 | problem: -4</font></pre> |
---|
| 62 | </td> |
---|
| 63 | </tr> |
---|
| 64 | </table> |
---|
| 65 | <p>YALMIP will automatically convert some simple violations of the |
---|
| 66 | posynomial assumptions, such as lower bounds on monomial terms and |
---|
| 67 | maximization of negative monomials. The following small program maximizes |
---|
| 68 | the volume of an open box, under constraints on the floor and wall area, |
---|
| 69 | and constraints on the relation between the height, width and depth |
---|
| 70 | (example from |
---|
| 71 | <a href="readmore.htm#BOYDETAL2">[S. Boyd, S. Kim, L. Vandenberghe, A. Hassibi]</a> |
---|
| 72 | ).</p> |
---|
| 73 | <table cellPadding="10" width="100%"> |
---|
| 74 | <tr> |
---|
| 75 | <td class="xmpcode"> |
---|
| 76 | <pre>sdpvar h w d |
---|
| 77 | |
---|
| 78 | Awall = 1; |
---|
| 79 | Afloor = 1; |
---|
| 80 | |
---|
| 81 | F = set(0.5 < h/w < 2) + set(0.5 < d/w < 2); |
---|
| 82 | F = F + set(2*(h*w+h*d) < Awall) + set(w*d < Afloor); |
---|
| 83 | |
---|
| 84 | solvesdp(F,-(h*w*d))</pre> |
---|
| 85 | </td> |
---|
| 86 | </tr> |
---|
| 87 | </table> |
---|
| 88 | <p>The posynomial geometric programming problem is not convex in its |
---|
| 89 | standard formulation. Hence, if a general nonlinear solver is applied to |
---|
| 90 | the problem, it will typically fail. However, by performing a suitable |
---|
| 91 | logarithmic variable transformation, the problem is rendered convex. |
---|
| 92 | YALMIP has built-in support for performing this variable change, and solve |
---|
| 93 | the problem using the nonlinear solver |
---|
| 94 | <a href="solvers.htm#fmincon">fmincon</a>. To invoke this module in |
---|
| 95 | YALMIP, use the solver |
---|
| 96 | tag <code>'fmincon-geometric'.</code>Note that this feature mainly is intended for the |
---|
| 97 | <a href="solvers.htm#fmincon">fmincon</a> solver in the MathWorks Optimization Toolbox. |
---|
| 98 | It may work in the |
---|
| 99 | <a href="solvers.htm#fmincon">fmincon</a> solver in |
---|
| 100 | <a target="_blank" href="http://tomlab.biz">TOMLAB</a>, but this has not |
---|
| 101 | been tested to any larger extent.</p> |
---|
| 102 | <table cellPadding="10" width="100%"> |
---|
| 103 | <tr> |
---|
| 104 | <td class="xmpcode"> |
---|
| 105 | <pre>t1 = sdpvar(1,1); |
---|
| 106 | t2 = sdpvar(1,1); |
---|
| 107 | t3 = sdpvar(1,1); |
---|
| 108 | obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3); |
---|
| 109 | F = set((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 < 1); |
---|
| 110 | solvesdp(F,obj,sdpsettings('solver','fmincon-geometric'));</pre> |
---|
| 111 | </td> |
---|
| 112 | </tr> |
---|
| 113 | </table> |
---|
| 114 | <p> |
---|
| 115 | <img border="0" src="exclamationmark.jpg" align="left" width="16" height="16"> The current |
---|
| 116 | version of YALMIP has a bug that may cause problems if you have convex |
---|
| 117 | quadratic constraints. To avoid this problem, use <code> |
---|
| 118 | sdpsettings('convertconvexquad',0)</code>. To avoid some other known |
---|
| 119 | issues, explicitly tell YALMIP that the |
---|
| 120 | problem is a geometric problem by specifying the solver to <code>'gpposy'</code>, <code>'mosek-geometric'</code> |
---|
| 121 | or <code>'fmincon-geometric'</code>.</p> |
---|
| 122 | <p> |
---|
| 123 | <img border="0" src="exclamationmark.jpg" align="left" width="16" height="16"> |
---|
| 124 | Never use the commands <b>sqrt</b> and <b>cpower</b> when working with |
---|
| 125 | geometric programs, i.e. always use the ^ operator. The reason is |
---|
| 126 | implementation issues in YALMIP. The commands <b>sqrt</b> and <b>cpower</b> |
---|
| 127 | are meant to be used in optimization problems where a conic model is |
---|
| 128 | derived using convexity propagation, see <a href="extoperators.htm"> |
---|
| 129 | nonlinear operators</a>.</p> |
---|
| 130 | <h3>Generalized geometric programming</h3> |
---|
| 131 | <p>Some geometric programs, although not given in standard form, can still |
---|
| 132 | be solved using a standard geometric programming solver after some some |
---|
| 133 | additional variables and constraints have been introduced. YALMIP has |
---|
| 134 | built-in support for some of these conversion. |
---|
| 135 | </p> |
---|
| 136 | <p>To begin with, nonlinear operators can be used also in geometric |
---|
| 137 | programs, as in any other optimization problems (as long as YALMIP is |
---|
| 138 | capable of proving convexity, see the <a href="extoperators.htm">nonlinear |
---|
| 139 | operator examples</a>)</p> |
---|
| 140 | <table cellPadding="10" width="100%"> |
---|
| 141 | <tr> |
---|
| 142 | <td class="xmpcode"> |
---|
| 143 | <pre>t1 = sdpvar(1,1); |
---|
| 144 | t2 = sdpvar(1,1); |
---|
| 145 | t3 = sdpvar(1,1); |
---|
| 146 | obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3); |
---|
| 147 | |
---|
| 148 | F = set(max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) < min(t1,t2)); |
---|
| 149 | solvesdp(F,obj);</pre> |
---|
| 150 | </td> |
---|
| 151 | </tr> |
---|
| 152 | </table> |
---|
| 153 | <p>Powers of posynomials are allowed in generalized geometric |
---|
| 154 | programs. YALMIP will automatically take care of this and convert the |
---|
| 155 | problems to a standard geometric programs. Note that the power has to be |
---|
| 156 | positive if used on the left-hand side of a <, and negative otherwise.</p> |
---|
| 157 | <table cellPadding="10" width="100%"> |
---|
| 158 | <tr> |
---|
| 159 | <td class="xmpcode"> |
---|
| 160 | <pre>t1 = sdpvar(1,1); |
---|
| 161 | t2 = sdpvar(1,1); |
---|
| 162 | t3 = sdpvar(1,1); |
---|
| 163 | obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3); |
---|
| 164 | |
---|
| 165 | F = set(max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) < min((t1+0.5*t2)^-1,t2)); |
---|
| 166 | F = F + set((2*t1+3*t2^-1)^0.5 < 2); |
---|
| 167 | |
---|
| 168 | solvesdp(F,obj);</pre> |
---|
| 169 | </td> |
---|
| 170 | </tr> |
---|
| 171 | </table> |
---|
| 172 | <p>To understand how a generalized geometric program can be converted to a |
---|
| 173 | standard geometric program. the reader is referred to |
---|
| 174 | <a href="readmore.htm#BOYDETAL2">[S. Boyd, S. Kim, L. Vandenberghe, A. Hassibi]</a> |
---|
| 175 | <h3><a name="migp"></a>Mixed integer geometric programming</h3> |
---|
| 176 | <p>The branch and bound solver in YALMIP is built in a modular fashion that makes it |
---|
| 177 | possible to solve almost arbitrary convex mixed integer programs. The |
---|
| 178 | following example is taken from |
---|
| 179 | <a href="readmore.htm#BOYDETAL2">[S. Boyd, S. Kim, L. Vandenberghe, A. Hassibi]</a>. |
---|
| 180 | To begin with, define the data for the example.<table cellPadding="10" width="100%" id="table2"> |
---|
| 181 | <tr> |
---|
| 182 | <td class="xmpcode"> |
---|
| 183 | <pre>a = ones(7,1); |
---|
| 184 | alpha = ones(7,1); |
---|
| 185 | beta = ones(7,1); |
---|
| 186 | gamma = ones(7,1); |
---|
| 187 | f = [1 0.8 1 0.7 0.7 0.5 0.5]'; |
---|
| 188 | e = [1 2 1 1.5 1.5 1 2]'; |
---|
| 189 | Cout6 = 10; |
---|
| 190 | Cout7 = 10;</pre> |
---|
| 191 | </td> |
---|
| 192 | </tr> |
---|
| 193 | </table> |
---|
| 194 | <p>Introduce symbolic expressions used in the model.</p> |
---|
| 195 | <table cellPadding="10" width="100%" id="table3"> |
---|
| 196 | <tr> |
---|
| 197 | <td class="xmpcode"> |
---|
| 198 | <pre>x = sdpvar(7,1);</pre> |
---|
| 199 | <pre>C = alpha+beta.*x; |
---|
| 200 | A = sum(a.*x); |
---|
| 201 | P = sum(f.*e.*x); |
---|
| 202 | R = gamma./x;</pre> |
---|
| 203 | <pre>D1 = R(1)*(C(4)); |
---|
| 204 | D2 = R(2)*(C(4)+C(5)); |
---|
| 205 | D3 = R(3)*(C(5)+C(7)); |
---|
| 206 | D4 = R(4)*(C(6)+C(7)); |
---|
| 207 | D5 = R(5)*(C(7)); |
---|
| 208 | D6 = R(6)*Cout6; |
---|
| 209 | D7 = R(7)*Cout7;</pre> |
---|
| 210 | </td> |
---|
| 211 | </tr> |
---|
| 212 | </table> |
---|
| 213 | <p>The objective function and constraints (notice the use of the |
---|
| 214 | <a href="extoperators.htm">nonlinear operator</a> <b>max</b> in the |
---|
| 215 | objective).</p> |
---|
| 216 | <table cellPadding="10" width="100%" id="table4"> |
---|
| 217 | <tr> |
---|
| 218 | <td class="xmpcode"> |
---|
| 219 | <pre>% Constraints |
---|
| 220 | F = set(x > 1) + set(P < 20) + set(A < 100);</pre> |
---|
| 221 | <pre>% Objective |
---|
| 222 | D = max((D1+D4+D6),(D1+D4+D7),(D2+D4+D6),(D2+D4+D7),(D2+D5+D7),(D3+D5+D6),(D3+D7));</pre> |
---|
| 223 | </td> |
---|
| 224 | </tr> |
---|
| 225 | </table> |
---|
| 226 | <p>Solve!</p> |
---|
| 227 | <table cellPadding="10" width="100%" id="table5"> |
---|
| 228 | <tr> |
---|
| 229 | <td class="xmpcode"> |
---|
| 230 | <pre>solvesdp(F+set(integer(x)),D) |
---|
| 231 | double(D) |
---|
| 232 | <font color="#000000">ans = |
---|
| 233 | 8.3333</font></pre> |
---|
| 234 | </td> |
---|
| 235 | </tr> |
---|
| 236 | </table> |
---|
| 237 | <p>An alternative model is discussed in the paper, and is just as easy |
---|
| 238 | to define.</p> |
---|
| 239 | <table cellPadding="10" width="100%" id="table1"> |
---|
| 240 | <tr> |
---|
| 241 | <td class="xmpcode"> |
---|
| 242 | <pre>T1 = D1; |
---|
| 243 | T2 = D2; |
---|
| 244 | T3 = D3; |
---|
| 245 | T4 = max(T1,T2)+D4; |
---|
| 246 | T5 = max(T2,T3) + D5; |
---|
| 247 | T6 = T4 + D6; |
---|
| 248 | T7 = max(T3,T4,T5) + D7; |
---|
| 249 | D = max(T6,T7); |
---|
| 250 | solvesdp(F+set(integer(x)),D) |
---|
| 251 | double(D) |
---|
| 252 | <font color="#000000">ans = |
---|
| 253 | 8.3333</font></pre> |
---|
| 254 | </td> |
---|
| 255 | </tr> |
---|
| 256 | </table> |
---|
| 257 | </td> |
---|
| 258 | </tr> |
---|
| 259 | </table> |
---|
| 260 | <p> </div> |
---|
| 261 | |
---|
| 262 | </body> |
---|
| 263 | |
---|
| 264 | </html> |
---|