How can I find the minimum of a multi-dim function that can be written as sum of absolute values

Question

for a certain application I need to implement an algo that finds the minimum of a function of the following form. It´s a function of the variables $x_{i}$:

$$\sum_{p} a^{p}| \sum_{i} b_{i}^{p}x_{i}+c_{i}^{p}| $$

It´s convex and I figured out the one dimensional case but got stuck here. Anybody has a clue?

Answer 1

If $a$ is non-negative, you can move those into the absolute value and after some reordering you essentially have a regression problem with an L1 cost $|Dx+e|_1$. You either solve that as a linear program, or use tailored algorithm for L1 regression.