bilinear programming solved by bmibnb

[Xiaomeng AI]

We know that the bilinear problem can be solved by bmibnb. The bmibnb uses the McCormick envelope to get a LP relaxation problem and the lower bound. The lower bound problem is a LP problem which can be easily solved. However, to get the upper bound, bmibnb uses the fmincon to solve the nonconvex and nonlinear problem, which is really hard to be solved. One way to get the upper bound is bringing the value of the variable got from lower bound problem into the original bilinear problem, in which the upper bound problem is a linear problem and can be solved easily. So can bmibnb use this method? Or can we only use the branch and bound method, and define the upper bound method by ourselves?

[Johan Löfberg]

??

The upper program is a nonlinear program. If you replace the variables with the value obtained from the lower bound problem, you get an infeasible solution (if not, that solution is the optimal solution). YALMIP always checks if the lower bound solution is a solution to the original problem. If it is, it trivially exits and the problems has  been solved to optimality.

[Xiaomeng AI]

Thank you for your help! But here are still some questions:

As for the bilinear programming, if the bilinear variable is bounded, to get a upper bound, we can bring the value of bilinear variable(only the value of variable which leads to the bilinear constraints) got from the lower bound problem into the original bilinear program(in which the bilinear constraints are not considered). The effectiveness of this method has been shown in some researches and books like A Reformulation-linearization Technique for Solving Discrete and Continuous Nonconvex Problem. Maybe this method can't get a tight upper bound compared with the nonlinear upper program, but it can be easily solved.

The procedure of this method can be summarized:

1. Use McCormick envelope to get the LP relaxed lower program;

2. Solve the lower program and get the value of bilinear variables;

3. Replace bilinear variables of original bilinear program with the value of bilinear variables got from the lower program(notice that the bilinear contraints now are not considered in the original bilinear program, which makes sure the original problem is feasible) and solve this program and get a upper bound.

4. Check if UB=LB, if not, branch and bound method is used, then repeat the above procedures. 

[Johan Löfberg]

Still don't undersytand what you mean

Lets minimize x*y s.t -1 <=x<=1, -1<=x<=y

Linearization is minimize w s.t A[x;y;w]<=b. Now we solve that problem to obtain the optimal relaxation (x',y',w'). What do you want to do now?

[Xm AI]

Thanks a lot for your help~~But at first, I want to make clear that the upper bound got by nonlinear program is effective, but it may results in non-convergence while solving a large-scale bilinear program. That’s why I want to know whether yalmip can achieve the proposed method.

An example is given as below:

Assume a program:

minimize -(x1-12)^2-x2^2   s.t -6*x1+8*x2<=48  3*x1+8*x2<=120, 0<=x1<=24,  0<=x2<=20

1. First a variable X1, X2, X3 is used to replace the variable x1^2, x1*x2, x2^2, and McCormick envelope is used to set constraints for X1, X2, X3. Solve this LP relaxed problem and we can get the lower bound and the value of x1 and x2; 

The lower program can be written as follow:

minimize -X1^2+24*X1*X2-144-X2^2  s.t -6*x1+8*x2<=48  3*x1+8*x2<=120, McCormick envelope constraints for X1, X2, X3

therfore x1=24  x2=6, and the lower bound is -180

2. Replace the variable x1 and x2 of the original problem with the value 24 and 6, and the upper bound is got. The upper problem can be written as follow: 

minimize -(x1-12)^2-x2^2 

Replace the x1 and x2 with 24 and 6, then the upper bound is -52

3. Of course the upper bound and lower bound is not equal, then a branch and bound method is used.

[Johan Löfberg]

When you replace the values into the upper problem, you no longer have an optimization problem, but simply a value. Since your model has only linear constraints, the lower bound solution is trivially feasible, and hence any lower bound solution trivially yields an associated upper bound. YALMIP of course checks this solution. It is one of the upper bound strategies used if you specify the upper bound solver as 'none', and it is also always checked before any nonlinear solver is called.

[Xm AI]

Thanks a lot for your reply!

So written like this?

options=sdpsettings('solver','bmibnb','bmibnb.uppersolver','none');

solvesdp(Constraints,Objective,options);

but it leads to non-convergence, which it's weird, due to a lower bound must associated with a upper bound

[Johan Löfberg]

Then the lower bound solution isn't feasible. Show the code and data