0
$\begingroup$

I have a optimization problem as follows:

minimize $ \sum_i \sum_j x_i x_j S_{ij} $

subject to the constraint

$x_i > a$ or $x_i=0$ for all indices and $ \sum_i x_i=1.0$

Can someone please help me to formulate this constraint. How do it formulate this "or" condition that if $x_i$ not greater than "a" then it can be zero.

Thanks in advance.

$\endgroup$
  • $\begingroup$ There's a couple of things wrong with this formulation. First, is there one constraint x_i > a? (for which i?), should there be a summation, or many constraints (with a_i on the right hand side)? Second, optimization does not do well with strict inequalities. I suspect you meant $x_i \ge a$. $\endgroup$ – user3697176 May 15 '17 at 23:13
  • $\begingroup$ Please try to fix the formulation, as pointed out by @user1612986, and use built-in tex support to write formula. $\endgroup$ – AndreaCassioli May 16 '17 at 6:20
1
$\begingroup$

The typical way to deal with such questions involves additional variables and a boundedness assumption. If you have an upper bound, say $M$, on $x_i$ that is automatically satisfied, then you can rewrite the two constraints as

$$M\ge x_i \ge a,$$ $$\mbox{or}$$ $$0\ge x_i \ge 0.$$

Now introduce a binary variable $z$ (which can only take two values, 0 and 1) and replace the constraints by $$Mz \ge x_i,$$ $$x_i \ge az, $$ $$z = 0 \mbox{ or } z = 1.$$

Explanation: If $z = 0$, the two constraints collapse into $0\ge x_i\ge 0$ (or $x_i = 0$), and if $z=1$, then $M \ge x_i \ge a$ (or just $x_i\ge a$, since the left inequality is assumed to be automatically satisfied).

$\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.