📄 globalbmi.htm
字号:
solvesdp(F,t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : -9.565E-001 2.22 -1.000E+000 2 Improved solution
2 : -9.565E-001 2.22 -1.000E+000 1 Infeasible
3 : -9.565E-001 2.22 -1.000E+000 2
4 : -9.565E-001 2.22 -1.000E+000 3
5 : -9.565E-001 0.24 -9.613E-001 2 Infeasible
+ 5 Finishing. Cost: -0.95653 Gap: 0.24126%</font></pre>
</td>
</tr>
</table>
<p>The constrained LQ problem in the section <a href="bmi.htm">Local BMIs</a>
can actually easily be solved to global optimality in just a couple of
iterations. For the global code to work, global lower and upper and bound on
all complicating variables (involved in nonlinear terms) must be supplied, either explicitly or implicitly in the linear
constraints. This was the case for all problems above. In this example, the variable <b>
K</b> is already bounded in
the original problem, but the elements in <b>P</b> have to be bounded
artificially. </p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>yalmip('clear')
A = [-1 2;-3 -4];B = [1;1];
P = sdpvar(2,2);
K = sdpvar(1,2);
F = set(P>0)+set((A+B*K)'*P+P*(A+B*K) < -eye(2)-K'*K);
F = F + set(K<0.1)+set(K>-0.1);
F = F + set(1000> P(:)>-1000)
options = sdpsettings('bmibnb.lowersolver','pensdp','bmibnb.uppersolver','penbmi');
options = sdpsettings(options,'solver','bmibnb','bmibnb.lpsolver','glpk');
options = sdpsettings(options,'verbose',2,'solver','bmibnb');
solvesdp(F,trace(P),options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : 4.834E-001 17.70 2.209E-001 2 Improved solution
2 : 4.834E-001 17.70 2.209E-001 1 Infeasible
3 : 4.834E-001 1.93 4.548E-001 2
4 : 4.834E-001 1.93 4.548E-001 1 Infeasible
5 : 4.834E-001 0.25 4.797E-001 2
+ 5 Finishing. Cost: 0.48341 Gap: 0.25032%</font></pre>
</td>
</tr>
</table>
<p>Beware, the BMI solver is absolutely not that efficient in general,
this was just a lucky case. Here is the <a href="gevp.htm">decay-rate
example</a> instead (with some additional constraints on the elements
in <b>P</b> to bound the feasible set). </p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>yalmip('clear');
A = [-1 2;-3 -4];
t = sdpvar(1,1);
P = sdpvar(2,2);
F = set(P>eye(2))+set(A'*P+P*A < -2*t*P);
F = F + set(-1e4 < P(:) < 1e4) + set(100 > t > 0) ;
options = sdpsettings('bmibnb.lowersolver','pensdp','bmibnb.uppersolver','penbmi');
options = sdpsettings(options,'solver','bmibnb','bmibnb.lpsolver','glpk');
options = sdpsettings(options,'verbose',2,'solver','bmibnb');
solvesdp(F,-t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : Inf NaN -9.965E+001 2
2 : -2.500E+000 2775.83 -9.965E+001 3 Improved solution
3 : -2.500E+000 2721.00 -9.773E+001 4
4 : -2.500E+000 2721.00 -9.773E+001 3 Infeasible
5 : -2.500E+000 2634.59 -9.471E+001 4
6 : -2.500E+000 2634.59 -9.471E+001 3 Infeasible
7 : -2.500E+000 2577.61 -9.272E+001 4
8 : -2.500E+000 2577.61 -9.272E+001 3 Infeasible
9 : -2.500E+000 2501.03 -9.004E+001 4
10 : -2.500E+000 2501.03 -9.004E+001 3 Infeasible
...
94 : -2.500E+000 4.30 -2.650E+000 49
95 : -2.500E+000 0.47 -2.516E+000 50
+ 95 Finishing. Cost: -2.5 Gap: 0.46843%</font></pre>
</td>
</tr>
</table>
<p>The linear relaxations give very poor lower bounds on this problem,
leading to poor convergence of the branching process. However, for this
particular problem, the reason is easy to find. The original BMI is
homogeneous w.r.t <b>P</b>, and to guarantee a somewhat reasonable
solution, we artificially added the constraint <b>P<font face="Tahoma">≥I</font></b>.
A better model is obtained if we instead fix the trace of <b>P</b>. This will
make the feasible set w.r.t P much smaller, but the problems are
equivalent. Note also that we no longer need any artificial constraints
on the elements in <b>P</b>.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>F = set(P>0)+set(A'*P+P*A < -2*t*P) + set(100 > t > 0) ;
F = F + set(trace(P)==1);
solvesdp(F,-t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : -2.500E+000 1396.51 -5.138E+001 2 Improved solution
2 : -2.500E+000 1396.51 -5.138E+001 1 Infeasible
3 : -2.500E+000 1.41 -2.549E+000 2
4 : -2.500E+000 1.41 -2.549E+000 1 Infeasible
5 : -2.500E+000 0.17 -2.506E+000 2
+ 5 Finishing. Cost: -2.5 Gap: 0.1746%</font></pre>
</td>
</tr>
</table>
<p>For this problem, we can easily find a very efficient additional cutting
plane. The
decay-rate BMI together with the constant trace on <b>P</b> implies <b>trace(A<sup>T</sup>P+PA)<font face="Times New Roman">≤</font>-2t</b>.
Adding this cut reduce the number of iterations needed.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>F = set(P>0)+set(A'*P+P*A < -2*t*P) + set(100 > t > 0);
F = F + set(trace(P)==1);
F = F + set(trace(A'*P+P*A)<-2*t);
solvesdp(F,-t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : -2.500E+000 26.60 -3.431E+000 2 Improved solution
2 : -2.500E+000 26.60 -3.431E+000 3
3 : -2.500E+000 0.55 -2.519E+000 2 Infeasible
+ 3 Finishing. Cost: -2.5 Gap: 0.5461%</font></pre>
</td>
</tr>
</table>
<p>
A Schur complement on the decay-rate BMI gives us yet another cut
which improves the node relaxation even more.</p><table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>F = set(P>0)+set(A'*P+P*A < -2*t*P) + set(100 > t > 0) ;
F = F + set(trace(P)==1);
F = F + set(trace(A'*P+P*A)<-2*t)
F = F + set([-A'*P-P*A P*t;P*t P*t/2]);
solvesdp(F,-t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : -2.500E+000 17.84 -3.124E+000 2 Improved solution
2 : -2.500E+000 17.84 -3.124E+000 3
3 : -2.500E+000 0.55 -2.519E+000 2 Infeasible
+ 3 Finishing. Cost: -2.5 Gap: 0.55275%</font></pre>
</td>
</tr>
</table>
<p>
By adding valid cuts, the relaxations are possibly tighter, leading to
better lower bounds. A problem however is that we add additional
burden to the local solver used for the upper bounds. The additional
cuts are redundant for the local solver, and most likely detoriate the
performance. To avoid this, cuts can be exlicitely specified by using
the command <a target="topic" href="reference.htm#cut">cut</a>.
Constraints defined using this command (instead of
<a target="topic" href="reference.htm#set">set</a>) will only be used
in the solution of relaxations, and omitted when the local solver is
called. </p><table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>F = set(P>0)+set(A'*P+P*A < -2*t*P) + set(100 > t > 0) ;
F = F + set(trace(P)==1);
F = F + cut(trace(A'*P+P*A)<-2*t);
F = F + cut([-A'*P-P*A P*t;P*t P*t/2]);
solvesdp(F,-t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : -2.500E+000 17.84 -3.124E+000 2 Improved solution
2 : -2.500E+000 17.84 -3.124E+000 3
3 : -2.500E+000 0.55 -2.519E+000 2 Infeasible
+ 3 Finishing. Cost: -2.5 Gap: 0.55275%</font></pre>
</td>
</tr>
</table>
<p>
Upper bounds were obtained above by solving the BMI locally using
<a href="solvers.htm#penbmi">PENBMI</a>. If no local BMI solver is available, an alternative is to
check if the relaxed solution is a feasible solution. If so,
the upper bound can be updated. This scheme
can be obtained by specifying <code>'none'</code> as the upper bound solver.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>options = sdpsettings(options,'bmibnb.uppersolver','none');
F = set(P>0)+set(A'*P+P*A < -2*t*P) + set(100 > t > 0) ;
F = F + set(trace(P)==1);
F = F + cut(trace(A'*P+P*A)<-2*t);
F = F + cut([-A'*P-P*A P*t;P*t P*t/2]);
solvesdp(F,-t,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : pensdp
* Upper solver : none
Node Upper Gap(%) Lower Open
1 : Inf NaN -3.124E+000 2
2 : Inf NaN -3.124E+000 3
3 : -9.045E-001 104.47 -2.894E+000 4 Improved solution
4 : -9.045E-001 104.47 -2.894E+000 5
5 : -1.467E+000 52.43 -2.761E+000 4 Improved solution
6 : -1.467E+000 52.43 -2.761E+000 5
7 : -1.831E+000 29.87 -2.677E+000 4 Improved solution
8 : -1.831E+000 29.87 -2.677E+000 5
9 : -2.071E+000 17.77 -2.616E+000 4 Improved solution
10 : -2.071E+000 17.77 -2.616E+000 5
11 : -2.229E+000 10.46 -2.567E+000 4 Improved solution
12 : -2.229E+000 10.46 -2.567E+000 5
13 : -2.332E+000 5.70 -2.522E+000 4 Improved solution
14 : -2.332E+000 5.70 -2.522E+000 5
15 : -2.397E+000 3.25 -2.508E+000 4 Improved solution
16 : -2.397E+000 3.25 -2.508E+000 5
17 : -2.435E+000 2.01 -2.504E+000 4 Improved solution
18 : -2.435E+000 2.01 -2.504E+000 5
19 : -2.459E+000 1.25 -2.503E+000 4 Improved solution
20 : -2.459E+000 1.25 -2.503E+000 5
21 : -2.478E+000 0.70 -2.502E+000 4 Improved solution
+ 21 Finishing. Cost: -2.4776 Gap: 0.69631%</font></pre>
</td>
</tr>
</table>
<p>
More examples can be found in <a href="reference.htm#yalmipdemo">
yalmipdemo</a>.<br>
<br>
<img border="0" src="demoicon.gif" width="16" height="16"> The global
branch and bound algorithm will hopefully be improved upon
significantly in future releases. This includes both algorithmic
improvements and code optimization. If you have any ideas, you are welcome to contribute.</td>
</tr>
</table>
</div>
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -