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.



sparse data fitting problem
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$.


