L1 problema de minimización con dichas sumas como LP problema

Question

He estado tratando de solucionar este problema, pero tengo un problema con el hecho de que hay una suma en cada valor absoluto. Estoy tratando de convertir este problema de minimización (con respecto a $x, y_1, \dots,y_n$)

$$ \sum_{i=1}^{m} \left| x - \sum_{j=1}^{n}\left| y_j - a_{ij} \right| \right| $$

para un problema de programación lineal. Es similar a esta pregunta, sin embargo, que el problema no tiene el anidado de sumas.

No es suficiente simplemente hacer la misma sustitución como en los vinculados pregunta o debo hacer otro sustituciones y limitaciones así?

Answer 1

Usted puede convertir esto en un problema de programación lineal. La función objetivo es no convexo (considere el caso especial $m = n = x = a_{11} = 1$, dibujar la función y verás). Usted puede utilizar epígrafe modelos cuando la expresión límite exterior entra en un nonconvex de la moda (que el interior de valor absoluto).

EDIT: Dar un ejemplo más completo que muestra el fracaso de la LP propuesto en otra respuesta. Suponga $a = (2,0,-1)$. Una solución óptima para esto es $x = y = 1$ (no es la única) con valor objetivo 1. Una solución óptima a un defectuoso LP modelo se $x=2, y=0, z = (0,0,0), \omega = (2,2,2)$. El LP objetivo es, pues,$0$, pero si se conecta la solución de $x = 2, y = 0$ en la original no lineal objetivo, tiene valor objetivo 3. En otras palabras, el LP es incorrecta. Aquí está una MATLAB/YALMIP modelo para reproducir el ejemplo

a = [2;0;-1];
sdpvar x y
Objective = sum(abs(x - abs(y-a)));
optimize([],Objective)
[value(x) value(y) value(Objective)]

z = sdpvar(3,1);
w = sdpvar(3,1);
Model = [-z <= x - w <= z, -w <= a-y <= w];
optimize(Model,sum(z))
[value(x) value(y) value(sum(z)) value(Objective)]

Answer 2

Primero de todo, como se ha señalado por Johan Löfberg, esta no es una función convexa, por lo que es vano buscar un puro problema de programación lineal. Por lo tanto, el siguiente no funciona en el caso general :

Paso 1: $$ \sum_{i=1}^m z_i $$ sujeto a $$ x-\sum_{j=1}^n|y_j-a_{ij}| \le z_i\\ -x+\sum_{j=1}^n|y_j-a_{ij}| \le z_i $$

Paso 2: $$ \sum_{i=1}^m z_i $$ sujeto a $$ x-\sum_{j=1}^n \omega_{ij} \le z_i\\ -x+\sum_{j=1}^n \omega_{ij} \le z_i\\ y_j-a_{ij} \le \omega_{ij}\\ -y_j+a_{ij} \le \omega_{ij}\\ $$

Estoy convencido, sin embargo, que un MILP muy cerca de la anterior programa debe hacer el truco. Sigue trabajando en ello, tratando de usar los binarios para asegurar la estanqueidad.