How do I minimize sum of modules?

Question

I need to minimize sum of modulus of linear combinations of the variables. For example:

$$ f = |1+a-2b+3c| + |-a+b+c| + |a| + |b| + |c| $$

My initial plan was to calculate gradient and then perform linear search. I faced a problem: if f derivative is non-existent, when some of these modules are equal to zero, if we assume $\\D_x|x|=0$ for $x=0$, gradient indeed is not the direction of steepest descent indeed. For example, when (a,b,c) = (22/27,23/27,-1/27), gradient is (1,1,-1), but if we plug $a \to 22/27+t, b \to 23/27 + t, c \to -1/27 + t$, then minimum for f(t) is $t=0$:

But if we take different direction, say (22,23,-1), then we can make a step and reduce function value:

So my question is: how do I handle such a function in a numerical optimisation? May be I can reformulate the problem somehow, may be it may be reformulated as LP problem or some other sort of problem?

Answer 1

EDIT

Inside a domain where all moduli contents have constant sign, the problem is a LP (Linear Program) and hence has an optimum on a vertex of the domain boundary.
This implies that the global solution lies on a vertex intersection of moduli boundaries. (Or a larger dimension affine subspace, if there are less independent moduli than variables).
So the problem can be solved by a variant of simplex method: if there are $n$ variables, jump from one vertex to another, where vertices are intersections of $n$ (independent) moduli boundaries. The jump is made by following an edge, which means exchanging one boundary by another one, just like in simplex we exchange one variable by another one.

This gives a hint as the way to transform the problem into a LP with a usual trick.
For each modulus, e.g. $|-a+b+c|$:

• add $2$ variables $u$ and $v$,
• add the following positivity constraints: $u \ge 0$, $v \ge 0$,
• add the constraint $-a+b+c+u-v = 0$,
• in the objective function $f$, replace $|-a+b+c|$ by $u + v$.

And we are done. It works because on the optimum, only one of $u$ and $v$ may be strictly positive, but not both: otherwise subtract $\min(u,v)$ to both and you get a lower objective. So at the optimum, either $u = |-a+b+c|$ and $v = 0$, or $v = |-a+b+c|$ and $u = 0$.

Note that the remarks in comments are still applicable: the problem lies in the vast category of non-differentiable convex optimization problems, with the added benefit that it is non-constrained. But the transformation into a LP proposed above is much simpler than the general case.

First answer

To deal with piecewise-linear functions in optimisation problems, the usual way is to decompose the domain into parts where the functions are linear. Here, this means having $2$ cases for each of the $5$ modulus, which in total makes $2^5=32$ cases. Each case is a linear problem; send all them to your favorite LP solver, the $32$ should be solved in an eyeblink, given the small number of variables.

Actually you could also use steepest gradient descent. As the problem is convex there is no risk to stop in a local minimum. Chosing the step size is the difficult part, as the gradient is not continuous accross modulus boundaries.