Analytical form of the minimum of a function with absolute values

Question

I would like to find the analytical form of the point which minimizes the following function:

$$ f(x_T) = \frac{1}{T} a_1 (x_T-x_0)^2 + a_2 |x_T-x_0| + T a_3 + \sum_{i=1}^M p_i \left[b_{1i} (x_T - l_i)^2 + b_{2i} |x_t - l_i| + b_{3i} \right] $$

where $T,a_1,x_0,a_2,a_3,p_i,b_{1i},l_i,b_{2i},b_{3i}$ are constants, $T,a_1,x_0,a_2,p_i,b_{1i},l_i,b_{2i}$ are greater than zero, and M is a positive index. The function is continuous, convex, and piecewise differentiable. Any ideas on how to find the analytical form of the point, $x^*_T$, which minimizes $f(x_T)$?

Answer 1

I very much doubt that such a closed form solution exists. Certainly, if one can be found, it needs to make use of the fact that what you have is a linear combination of functions of the form $\gamma_1(x_T-y)^2 + \gamma_2 |x_T-y|$ which is certainly a nice function to have.

However, the solution of your problem is not continuous with respect to the parameters $a_{1/2},b_{i1/2}$. You can already see that if, for a moment, you neglect the quadratic terms (i.e., $a_1=b_{i1}=0$) and consider the case $M=1$. In that case, you add two absolute value functions, i.e., $$ f(x_T) = a_1 |x_T-x_0| + b_{11} |x_T-l_1| $$ It is easy to see that if $a_1>b_{11}$ then the minimum is at $x_T=x_0$ whereas for $a_1<b_{11}$ the minimum is at $x_T=l_1$. For $a_1=b_{11}$, every point between $x_0$ and $l_1$ is a the minimum.

This example already shows that even a simplified case is not easy to solve. It's only going to get worse if you add more parameters to the problem.

(As an aside: One might speculate that one of the points $x_0, l_i$ is in fact the minimum, given the form of the terms you add up. However, I believe that it would be simple to give a counter-example for which this is not true. But, even if it was, the question which of these finitely many points is the minimum clearly depends on the relative sizes of all of your coefficients and, as the example above shows, it's not going to be a simple decision.)

Answer 2

This is not an analytic solution, but rather a strategy to find the solution.

The cusp points $x_0,l_i$ partition $\mathbb{R}$ into a series of intervals. The minimum either lies at one of the cusp points, or lies in one of the intervals inbetween. You could do a binary search of these intervals to see which cusp point the derivative changes sign around. Then check the left and right derivatives at that cusp point to see if the subderivative there contains zero. If it does, that's the minimum.

On the other hand, if both the left and right derivatives at the cusp point are positive, the solution is in the interval directly to the left. Similarly, if both derivatives are negative, the solution is in the interval directly to the right. In both of these intervals the function is quadratic so there is a formula for the solution.