Global solution of polynomial programs


This example requires the solver PENBMI (Well, actually, not really. See the last example below). Moreover, the example below is hard-coded to use PENSDP and GLPK.

Global solutions! Well, almost... don't expect too much at this stage. The functionality described here is at an early development phase (read hack...) The code seem to be fairly robust on small bilinear and indefinite quadratic optimization problems, and a couple of small problems with bilinear matrix inequalities have been solved successfully.

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 PENBMI. A more detailed description of the algorithm will be presented in the future.

For a short introduction to the parameters available in the solver, see help bmibnb.

Nonconvex quadratic programming

The first example is a problem with a concave quadratic constraint (this is the example addressed in the moment relaxation section). Three different optimization problems are solved during the branching: Upper bounds using a local nonlinear solver (bmibnb.uppersolver), lower bounds (bmibnb.lowersolver) and bound tightening using linear programming (bmibnb.lpsolver).

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);
*****************************************************************************************************
#node          Was' up                         gap      upper   current    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1                                       100.00%    0.0000   -6.0000   -6.0000    1    1  0.0%  
+   2                                       100.00%    0.0000   -6.0000   -6.0000    1    2  21.7%  
+   3 Improved upper bound                   33.33%   -4.0000   -4.4133   -6.0000    2    3  84.3%  
+   4                                        33.33%   -4.0000   -5.8177   -6.0000    2    4  78.3%  
+   5 Infeasible during box-reduction        31.24%   -4.0000       Inf   -5.8177    3    3  99.6%  
+   6                                        31.24%   -4.0000   -5.5468   -5.8177    3    4  38.3%  
+   7 Infeasible during box-reduction        27.89%   -4.0000       Inf   -5.5468    4    3  93.2%  
+   8                                        27.89%   -4.0000   -5.2523   -5.5468    4    4  48.4%  
+   9 Infeasible during box-reduction        23.84%   -4.0000       Inf   -5.2523    5    3  96.5%  
+  10                                        23.84%   -4.0000   -4.6729   -5.2523    5    4  55.3%  
+  11 Infeasible during box-reduction        14.40%   -4.0000       Inf   -4.6729    6    3  97.5%  
+  12 Infeasible during box-reduction        14.40%   -4.0000       Inf   -4.6729    6    2  45.2%  
+  13                                         9.36%   -4.0000   -4.0000   -4.4133    2    1  100.0%  
+  14 Infeasible during box-reduction         9.36%   -4.0000       Inf   -4.4133    2    0  2.1%  
+  15                                         0.00%   -4.0000   -4.0000   -4.4133    0    0  100.0%  
*****************************************************************************************************
+  15 Finishing.  Cost: -4 Gap: 0%
*****************************************************************************************************

The second example is a slightly larger problem. It was originally a problem with a concave quadratic objective function, but the global code in YALMIP currently assumes a linear objectives, so a new variable and constraint has been introduced to transform the problem using an epigraph formulation. The problem is easily solved in the root node to a gap of less than 1%.

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);
t = 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);
F = F + set(p<t)+set(-1000<t<1000);
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,t,options);

*****************************************************************************************************
#node          Was' up                         gap      upper   current    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                    0.96%  -310.0000  -313.0000  -313.0000    1    1  6.8%  
*****************************************************************************************************
+   1 Finishing.  Cost: -310 Gap: 0.95847%
*****************************************************************************************************

Quadratic equality constraints can also be dealt with. This can be used for, e.g., boolean programming.

n = 10;
x = sdpvar(n,1);
t = sdpvar(1,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) + set(objective < t);
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,t,options);
*****************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                   31.42%   -2.0704   -3.0191   -3.0191    1    1  100.0%  
+   2                                        31.42%   -2.0704   -2.4595   -3.0191    1    2  100.0%  
+   3 Improved upper bound                   25.78%   -2.2409   -3.0191   -3.0191    2    3  100.0%  
+   4 Improved upper bound                    0.00%   -3.0191   -3.0191   -3.0191    2    2  100.0%  
*****************************************************************************************************
+   4 Finishing.  Cost: -3.0191 Gap: 5.6525e-007%
*****************************************************************************************************

Nonconvex polynomial programming

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 x3y2 will be replaced with the the variable w and the constraints w == uv, u == zx, z == x2, v == y2. The is done automatically if the global solver, or PENBMI, 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.

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,ops)
******************************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk     Memory Vol-red
******************************************************************************************************************
+   1                                          NaN%       Inf  -29.9020  -29.9020    1    1     0.19MB    79.3%  
+   2 Infeasible during box-reduction          NaN%       Inf       Inf  -29.9020    1    0     0.20MB     0.0%  
+   3                                          NaN%       Inf  -27.6344  -27.6344    2    1     0.20MB    25.5%  
+   4                                          NaN%       Inf   20.9234  -27.6344    2    2     0.20MB    23.5%  
+   5                                          NaN%       Inf  -15.8410  -15.8410    3    3     0.20MB    59.5%  
+   6                                          NaN%       Inf    7.7090  -15.8410    3    4     0.20MB    16.1%  
+   7                                          NaN%       Inf   -8.3502   -8.3502    4    5     0.20MB    54.5%  
+   8                                          NaN%       Inf    3.1171   -8.3502    4    6     0.20MB     8.8%  
+   9 Improved upper bound                  115.21%   -1.7100   -4.8322   -4.8322    5    1     0.20MB    43.4%  
+  10 Infeasible during box-reduction       115.21%   -1.7100       Inf   -4.8322    5    0     0.20MB    58.9%  
+  11                                         0.00%   -1.7100   -1.7100   -1.7100    6    1     0.20MB    97.3%  
******************************************************************************************************************
+  11 Finishing.  Cost: -1.71 Gap: 0.0016505%
******************************************************************************************************************

Nonconvex semidefinite programming

The following problem is a classical BMI problem

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');
solvesdp(F,t,options);
*****************************************************************************************************
#node          Was' up                         gap      upper   current    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1                                          Inf%       Inf   -1.0000   -1.0000    1    1  0.0%  
+   2                                          Inf%       Inf   -0.9638   -1.0000    1    2  6.5%  
+   3                                          Inf%       Inf   -1.0000   -1.0000    2    3  36.8%  
+   4                                          Inf%       Inf   -0.9907   -1.0000    2    4  38.8%  
+   5                                          Inf%       Inf    0.9456   -0.9907    3    5  3.2%  
+   6 Improved upper bound                   76.26%   -0.2352   -0.2352   -0.9907    3    4  0.0%  
+   7 Infeasible during box-reduction        75.60%   -0.2352       Inf   -0.9638    2    3  46.0%  
+   8                                        75.60%   -0.2352   -0.7039   -0.9638    2    4  25.8%  
+   9 Improved upper bound                    0.75%   -0.9565   -0.9638   -0.9638    3    1  61.1%  
*****************************************************************************************************
+   9 Finishing.  Cost: -0.95653 Gap: 0.75172%
*****************************************************************************************************

The constrained LQ problem in the section Local BMIs 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 K is already bounded in the original problem, but the elements in P have to be bounded artificially.

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);
*****************************************************************************************************
#node          Was' up                         gap      upper   current    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                  116.61%    0.4834    0.2232    0.2232    1    1  0.0%  
+   2                                       116.61%    0.4834    0.4824    0.2232    1    2  100.0%  
+   3 Infeasible node                         0.20%    0.4834       Inf    0.4824    2    1  100.0%  
*****************************************************************************************************
+   3 Finishing.  Cost: 0.48341 Gap: 0.20057%
*****************************************************************************************************

Beware, the BMI solver is absolutely not that efficient in general, this was just a lucky case. Here is the decay-rate example instead (with some additional constraints on the elements in P to bound the feasible set).

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);
*****************************************************************************************************
#node          Was' up                         gap      upper   current    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                   97.49%   -2.5000  -99.6541  -99.6541    1    1  0.0%  
+   2                                        97.49%   -2.5000   -4.7453  -99.6541    1    2  91.3%  
+   3                                        97.44%   -2.5000  -97.6512  -97.6512    2    3  13.6%  
+   4                                        97.44%   -2.5000   -2.9813  -97.6512    2    4  98.9%  
+   5                                        97.29%   -2.5000  -92.3533  -92.3533    3    5  61.2%  
+   6                                        97.29%   -2.5000   -3.4232  -92.3533    3    6  96.8%  
+   7                                        97.18%   -2.5000  -88.7931  -88.7931    4    7  32.0%  
+   8                                        97.18%   -2.5000   -3.4227  -88.7931    4    8  96.7%  
+   9                                        97.04%   -2.5000  -84.4630  -84.4630    5    9  33.1%  
+  10                                        97.04%   -2.5000   -3.4223  -84.4630    5   10  96.6% 
.... 
+  84                                        24.19%   -2.5000   -2.5025   -3.2978   19   82  80.5%  
+  85                                        23.69%   -2.5000   -2.5086   -3.2761    3   83  49.6%  
+  86                                        23.69%   -2.5000   -2.5001   -3.2761    3   84  99.3%  
+  87 Infeasible node                        22.72%   -2.5000       Inf   -3.2349   20   83  56.5%  
+  88                                        22.72%   -2.5000   -2.5002   -3.2349   20   84  95.8%  
+  89 Poor lower bound                       16.14%   -2.5000   -2.4988   -2.9813    3   83  100.0%  
+  90                                        16.14%   -2.5000   -2.5059   -2.9813    3   84  63.0%  
+  91 Infeasible node                        14.47%   -2.5000       Inf   -2.9229   26   83  45.1%  
+  92                                        14.47%   -2.5000   -2.5002   -2.9229   26   84  96.4%  
+  93                                        11.07%   -2.5000   -2.6857   -2.8111    5   85  50.1%  
+  94 Infeasible node                        11.07%   -2.5000       Inf   -2.8111    5   84  53.3%  
+  95                                        11.05%   -2.5000   -2.5039   -2.8107    6   85  52.0%  
+  96 Infeasible node                        11.05%   -2.5000       Inf   -2.8107    6   84  53.4%  
+  97 Infeasible node                        11.04%   -2.5000       Inf   -2.8103    7   83  51.9%  
+  98 Infeasible node                        11.04%   -2.5000       Inf   -2.8103    7   82  53.4%  
+  99                                        11.02%   -2.5000   -2.5039   -2.8097    8   83  52.0%  
+ 100 Infeasible node                        11.02%   -2.5000       Inf   -2.8097    8   82  53.4%  
*****************************************************************************************************
+ 100 Finishing.  Cost: -2.5 Gap: 11.0239%
*****************************************************************************************************

The linear relaxations give very poor lower bounds on this problem, leading to poor convergence of the branching process. After 100 iterations, we still have a significant gap. However, for this particular problem, the reason is easy to find. The original BMI is homogeneous w.r.t P, and to guarantee a somewhat reasonable solution, we artificially added the constraint P≥I. A better model is obtained if we instead fix the trace of P. 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 P.

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);
*****************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                 1396.51%   -2.5000  -51.3778  -51.3778    1    1  0.0%  
+   2 Infeasible during box-reduction      1396.51%   -2.5000       Inf  -51.3778    1    0  0.0%  
+   3                                      1396.51%   -2.5000   -2.5493  -51.3778    2    1  86.0%  
+   4 Infeasible during box-reduction         1.41%   -2.5000       Inf   -2.5493    2    0  0.0%  
+   5                                         1.41%   -2.5000   -2.5061   -2.5493    3    1  36.3%  
+   6                                         0.17%   -2.5000   -2.5015   -2.5061    3    2  54.5%  
*****************************************************************************************************
+   6 Finishing.  Cost: -2.5 Gap: 0.1746%
*****************************************************************************************************

For this problem, we can easily find a very efficient additional cutting plane. The decay-rate BMI together with the constant trace on P implies trace(ATP+PA)-2t. Adding this cut reduce the number of iterations needed.

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);
*****************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                   26.60%   -2.5000   -3.4311   -3.4311    1    1  0.0%  
+   2                                        26.60%   -2.5000   -2.5191   -3.4311    1    2  86.5%  
+   3 Infeasible during box-reduction         0.55%   -2.5000       Inf   -2.5191    2    1  0.0%  
*****************************************************************************************************
+   3 Finishing.  Cost: -2.5 Gap: 0.5461%
*****************************************************************************************************

A Schur complement on the decay-rate BMI gives us yet another cut which improves the node relaxation even more.

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);
*****************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                   17.84%   -2.5000   -3.1244   -3.1244    1    1  0.0%  
+   2                                        17.84%   -2.5000   -2.5193   -3.1244    1    2  79.7%  
+   3 Infeasible during box-reduction         0.55%   -2.5000       Inf   -2.5193    2    1  0.0%  
*****************************************************************************************************
+   3 Finishing.  Cost: -2.5 Gap: 0.55276%
*****************************************************************************************************

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 cut. Constraints defined using this command (instead of set) will only be used in the solution of relaxations, and omitted when the local solver is called.

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);
*****************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1 Improved upper bound                   17.84%   -2.5000   -3.1244   -3.1244    1    1  0.0%  
+   2                                        17.84%   -2.5000   -2.5193   -3.1244    1    2  79.7%  
+   3 Infeasible during box-reduction         0.55%   -2.5000       Inf   -2.5193    2    1  0.0%  
*****************************************************************************************************
+   3 Finishing.  Cost: -2.5 Gap: 0.55276%
*****************************************************************************************************

Upper bounds were obtained above by solving the BMI locally using PENBMI. 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 'none' as the upper bound solver.

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);
*****************************************************************************************************
#node          Was' up                         gap      upper      node    lower  dpth  stk Vol-red
*****************************************************************************************************
+   1                                          NaN%       Inf   -3.1244   -3.1244    1    1  0.0%  
+   2                                          NaN%       Inf   -2.8942   -3.1244    1    2  4.6%  
+   3 Improved upper bound                  104.47%   -0.9045   -0.9045   -2.8942    2    3  0.0%  
+   4                                       104.47%   -0.9045   -2.7609   -2.8942    2    4  3.6%  
+   5 Improved upper bound                   52.43%   -1.4673   -1.4673   -2.7609    3    3  0.0%  
+   6                                        52.43%   -1.4673   -2.6769   -2.7609    3    4  7.4%  
+   7 Improved upper bound                   29.87%   -1.8312   -1.8312   -2.6769    4    3  0.0%  
+   8                                        29.87%   -1.8312   -2.6162   -2.6769    4    4  23.1%  
+   9 Improved upper bound                   17.77%   -2.0706   -2.0706   -2.6162    5    3  0.4%  
+  10                                        17.77%   -2.0706   -2.5508   -2.6162    5    4  13.5%  
+  11 Infeasible node                        15.64%   -2.0706       Inf   -2.5508    6    3  36.7%  
+  12                                        15.64%   -2.0706   -2.5239   -2.5508    6    4  20.3%  
+  13 Improved upper bound                    9.66%   -2.2135   -2.2135   -2.5239    7    3  4.8%  
+  14                                         9.66%   -2.2135   -2.5141   -2.5239    7    4  15.8%  
+  15 Improved upper bound                    6.35%   -2.3042   -2.3042   -2.5141    8    3  2.2%  
+  16                                         6.35%   -2.3042   -2.4746   -2.5141    8    4  2.0%  
+  17                                         6.01%   -2.3042   -2.5028   -2.5028    9    5  23.5%  
+  18                                         6.01%   -2.3042   -2.5011   -2.5028    9    6  21.8%  
+  19 Improved upper bound                    4.33%   -2.3558   -2.3558   -2.5011   10    5  0.0%  
+  20                                         4.33%   -2.3558   -2.5010   -2.5011   10    6  0.1%  
+  21 Improved upper bound                    3.18%   -2.3932   -2.3932   -2.5010   11    5  0.0%  
+  22                                         3.18%   -2.3932   -2.5010   -2.5010   11    6  0.0%  
+  23 Improved upper bound                    2.33%   -2.4211   -2.4211   -2.5010   12    5  0.0%  
+  24                                         2.33%   -2.4211   -2.5005   -2.5010   12    6  0.0%  
+  25 Infeasible node                         2.32%   -2.4211       Inf   -2.5005   13    5  0.0%  
+  26                                         2.32%   -2.4211   -2.5005   -2.5005   13    6  0.0%  
+  27 Improved upper bound                    1.70%   -2.4420   -2.4420   -2.5005   14    5  0.0%  
+  28                                         1.70%   -2.4420   -2.4479   -2.5005   14    6  0.0%  
+  29                                         1.70%   -2.4420   -2.5004   -2.5004   15    7  0.0%  
+  30                                         1.70%   -2.4420   -2.5004   -2.5004   15    8  0.0%  
+  31                                         1.70%   -2.4420   -2.4544   -2.5004   16    9  0.0%  
+  32                                         1.70%   -2.4420   -2.5004   -2.5004   16   10  0.0%  
+  33 Improved upper bound                    1.24%   -2.4577   -2.4577   -2.5004   17    5  0.0%  
+  34                                         1.24%   -2.4577   -2.5004   -2.5004   17    6  0.0%  
+  35 Improved upper bound                    0.89%   -2.4695   -2.4695   -2.5004   18    5  0.0%  
*****************************************************************************************************
+  35 Finishing.  Cost: -2.4695 Gap: 0.89144%
*****************************************************************************************************

More examples can be found in yalmipdemo.

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.