# 1D Optimisation Problem with Objective function of Absolutes

I have a vector of finite, real parameters $[\theta_2, \theta_3, .., \theta_{n-1}]$. I have one variable, $x_1$. I want to minimise the following objective function: $$f(x_1) = |x_1| + |x_1+\theta_2| + |x_1+\theta_2+\theta_3| + ... + |x_1+\theta_2+...+\theta_{n-1}|$$ I would like to know if there is a simple, analytical solution for this problem. Traditional calculus techniques would suggest taking the derivative, but it is not a smooth function. In particular given the sub-function: $$g(x)=|x+y|, \quad \frac{dg}{dx}= \left \{ \begin{matrix} -1,\; x<-y \\ +1,\; x>-y \end{matrix} \right.$$ Also I expect there to be a unique solution but am currently thinking through how to prove this also.

• Why do you expect a unique solution? Try just one parameter $|x|+|x+\theta|$, then all $x$ between $0$ and $-\theta$ are solutions. – A.Γ. Nov 4 '17 at 14:12
• This formula is the abstraction of part of rather complicated financial process. Inution about the real action of the problem suggested a unique solution, albeit you make a neat and simple point. When there are many more theta it make the linear range very small giving the intuitive impsression of uniqueness. See my suggested answer which alludes to still a possible unique solution if certain criteria hold? – Attack68 Nov 4 '17 at 17:03

I have thought a little more about this and propose the solution. Set $\theta_1:=0$ and $y_i=\sum_{j=1}^i \theta_j$, so that the problem above becomes minimise: $$f(x_1)=\sum_{i=1}^{n-1}|x_1+y_i|$$ If we order the $y_i$s in say ascending order then the solution for $x_1$ should be at the midpoint which will permit the derivative to be zero (or i suppose undefined) placing $x_1$ either side of that will result in a derivative that suggests a better solution. For odd numbers of $n$ a range of permitted values might be valid (see A.r. comment) but for an even $n$ this might result in a unique value. I havent explored the cases of repeated $y_i$ thoroughly yet.
• Yes, it's the right way to start thinking. When you say "at the midpoint" you mean not in the sense of length, but in the sense of that it is as many parameters that are smaller as that that are larger than the point. Think also what happens if some $y_i$ are equal. "Derivative is zero" is not applicable here. – A.Γ. Nov 4 '17 at 17:18