constraint formulation of optimization problem.

Question

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.

Answer 1

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).