Solve $\inf_{x \le b}ax + \sum_{i=1}^n|c_i-x|$ where $a,b,c_1,\ldots,c_n \in \mathbb R$ with $\max_i c_i \le b$ and $a \le n$

Question

Let $a,b, c_1,\ldots,c_n \in \mathbb R$ with $a \le n$ and $\max (c_1,\ldots,c_n) \le b$. Consider the convex function $f:\mathbb R \rightarrow \mathbb R$ defined by $f(x) := ax +\|\boldsymbol{c}-x\boldsymbol{1}\|_1=ax + \sum_{i=1}^n|c_i-x|$

Question

Is there a semi closed-form formula (maybe involving sorting, etc.) for optimal the value $f^*$ of the following convex program ?

$$ \inf_{x \le b}f(x) $$

Observation

For the case $n=1$, one can compute a closed-form expression for $f^*$ like so

$$ \begin{split} f^* &= \inf_{x \le b}ax + |c-x| = \inf_{x \le b}ax + \sup_{|z| \le 1}z(c-x) = \sup_{|z| \le 1}cz + \inf_{x \le b}\;(a-z)x\\ &= ab + \sup_{|z| \le 1,\;z \ge a}(c-b)z = ab-\max(a, -1)(b-c) =\begin{cases}ab+b-c,&\mbox{ if }a \le -1,\\ ac,&\mbox{ else}.\end{cases} \end{split} $$

Answer 1

OK, I solved my problem. Posting the answer here hoping it will be helpful to someone else (plus, too long to fit in a comment).

So, WLOG, assume the $c_i$'s are sorted in ascending order so that $$ -\infty =: c_0 < c_1 \le c_2 \le \ldots c_n \le c_{n+1} := b. $$ Then the domain of optimization can be partition as $ (-\infty, b] = \cup_{i=1}^n (c_i,c_{i+1}]$, and so $f^* = \min_{0 \le i \le n} f_i$, where

$$ f_i := \inf_{c_i < x \le c_{i+1}} ax + \sum_{i=j}^n|c_j-x|. $$ For $1 \le i \le n$, define $\overline{c}_i := \sum_{j=1}^ic_j$, and set $\overline{c}_0 := 0$. For any $i \in \{0,1,\ldots,n\}$, one computes, $$ \begin{split} f_i &:= \inf_{c_i < x \le c_{i+1}} ax + \sum_{j=1}^n|c_j-x| = \inf_{c_i < x \le c_{i+1}} ax + \sum_{j=1}^i(x-c_j) + \sum_{j=i+1}^n(c_j-x)\\ &=\inf_{c_i < x \le c_{i+1}} (a+2i-n)x+\overline{c}_n-2\overline{c}_i = \overline{c}_n-2\overline{c}_i + \min((a+2i-n)c_i,(a+2i-n)c_{i+1}). \end{split} $$

Note that if $a \ge n$, then $f_0 = \min((a-n)c_0,(a-n)c_{1}) + \overline{c}_n=-\infty$, since $c_0 := -\infty$. This explains the initial requirment that $a \le n$.

Putting things together, we get the analytic formula

$$ \begin{split} f^* &=\overline{c}_n+\min\left(\min_{0 \le i \le (n-a)/2}(a+2i-n)c_{i+1} - 2\overline{c}_i,\min_{(n-a)/2 < i \le n}(a+2i-n)c_{i} - 2\overline{c}_i\right)\\ \end{split} $$

All in all, the complexity of the computations are $\mathcal O(n)$ (including the complexity of presorting the $c_i$'s!).