# How to solve the linear programming with constraints of $\ell_0$-norm?

I am trying to solve a linear programming with the $$\ell_0$$-norm constraints, which give a constrain on the element of the variables. E.g., I have $$3$$ variables, $$x_1$$, $$x_2$$, $$x_3$$ and I have some "normal" constraints, like below

$$x_1 > 0,$$

$$x_1 < 0.3,$$

$$x_2 > 0,$$

$$x_1 < 0.4,$$

$$x_3 > 0,$$

$$x_1 < 0.5.$$

Besides I have a $$\ell_0$$-norm like constraints.

$$|x_1|_{0} + |x_2|_{0} +|x_3|_{0} \leq 2$$

That is the maxinum amount of the chosen variable from $$x_1$$, $$x_2$$, $$x_3$$ is $$2$$.

The objective function (to get mininum) is

$$f = -(x_1+x_2+x_3)$$

So the answer should be $$[0, 0.3, 0.4]$$, that is $$x_2$$ and $$x_3$$ chosen.

How to deal with this kind of linear programming? I know it may be a non-convex problem. Also a $$\text{LP}$$ problem. Could it be change to a Mixed-integer linear programming ($$\text{MILP}$$) problem? Or is there any usual way to solve it? Any idea is appreciated. Just some key words or workflows is well, too. I need to know more about it.

You can make it into a MILP by introducing binary variables indicating if the corresponding $$x$$ values are zero or not. In your case, assuming $$x$$ are nonnegative: $$\begin{array}{l} x_i\leq Mz_i\\ z_i\in\{0,1\}\\ z_0+z_1+z_2\leq 2 \end{array}$$ where $$M$$ is a reasonable constant, will give you the bound you are looking for. See for instance https://docs.mosek.com/modeling-cookbook/mio.html#implication-of-positivity for more on this.
In general problems with $$L_0$$ norm are hard. A typical approximation is to replace the $$0$$-norm with $$1$$-norm and include the $$1$$-norm as penalty in the objective. This is just a heuristic but it tends to prefer sparse solutions. See for instance from slide 17 in https://web.stanford.edu/class/ee364b/lectures/l1_slides.pdf.