Optimization problem with absolute value term

Question

I want to minimize the following sum $$\sum_{i=1}^N (\frac{1}{2}(1-a)(b_{ki} -x )^2+a| b_{ki} -x |)$$ with respect to $x$ where $a\in [0,1]$.

My idea is to minimize each term in the sum using left and right derivatives. However I cannot make it work.

Can anyone help me get started or give me a hint?

Answer 1

Hint You can sort the $b_i$ so that $b_1\le b_2\le\cdots\le b_N$. You can add $b_0=-\infty$ and $b_{N+1} = +\infty$. On each interval $[b_j, b_{j+1}]$, the functional is a quadratic function of $x$ that is easy to minimize.

Answer 2

The most difficult part is the absolute value.

For $x\ne b_{ki}$, you can write $|b_{ki}-x|=|x-b_{ki}|=(x-b_{ki})\cdot\text{sign}(x-b_{ki})$, where the definition of the sign-function can be found here. If you derive this, wrt $x$, you get $\text{sign}(x-b_{ki})$.

For $x=b_{ki}$, the absolute value function is not differentiable, see here. You want to use the subderivative. The subderivative of the absolute value function $|x-b_{ki}|$ at point $x=b_{ki}$ is equal to the interval $[-1,1]$ (see here, page 4).

Answer 3

I do not know if there is an analytic solution to this problem. I can only tell you the solution for the two special cases: For $a=0$ the solution is given by the mean of the $(b_i)_{i=1,\dots,N}$ and for $a=1$ it is the median.