-1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
0

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