MILP: Minimizar $|Ax-b|$ con un máximo de 5 variables x no nulas

Question

Tengo un $m \times n$ matriz $A$ , donde $n$ es muy grande y $ n>m$ (infradeterminado), y $b$ es $m \times 1$ matriz. Quiero minimizar $|Ax-b|$ , pero como máximo $5$ $x_i$ puede ser distinto de cero. Otras restricciones son que $\sum x_i=1$ y $x_i\geq 0$ . Así que he creado un programa lineal mixto interger:

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

No tengo ni idea de cómo poner esto en MatLab. Cualquier ayuda sería apreciada.

Answer 1

Con la caja de herramientas de MATLAB YALMIP (aviso, desarrollada por mí), sería

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)

Si tiene instalado un solucionador de enteros, como intlinprog, se utilizará automáticamente. Si quieres ver cómo es el modelo de intlinprog para hacer ingeniería inversa, puedes utilizar el comando exportar. Sin embargo, como se mencionó anteriormente, si realmente tienes un problema grande, te beneficiarías de un mejor solucionador como cplex, gurobi o mosek (todos disponibles a través de YALMIP y el mismo código)

Dicho esto, la persona perezosa dejaría que la capa de modelado hiciera todo el modelado

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

Como se ha preguntado en los comentarios, generar muchas soluciones

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

Si su único problema es "cómo ponerlo en Matlab", puede empezar aquí https://se.mathworks.com/help/optim/ug/intlinprog.html

Considere la posibilidad de utilizar una herramienta de modelado como https://yalmip.github.io/

Sin embargo, si los problemas son grandes, es posible que quieras conseguir un solucionador de enteros mixtos especializado.