# Bilinear Constraint

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.

• It might be difficult then you think, as $0=a^T Q v$ is not convex. Also, is the minus sign in $-a_2v_2$ intended? – user251257 Jul 14 '15 at 18:05
• yes, some elements of Q will be negative! – Hybrid Jul 15 '15 at 12:13
• Like I said, it isn't straight forward. You could try SQP type methods. – user251257 Jul 15 '15 at 12:18
• Agreed, there is no simple re-casting of this problem. – Michael Grant Jul 15 '15 at 12:27
• If all elements of Q were made positive, would it be possible? – Hybrid Jul 15 '15 at 12:37

## 1 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.