Finding a sparse solution to $A x = b$ via linear programming

Question

I'm trying to solve a system $Ax = b$ where all entries of $x$ are nonnegative, and most are zero. So if $x$ has $N$ entries, then $\epsilon N$ of them are nonzero, where $\epsilon > 0$ is some small constant. Is it possible to use linear programming in this setting?

Answer 1

I assume you want to solve for $x$ where $$\begin{align} & Ax=b \\ & x_i\ge 0 \\ & \sum_{i|x_i>0} 1 \le m \end{align}$$ Counting non-zero elements is not easy in an LP, but we can use a MIP model: $$\begin{align} & Ax=b \\ & x_i \le M y_i \\ & \sum_i y_i \le m\\ & x_i\in [0,M] \\ & y_i \in \{0,1\} \end{align}$$ where $M$ is an upper bound on $x_i$ and $y_i$ are binary variables.

This approach requires some reasonable upper bound on $x$. Otherwise many MIP solvers nowadays have a concept called indicator variables, allowing a model like this to be solved without a big-$M$. I.e.:

$$\begin{align} & Ax=b \\ & y_i = 0 \Rightarrow x_i=0 \\ & \sum_i y_i \le m\\ & x_i\ge 0 \\ & y_i \in \{0,1\} \end{align}$$