Does the triangle inequality suffice to prove all minimum results on sums of absolute values of affine functions? The title says it all ... more formally : let $n \geq 1$, and let $a_1, a_2 , \ldots ,a_n$ be positive numbers, let $b_1, b_2 , \ldots ,b_n$ be real numbers. Consider for $x\in {\mathbb R}$,
$$
\phi(x)=\sum_{k=1}^n a_k |x-b_k|
$$
It is easy to see that $\phi$ has a global minimum $m$ on $\mathbb R$, and that $m$
is attained of one the values $b_1, \ldots ,b_n$. In fact, $\phi$ is affine on each interval
$[b_k,b_{k+1}]$ (and on the outer intervals $]-\infty,b_1]$ and $[b_n,+\infty[$ ).
I say that "m is the global minimum for $\phi$" can be proved "using only the triangular inequality" if there are numbers $a'_1,a'_2, \ldots ,a'_n$
with $0 \leq a'_k \leq a_k$ (for $1 \leq k \leq n$) and constants $\varepsilon_1,\varepsilon_2, \ldots, \varepsilon_n$ all equal to $-1$ or $+1$, such that
$$
\sum_{k=1}^n\varepsilon_ka'_k=0, \ {\rm and} \ \sum_{k=1}^n\varepsilon_ka'_kb_k=m
$$
because then we have
$$
\phi(x)=\sum_{k=1}^n a_k |x-b_k| \geq \sum_{k=1}^n a'_k |x-b_k|
=\sum_{k=1}^n  |\varepsilon_k a'_k(x-b_k)| \geq 
\Bigg| \sum_{k=1}^n  \varepsilon_k a'_k(x-b_k) \Bigg| =m
$$
 A: Yes, the triangle inequality always suffices, and you can explicitly construct the $a_k'$ and $\epsilon_k$. They are severely constrained by the fact that the two inequalities in your last line must be equalities at the value $b_j$ at which $\phi$ takes the value $m$. For the first inequality to be an equality at $b_j$, we must have $a'_k=a_k$ for all $k\ne j$. For the second inequality to be an equality at $b_j$, all the terms must have the same sign, and this determines $\epsilon_k$ for all $k\ne j$ up to an overall sign; we can choose that sign such that all terms are non-negative. (I'm assuming that the $b_k$ are distinct, since otherwise we could just combine terms with the same $b_k$.)
This leaves only $a'_j$ and $\epsilon_j$ to be determined. Your first sum condition determines the value of $\epsilon_ja'_j$, and since $\epsilon_j=\pm1$ and $a'_j\ge0$, this determines $a'_j$ and $\epsilon_j$ (unless $a'_j=0$, in which case $\epsilon_j$ can be chosen arbitrarily). The resulting $a'_j$ is the absolute value of the slope at $b_j$ of the sum of all terms except the $j$-th, so the fact that adding the $j$-th term creates a minimum at $b_j$ implies $a'_j\le a_j$ as required. Since the values thus determined make all terms in the second inequality non-negative, the first sum condition and the last equality in the last line imply the second sum condition.
Actually the second sum condition should probably have $\pm m$, since both signs would make the last line work out; then the choice of making all terms positive wouldn't be required and either of the overall signs for the $\epsilon_k$ would yield an admissible set of values.
[Edit in response to comment:]
I think the result holds just as well for several variables. Basically what you're doing is to find the affine function that represents the sum of all terms but the $j$-th in a neighbourhood of $b_j$ and to replace the $j$-term by the negative of that so that the sum is identically zero in a neighbourhood of $b_j$, and then as you leave that neighbourhood the sign changes can only work to increase the function value. You can do something analogous for several variables: You can again replace the sum of all the functions that vanish at the minimum by the negative of the affine function that represents the sum of the non-vanishing terms in a neighbourhood of the minimum to make the sum vanish in that neighbourhood. In this case the neighbourhood will be bounded by hyperplanes on which individual affine functions vanish, and the sign change on crossing one of these hyperplanes can again only work to increase the value. As in the one-dimensional case, the replacement term is less than or equal in absolute value to the sum of the terms it replaces because otherwise the minimum wouldn't be a minimum.
