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

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

Added original make3d
File size: 10.0 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 : 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">&#8805;0</font></b> 
33      with the additional constraint <b>t<font face="Times New Roman">&#8805;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);
42t2 = sdpvar(1,1);
43t3 = sdpvar(1,1);
44obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
45F = set((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 &lt; 1);
46solvesdp(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 &lt; 1),obj)
56Warning: 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
78Awall  = 1;
79Afloor = 1;
80
81F = set(0.5 &lt; h/w &lt; 2) + set(0.5 &lt; d/w &lt; 2);
82F = F + set(2*(h*w+h*d) &lt; Awall) + set(w*d &lt; Afloor);
83
84solvesdp(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);
106t2 = sdpvar(1,1);
107t3 = sdpvar(1,1);
108obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
109F = set((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1 &lt; 1);
110solvesdp(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);
144t2 = sdpvar(1,1);
145t3 = sdpvar(1,1);
146obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
147
148F = set(max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) &lt; min(t1,t2));
149solvesdp(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 &lt;, and negative otherwise.</p>
157      <table cellPadding="10" width="100%">
158        <tr>
159          <td class="xmpcode">
160          <pre>t1 = sdpvar(1,1);
161t2 = sdpvar(1,1);
162t3 = sdpvar(1,1);
163obj = (40*t1^-1*t2^-0.5*t3^-1)+(20*t1*t3)+(40*t1*t2*t3);
164
165F = set(max((1/3)*t1^-2*t2^-2+(4/3)*t2^0.5*t3^-1,0.25*t1*t2) &lt; min((t1+0.5*t2)^-1,t2));
166F = F + set((2*t1+3*t2^-1)^0.5 &lt; 2);
167
168solvesdp(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&nbsp;
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);
184alpha = ones(7,1);
185beta  = ones(7,1);
186gamma = ones(7,1);
187f = [1 0.8 1 0.7 0.7 0.5 0.5]';
188e = [1 2 1 1.5 1.5 1 2]';
189Cout6 = 10;
190Cout7 = 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;
200A = sum(a.*x);
201P = sum(f.*e.*x);
202R = gamma./x;</pre>
203                        <pre>D1 = R(1)*(C(4));
204D2 = R(2)*(C(4)+C(5));
205D3 = R(3)*(C(5)+C(7));
206D4 = R(4)*(C(6)+C(7));
207D5 = R(5)*(C(7));
208D6 = R(6)*Cout6;
209D7 = 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
220F = set(x &gt; 1) + set(P &lt; 20) + set(A &lt; 100);</pre>
221                        <pre>% Objective
222D = 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)
231double(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;
243T2 = D2;
244T3 = D3;
245T4 = max(T1,T2)+D4;
246T5 = max(T2,T3) + D5;
247T6 = T4 + D6;
248T7 = max(T3,T4,T5) + D7;
249D = max(T6,T7);
250solvesdp(F+set(integer(x)),D)
251double(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>&nbsp;</div>
261
262</body>
263
264</html>
Note: See TracBrowser for help on using the repository browser.