[Math] Bilinear Constraint

constraintsnonlinear optimizationoptimization

I would like to formulate the following Optimization problem. My question is focused on the constraint. Given a "typical" objective function, e.g.:

$$ \min c^T v $$

s.t.

$$ 0 = a_1 v_1 – a_2 v_2 + a_3 v_3 + a_4 v_4 +\dotsb $$

or written alternatively:

$$
\begin{gather}
0 = a^T Q v \\
0 \le b_L ≤ v \le b_U \\
0 < d_L ≤ a ≤ d_U,
\end{gather}$$

where $v$ and $a$ are variable vectors ($a$ is strictly positive and $v$ is positive); $b$ and $d$ are upper and lower bound vectors. I recognize that this constraint is bilinear. I'm hoping this problem is a recastable as LP or MILP given the equalities, and the positive variables. Is there an easy LP re-casting in this case?

I should mention that keeping the number of new constraints down to a minimum is at a premium. The McCormick convex relaxation seems like overkill (each constraint being recast with 4 new ones). Also, if possible I would like to implement this in IBM ILOG CPLEX.

Best Answer

You may decompose the bilinear constraint $a^TQv$ using a LU decomposition of $Q=LU$. Something like $x=L^Ta$ and $y=Uv$. Next, instead of using the bilinear constraint $x^Ty=0$, a (stronger) complementarity constraint is used $-b_i M\leq x_i\leq b_i M$ and $-(1-b_i) M\leq y_i\leq (1-b_i) M$, where $M$ is a large positive number and $b$ is a boolean variable.

Related Question