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.

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

  • Thanks for your help. I understand now. – Yu Lin Sep 15 at 9:16

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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