📄 globalbmi.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<title>YALMIP Example : Solving BMIs globally</title>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
<meta content="Microsoft FrontPage 6.0" name="GENERATOR">
<meta name="ProgId" content="FrontPage.Editor.Document">
<link href="yalmip.css" type="text/css" rel="stylesheet">
<base target="_self">
</head>
<body leftMargin="0" topMargin="0">
<div align="left">
<table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%">
<tr>
<td width="100%" align="left" height="100%" valign="top">
<h2>Global solution of polynomial programs</h2>
<hr noShade SIZE="1">
<p>
<img border="0" src="exclamationmark.jpg" align="left" width="16" height="16">This
example requires the solver <a href="solvers.htm#penbmi">PENBMI</a> as a
local nonlinear solver (<a href="solvers.htm#fmincon">fmincon</a>
is sufficient for the first examples).
Moreover, the examples below are all coded to use <a href="solvers.htm#pensdp">PENSDP</a>
and <a href="solvers.htm#glpk">GLPK</a> for solving the relaxations.</p>
<p>Global solutions! Well, almost... don't expect too much at this stage.
The functionality described here is under development. The code
is fairly robust on small bilinear and indefinite quadratic
optimization problems, and a couple of small problems
with bilinear matrix inequalities have been solved successfully.<br>
<br>
The algorithm is based on a simple spatial branch and bound strategy,
using McCormick's convex envelopes for bounding bilinear terms. In
addition to this, LP-based bound tightening can be applied iteratively to
improve
variable bounds. Relaxed problems are solved using either an LP solver or an SDP
solver, depending on the problem, while upper bounds are found using the
local solver <a href="solvers.htm#penbmi">PENBMI</a>. A more detailed
description of the algorithm will be presented in the future.</p>
<h3>Options</h3>
<p>In the examples below, we are mainly using the default settings when solving
the problem, but there are several options that can be changed to
alter the computations. The most important are</p>
<table border="1" cellspacing="1" style="border-collapse: collapse" width="100%" bordercolor="#000000" bgcolor="#FFFFE0" id="table1">
<tr>
<td width="367"><code>sdpsettings('bmibnb.roottight',[0|1])</code></td>
<td>Improve variable bounds at root-node by performing bound
strengthening based on the full relaxed model (Can be very expensive,
but lead to improved branching)</td>
</tr>
<tr>
<td width="367"><code>sdpsettings('bmibnb.lpreduce',[0|1])</code></td>
<td>Improve variable bounds in all nodes by performing bound
strengthening using only the scalar constraints (including scalar cut
constraints) in the model (Can be very expensive, but lead to
improved branching, in particular for semidefinite problems)</td>
</tr>
<tr>
<td width="367"><code>sdpsettings('bmibnb.lowersolver', solvertag)</code></td>
<td>Solver for relaxed problems.</td>
</tr>
<tr>
<td width="367"><code>sdpsettings('bmibnb.uppersolver', solvertag)</code></td>
<td>Local solver for computing upper bounds.</td>
</tr>
<tr>
<td width="367"><code>sdpsettings('bmibnb.lpsolver', solvertag)</code></td>
<td>LP solver for bound strengthening
(only used if <code>bmibnb.lpreduce</code> is set to 1)</td>
</tr>
<tr>
<td width="367"><code>sdpsettings('bmibnb.numglobal', [int])</code></td>
<td>A major computational burden along the branching process is to
solver the upper bound problems using a local nonlinear solver. By
setting this value to a finite value, the local solver will no
longer be used when the upper bound has been improved <code>numglobal</code> times.
This option is useful if you believe your local solver quickly gives
globally optimal solutions. It can also be useful if you have a
feasible solution and just want to compute a gap. In this case, use
the <code>usex0</code> option and set <code>numglobal</code> to 0.</td>
</tr>
</table>
<h3>Nonconvex quadratic programming</h3>
<p>The first example is a problem with a concave quadratic constraint (this
is the example addressed in the <a href="moment.htm">moment
relaxation section</a>). Three different optimization problems are solved
during the branching: Upper bounds using a local nonlinear solver (<code>bmibnb.uppersolver</code>),
lower bounds (<code>bmibnb.lowersolver</code>) and bound tightening using
linear programming (<code>bmibnb.lpsolver</code>).</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>clear all
x1 = sdpvar(1,1);
x2 = sdpvar(1,1);
x3 = sdpvar(1,1);
p = -2*x1+x2-x3;
F = set(x1*(4*x1-4*x2+4*x3-20)+x2*(2*x2-2*x3+9)+x3*(2*x3-13)+24>0);
F = F + set(4-(x1+x2+x3)>0);
F = F + set(6-(3*x2+x3)>0);
F = F + set(x1>0);
F = F + set(2-x1>0);
F = F + set(x2>0);
F = F + set(x3>0);
F = F + set(3-x3>0);
options = sdpsettings('bmibnb.uppersolver','penbmi','bmibnb.lowersolver','glpk');
options = sdpsettings(options,'solver','bmibnb','bmibnb.lpsolver','glpk');
options = sdpsettings(options,'verbose',2);
solvesdp(F,p,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : glpk
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : Inf NaN -6.000E+000 2
2 : Inf NaN -6.000E+000 3
3 : -4.000E+000 40.00 -6.000E+000 4 Improved solution
4 : -4.000E+000 40.00 -6.000E+000 3 Infeasible
5 : -4.000E+000 37.98 -5.899E+000 4 Poor bound
6 : -4.000E+000 37.98 -5.899E+000 5
7 : -4.000E+000 25.80 -5.290E+000 6
8 : -4.000E+000 25.80 -5.290E+000 5 Infeasible
9 : -4.000E+000 7.08 -4.354E+000 4 Infeasible
10 : -4.000E+000 7.08 -4.354E+000 3 Infeasible
11 : -4.000E+000 0.06 -4.003E+000 4
+ 11 Finishing. Cost: -4 Gap: 0.06486%</font></pre>
</td>
</tr>
</table>
<p>The second example is a slightly larger problem indefinite quadratic
programming problem. The problem is easily solved to a gap of
less than 1%. </p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>clear all
x1 = sdpvar(1,1);
x2 = sdpvar(1,1);
x3 = sdpvar(1,1);
x4 = sdpvar(1,1);
x5 = sdpvar(1,1);
x6 = sdpvar(1,1);
p = -25*(x1-2)^2-(x2-2)^2-(x3-1)^2-(x4-4)^2-(x5-1)^2-(x6-4)^2;
F = set((x3-3)^2+x4>4)+set((x5-3)^2+x6>4);
F = F + set(x1-3*x2<2)+set(-x1+x2<2);
F = F + set(x1-3*x2 <2)+set(x1+x2>2);
F = F + set(6>x1+x2>2);
F = F + set(1<x3<5) + set(0<x4<6)+set(1<x5<5)+set(0<x6<10)+set(x1>0)+set(x2>0);
options = sdpsettings('bmibnb.uppersolver','penbmi','bmibnb.lowersolver','glpk');
options = sdpsettings(options,'solver','bmibnb','bmibnb.lpsolver','glpk');
options = sdpsettings(options,'verbose',2,'solver','bmibnb');
solvesdp(F,p,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : glpk
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : Inf NaN -3.130E+002 2
2 : -3.100E+002 0.96 -3.130E+002 3 Improved solution
+ 2 Finishing. Cost: -310 Gap: 0.96463%</font></pre>
</td>
</tr>
</table>
<p>Quadratic equality constraints can also be dealt with. This can be used
for, e.g., boolean programming. </p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>n = 10;
x = sdpvar(n,1);
Q = randn(n,n);Q = Q*Q'/norm(Q)^2;
c = randn(n,1);
objective = x'*Q*x+c'*x;
F = set(x.*(x-1)==0) + set(0<x<1);
options = sdpsettings('bmibnb.uppersolver','penbmi','bmibnb.lowersolver','glpk');
options = sdpsettings(options,'solver','bmibnb','bmibnb.lpsolver','glpk');
options = sdpsettings(options,'verbose',2,'solver','bmibnb');
solvesdp(F,objective,options);
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : glpk
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : -2.967E+000 0.00 -2.967E+000 2 Improved solution
+ 1 Finishing. Cost: -2.9671 Gap: 2.5207e-009%</font></pre>
</td>
</tr>
</table>
<h3>Nonconvex polynomial programming</h3>
<p>The global solver in YALMIP can only solve bilinear programs, but
a pre-processor is capable of transforming higher order problems to
bilinear programs. As an example, the variable <b>x<sup>3</sup>y<sup>2</sup></b>
will be replaced with the the variable <b>w</b> and the constraints
<b>w == uv</b>, <b>u == zx</b>, <b>z == x<sup>2</sup></b>, <b>v == y<sup>2</sup></b>.
The is done automatically if the global solver, or <a href="solvers.htm#penbmi">PENBMI</a>,
is called with a higher order polynomial problem. Note that this
conversion is rather inefficient, and only very small problems can
be addressed using this simple approach. Additionally, this module
has not been tested in any serious sense.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>sdpvar x y
F = set(x^3+y^5 < 5) + set(y > 0);
F = F + set(-100 < [x y] < 100) % Always bounded domain
solvesdp(F,-x,options)
<font color="#000000">* Starting YALMIP bilinear branch & bound.
* Lower solver : glpk
* Upper solver : penbmi
Node Upper Gap(%) Lower Open
1 : Inf NaN -2.990E+001 2
2 : Inf NaN -2.990E+001 1 Infeasible
3 : Inf NaN -2.763E+001 2
4 : Inf NaN -2.763E+001 3
5 : Inf NaN -1.452E+001 4
6 : Inf NaN -1.452E+001 5
7 : -1.710E+000 171.54 -6.359E+000 4 Improved solution
8 : -1.710E+000 171.54 -6.359E+000 3 Infeasible
9 : -1.710E+000 127.11 -5.155E+000 4 Poor bound
10 : -1.710E+000 127.11 -5.155E+000 3 Infeasible
11 : -1.710E+000 0.00 -1.710E+000 2 Infeasible
+ 11 Finishing. Cost: -1.71 Gap: 1.247e-005%</font></pre>
</td>
</tr>
</table>
<h3>Nonconvex semidefinite programming</h3>
<p>The following problem is a classical BMI problem</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>yalmip('clear')
x = sdpvar(1,1);
y = sdpvar(1,1);
t = sdpvar(1,1);
A0 = [-10 -0.5 -2;-0.5 4.5 0;-2 0 0];
A1 = [9 0.5 0;0.5 0 -3 ; 0 -3 -1];
A2 = [-1.8 -0.1 -0.4;-0.1 1.2 -1;-0.4 -1 0];
K12 = [0 0 2;0 -5.5 3;2 3 0];
F = lmi(x>-0.5)+lmi(x<2) + lmi(y>-3)+lmi(y<7);
F = F + lmi(A0+x*A1+y*A2+x*y*K12-t*eye(3)<0);
options = sdpsettings('bmibnb.lowersolver','pensdp','bmibnb.uppersolver','penbmi');
options = sdpsettings(options,'solver','bmibnb','bmibnb.lpsolver','glpk');
options = sdpsettings(options,'verbose',2,'solver','bmibnb');
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -