MILP: Minimizing $|Ax-b|$ with at most 5 x variables being non-zero

Question

I have a $m \times n$ matrix $A$, where $n$ is very large and $ n>m$ (underdetermined), and $b$ is $m \times 1$ matrix. I want to minimize $|Ax-b|$, but at most $5$ $x_i$ can be non-zero. Other constraints are that $\sum x_i=1$ and $x_i\geq 0$. So I have set up a mixed interger linear program:

$$\min \sum z_i$$ s.t. $$Ax-b\leq z$$ $$b-Ax\leq z$$ $$\sum x_i=1$$ $$y_i \in\{0,1\}$$ $$\sum y_i=5$$ $$0\leq x_i\leq y_i$$

I'm absolutely clueless as to how to put this into MatLab. Any help would be appreciated.

Answer 1

With the MATLAB Toolbox YALMIP (disclaimer, developed by me), it would be

x = sdpvar(n,1);
z = sdpvar(m,1);
y = binvar(n,1);
Model = [-z <= A*x-b <= z, sum(x) == 1, x >= 0, sum(y)==5, 0<=x<=y];
Objective = sum(z);
optimize(Model,objective)
value(x)

If you have an integer solver installed, such as intlinprog, it will automatically be used. If you want to see what the intlinprog model looks like to reverse engineer, you can use the command export. As mentioned above though, if you really have a large problem, you would benefit from a better solver such as cplex, gurobi or mosek (all still available via via YALMIP and the same code)

Having said that, the lazy person would let the modelling layer do all the modelling

Objective = norm(A*x-b,1);
Model = [nnz(x) <= 5, 0 <= x <= 1];
optimize(Model,objective)

As asked about in the comments, generate many solutions

x = sdpvar(n,1);
z = sdpvar(m,1);
y = binvar(n,1);
Model = [-z <= A*x-b <= z, sum(x) == 1, x >= 0, sum(y)==5, 0<=x<=y];
Objective = sum(z);
result = optimize(Model,Objective);
Model = [Model, Objective <= value(Objective)];
while result.problem == 0
 Model = [Model, exclude(y,value(y))]  
 result = optimize(Model,Objective);
 value(x)      
end

Answer 2

If your only issue is "How to put it into Matlab" then you can start here https://se.mathworks.com/help/optim/ug/intlinprog.html

Consider using a modeling tool such as https://yalmip.github.io/

You may want to get yourself a specialized mixed-integer solver though if your problems get large.