How to prove that this function is unimodal?

Question

I have a function f(x) = $\sum_{i=1}^n c_i|x-h_i|$ where both $c_i$ and $h_i$ are positive integers. Now I wanted to prove that this function is unimodal but I am unable to do so.
Actually, I was learning Ternary Search so I wanted to apply that technique to a problem and this was the equation that I came up with for solving the particular problem. The answer to the problem is the minimum value of this function. Though I could solve the problem using Ternary Search, I couldn't figure out that why this function is unimodal. How can one prove whether a function is unimodal or not (especially this one)?

Answer 1

The function $f(x)=\sum_{i=1}^nc_i|x-h_i|$ is piecewise linear. Without loss of generality, let's assume that $h_1\lt h_2\lt\cdots\lt h_n$ (otherwise one can first permute the index notation). Then on each interval $(h_i,h_{i+1})$, the slope of the linear function is $m_i=(c_1+\cdot+c_i)-(c_{i+1}+\cdots+c_n)$, with $m_0=-(c_1+\cdots+c_n)$ for the interval $(-\infty,h_1)$ and $m_n=c_1+\cdots+c_n$ for the interval $(h_n,\infty)$. Since all the $c_i$'s are positive (by assumption), the slopes are strictly increasing (i.e., $m_i-m_{i-1}=2c_i\gt0$), so there cannot be more than a single local minimum. Finally, since $m_0\lt0$ and $m_n\gt0$, there is a minimum, and thus the function is unimodal.

Remark: The only crucial assumption here is that the $c_i$'s are all positive; they do not need to be integers, nor is any assumption on the $h_i$'s needed at all.

Answer 2

A function is quasi-convex if $\{ x: f(x) \le c \}$ is a convex set for every real $c$. If a function is quasi-convex, its set of minimizers is convex. An alternative definition is that $f$ is quasi-convex if $f(\lambda x + (1-\lambda)x') \le \max \{f(x),f(x')\}$ for every $\lambda \in (0,1)$. If the inequality is strict, then if $f$ has a minimizer, it has a unique minimizer. This seems like a better definition to use than unimodal? The idea is that the lower contour sets of a quasi-convex function are convex, so there can't be multiple "valleys". A stronger property that "sums" is convexity: a function is convex if $f(\lambda x + (1-\lambda) x') \le \lambda f(x) + (1-\lambda) f(x')$ for all $ \lambda \in (0,1)$.

Since $a_i|x-h_i|$ is a convex function if $a_i >0$, and a sum of convex functions is convex, $f$ is convex. The function $f(x)$ will have a convex set of minimizers, and will occur where the subgradient of $f(x)$ is equal to zero. So if $f:X\rightarrow \mathbb{R}$, the subgradient of $f$ at $x$, $\partial f(x)$, is defined as the set of vectors $g$ such that $$ |f(x)-f(y)|\ge g ||x-y||, \quad \forall y \in X. $$ For your $f$, a point $x^*$ is a global minimum iff $0 \in \partial f(x^*)$. In fact, your set of minimizers is probably set-valued.

So to find your minimizers, find the set where $$ \sum_{i=1}^N a_i \mathbb{I}\{x >h_i\} - a_i \mathbb{I}\{x<h_i\} = 0 $$ And that interval between two of the $h_i$'s will be the set of global minimizers; if the $a_i$ have a particular pattern, that quantity will not equal 0 on an interval, and the zero will occur at one of the $h_i$'s.

A fast way to do this would be to compute, for each $i = 1, ..., n$, $$ \sum_{\ell \le i} a_i - \sum_{\ell > i} a_i. $$ When you hit zero, you have arrived at the minimum of the function at some $i^*$, and just have to check whether it is also zero in a neighborhood of $a_{i^*}$.