I'm trying to write a linear programming problem statement. Values of the solution vector have a bound constraint: $0 \leq x_i \leq 1$.
Another constraint is that if we take a predefined subset of solution vector values, then it should contain only one nonzero value or no nonzero values.
So it can be informally formulated in this way (without loss of generality): a vector either should be zero or should have exactly one nonzero value. Is it possible to set such constraint for the vector $x$ in terms of inequality ($Ax \leq b$) or equality ($A_{e}x=b_{e}$) constraints? How to do that?
Best Answer
As already pointed out, the feasible space for the cardinality constraint is non-convex. (0, 1) and (1, 0) have 1 nonzero, but (0.5, 0.5) have two. Converting this to a nonlinear function is mathematically correct, but it is more practical to use a mixed-integer programming formulation.
You first, need to introduce an integer variable to indicate that each $x_i$ is nonzero. $$x_i - y_i \le 0 \hspace{0.25in} \forall i$$ $$ y_i \in \{ 0, 1 \} \hspace{0.25in} \forall i$$ These constraints will force $y_i$ to 1 if x_i is nonzero. For our purposes, it is not necessary to enforce the converse.
Then for any subset of that is constrained to have at most one nonzero, you add the constraint
$$ \sum_{i \in I'} y_i \le 1$$
Which can be satisfied if and only if 0 or 1 of the $x_i$ values are nonzero.