L1 minimization problem with nested sums as LP problem I've been trying to solve this problem but I have an issue with the fact that there is a sum under each absolute value. I'm trying to convert this minimization problem (with respect to $x, y_1, \dots,y_n$)
$$
\sum_{i=1}^{m} \left| x - \sum_{j=1}^{n}\left| y_j - a_{ij} \right|  \right|
$$
to a linear programming problem. It's similar to this question, however that problem hasn't got the nested sums.
Does it suffice to just do the same substitution as in the linked question or should I make other substitutions and constraints as well?
 A: You cannot convert this to a linear program. The objective function is not convex (consider the special case $m = n = x = a_{11} = 1$, draw the function and you'll see). You cannot use epigraph models when the expression you outer bound enters in a nonconvex fashion (which the inner absolute value does).
EDIT: Giving a more complete example which shows the failure of the LP proposed in another answer. Assume $a = (2,0,-1)$. An optimal solution to this is $x = y = 1$ (it is not unique) with objective value 1. An optimal solution to a flawed LP model would be $x=2, y=0, z = (0,0,0), \omega = (2,2,2)$. The LP objective is thus $0$, but if you plug the solution $x = 2, y = 0$ into the original nonlinear objective, it has objective value 3. In other words, the LP is incorrect. Here is a MATLAB/YALMIP model to reproduce example
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)]

A: First of all, as pointed out by Johan Löfberg, this is not a convex function, so it is vain to search for a pure linear program. Therefore, the following does not work in the general case :
Step 1:
$$
\sum_{i=1}^m z_i
$$
subject to
$$
x-\sum_{j=1}^n|y_j-a_{ij}| \le z_i\\
-x+\sum_{j=1}^n|y_j-a_{ij}| \le z_i
$$
Step 2:
$$
\sum_{i=1}^m z_i
$$
subject to
$$
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}\\
$$
I am convinced however that a MILP very close to the above program should do the trick. Still working on it, trying to use binaries to ensure tightness.
