Bilinear Program with Linear and Bilinear Inequality constraints

[Timothy Kam]

I was wondering if someone can provide some guidance. I have many independent medium (small?) scale bilinear programs (BLP) with linear (in)equality and bilinear inequality constraints to solve. Each program typically has only bilinear terms x_{i} * y_{i}, where i = 1, ..., N, and N <= 8. Let x and y, respectively, denote the vectors containing x_{i} and y{i}. The nonconvex BLP problem I specifically have, has the form:

min \sum_{i} x_{i} * y_{i}

s.t. 

(i)  \sum_{i} x_{i} * y_{i} <= constant

(ii) A * x + B* y <= constant, where rows(A) = rows(B) = L, and L ~ 200.

(iii) x_lb <= x <= x_ub

(iv) y_lb <= y <= y_ub

(v) sum(x) = 1.

where x_lb and x_ub are, respectively, lower- and upper-bounding vectors of real numbers.

As I understand, these problems, in theory, can be solved globally by reformulating with additional decision variables w_{i} := x_{i}y_{i}, so that it becomes a linear program with relaxed linear constraints as bounds on the constraint set (see. e.g. Sherali and Alameddine, 1992, J. of Global Optimization, 2: 379-410). To find the approximate global optimum, branch-and-bound methods are used to successively tighten the constraint relaxation bounds. (Is my understanding of the algorithm(s) here correct?)

After looking around for some time, it seems the closest implementation of a similar class of algorithm in through the YALMIP interface to PENBMI. My questions are:

1. Can I really solve such nonconvex problems globally using YALMIP/PENBMI?
2. What about KNITRO? Is there something similar to what I need there?

Thank you very much.

[Johan Löfberg]

That is the basic machinery used in the global solver bmibnb in YALMIP. It implements these cuts, with a lot of extra tricks to improve them, and generalizations, in a b&b setting. Hence, implementing this in YALMIP would be to reinvent the wheel (and making it square instead, thus lowering performance).

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.BMIBNB

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.BMIBNBTheory

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.GlobalOptimization

Simply code you problem and tell YALMIP to use its internal solver bmibnb to solve the problem. Try it on your problem and let me know how it works out.

Note that it requires a good nonlinear solver for upper bounds. PENBMI is not suitable (developed with bilinear semidefinite constraints as main target). Instead, fmincon, snopt or ipopt are suitable choices. I typically solve these global problems using fmincon. It actually performs rather well despite its reputation, probably due to the massive presolve that is done inherently in bmibnb before calling fmincon. Some problems requires some tweaking of the options in fmincon though to make it perform much better (changing algorithm, the default one in recent versions of MATLAB is robust but extremely slow on some problems, thus causing bmibnb to spend an awful amount of time in the computation of an upper bound in each node). You need an efficient LP solver too of course, gurobi for instance.

 Just for fun, here is some code using the (recently introduced, mostly for internal testing) function envelope which uses the same core machinery as bmibnb

sdpvar w x y

E = envelope([w == x*y, .1 <= [x y] <= 2]);

plot(E,[x y w],[],300,sdpsettings('relax',1,'plot.shade',.3))

hold on

[X,Y] = meshgrid(.1:.1:2, .1:.1:2);                                

Z = X.*Y;                                        

surf(X,Y,Z);

BTW, this sentence "After looking around for some time, it seems the closest implementation of a similar class of algorithm in through the YALMIP interface to PENBMI." seems to indicate that you misunderstood something about  local solvers such as penbmi, fmincon, ipopt etc. penbmi does not in any sense attack this problem using linear cuts. It treats the problem as a standard nonlinear program and simply tries to compute a locally optimal solution. Sure, it is limited to bilinear programs, but that does not in any sense mean it is better at solving these problems than any other general nonlinear local solver.