Minimize the maximum of bilinear functions

Question

Define $w_{i,j}=x_iy_j+z_i$. I am interested in finding (or proving that there cannot be found) $x_i,y_j,z_i$ such that the $w_{i,j}$ satisfy a given order. For example, find $x_i,y_j,z_i$ such that

$0<w_{1,1}<w_{2,1}<w_{1,2}<w_{3,1}<w_{3,2}<w_{1,3}<w_{2,2}<w_{3,3}<w_{2,3}<1$

To this end I would like to solve the following optimization problem:

Minimize $\max\{0-w_{1,1}, w_{1,1}-w_{2,1},…,w_{3,3}-w_{2,3}, w_{2,3}-1\}$

If the optimal value is strictly less than zero, then I have a solution. Unfortunately each $w_{i,j}$ is nonconvex due to the bilinear $x_i y_j$ term. What is the best way to deal with this nonconvexity? Transformation to convex problem, global search techniques, ways to verify that the a local min is actually global...?

Answer 1

I don't see any way to transform this to a convex problem, but simply throwing the problem at a global solver spits out a negative solution rather easily

An implementation in the MATLAB Toolbox YALMIP (disclaimer, developed by me) would look something like this

x = sdpvar(3,1,'full');
y = sdpvar(3,1,'full');
z = sdpvar(3,1,'full');
t = sdpvar(1);

w = x*y' + repmat(z,1,3);

q = [0 w(1,1) w(2,1) w(1,2) w(3,1) w(3,2) w(1,3) w(2,2) w(3,3) w(2,3) 1]
Model = [diff(q)>=0, -diff(q) <= t];
Model = [Model, Model, 0 <= [x y z]<=2];
optimize(Model,t,sdpsettings('solver','bmibnb','bmibnb.maxiter',1e4))


 value([x y z])

ans =

    0.1767         0    0.0528
    0.4991    0.5971    0.1055
    0.1453    1.6865    0.2113

 value(q)

ans =

  Columns 1 through 9

         0    0.0528    0.1055    0.1583    0.2113    0.2980    0.3508    0.4035    0.4563

  Columns 10 through 11

    0.9472    1.0000