I am a new learner of optimization, and I am confused by the question below, (how to change a 0-norm constrain into binary and linear constrain ?)


Given a sparse data fitting problem:

$ minimize \quad \| Ax-b \|^{2}_{2}$

$ s.t. \qquad \|x\|_{0} \le K, $

$x \in R^{n}$

Suppose we are given a constant $M > 0$ such that $\|x^{*}\|_{\infty} \le M$ for some optimal solution $x^{*}$ to this problem. How can we paraphrase this problem with only linear and binary constraints?


Thanks for any help.

closed as off-topic by j.c., Jan-Christoph Schlage-Puchta, Ben McKay, Pace Nielsen, Piotr Hajlasz Sep 27 at 21:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – j.c., Piotr Hajlasz
If this question can be reworded to fit the rules in the help center, please edit the question.

up vote 1 down vote accepted

This can be done using a Big M approach.

Introduce zero one binary variables $y_i, i=1,..,n$

Replace the constraint $\qquad \|x\|_{0} \le K, $ with the following constraints:

$$\Sigma_{i=1}^n y_i \le K$$ $$-x_i \le My_i, i=1,..,n$$ $$x_i \le My_i, i=1,..,n$$

As can be seen, when $y_i = 0$, then $x_i$ must equal $0$. When $y_i = 1$, $|x_i|$ is constrained to be $\le M$, and $y_i$won't sub-optimally "waste" being $1$ when $x_i = 0$.

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