0
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user251257 Jul 14 '15 at 18:05
  • $\begingroup$ yes, some elements of Q will be negative! $\endgroup$ – Hybrid Jul 15 '15 at 12:13
  • $\begingroup$ Like I said, it isn't straight forward. You could try SQP type methods. $\endgroup$ – user251257 Jul 15 '15 at 12:18
  • $\begingroup$ Agreed, there is no simple re-casting of this problem. $\endgroup$ – Michael Grant Jul 15 '15 at 12:27
  • $\begingroup$ If all elements of Q were made positive, would it be possible? $\endgroup$ – Hybrid Jul 15 '15 at 12:37
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.