Sum of Absolute Values

Problem

$\begin{align} f(x)=|x|&+2|x-1|+|x-2|+|x-4|\\ &+|x-6|+2|x-10|. \end{align}$

Find the minimum value of $f(x),$ for $x\in\mathbb{R}.$

Brute force solution

$f(x)$ is the sum of functions with $V$-shaped graphs. The minimum is bound to occur at one of the "break" points. There are only six of them: $x=0,1,2,4,6,10.$ Let's check:

$\begin{align} f(0)&=0+2+2+4+6+20=34\\ f(1)&=1+0+1+3+5+18=28\\ f(2)&=2+2+0+2+4+16=26\\ f(4)&=4+6+2+0+2+12=26\\ f(6)&=6+10+4+2+0+8=30\\ f(10)&=10+18+8+6+4+0=46 \end{align}$

The minimum is achieved at two points, $x=2$ and $x=4$ and is equal to $26.$

Looking back

Function $f$ being the sum of functions with $V$-shaped graph is piecewise linear. It is linear between any two successive breakpoints and outside the smallest interval that contains all of them, $[0,10]$ in this problem. So the fact that the minimum is achieved at two points, means that on the interval $[2,4]$ the function is constant. Indeed, here is its graph:

graph of f(x)=|x|+2|x-1|+|x-2|+|x-4|+|x-6|+2|x-10|

Now, is there anything about this problem that suggests a more insightful approach? There is indeed. A similar problem has been popularized by Paul J. Nahin:

Suppose we have a real line before us (labeled as the \(x\)-axis), stretching from \(-\infty\) to \(+\infty\). On this line there are marked \(n\) points labeled in increasing value as \(x_1 \lt x_2 \lt \ldots \lt x_n\). Let's assume that all the \(x_i\) are finite (in particular \(x_1\) and \(x_n\)), and so the interval of the \(x\)-axis that contains all \(n\) points is finite in length. Now, somewhere (anywhere) on the finite \(x\)-axis we mark one more point (let's call it \(x\)). We wish to pick \(x\) so that the sum of the distances between \(x\) and and the original points is minimized. That is, we wish to pick \(x\) so that

\(S = |x - x_{1}| +|x - x_{2}| + \ldots + |x - x_{n}|\)

is minimized.

The crucial insight is already apparent in the simplest graph of that sort, say, that of $g(x)=|x-1|+|x-2|:$

graph of f(x)=|x-1|+|x-2|

Any function $g(x)=|x-a|+|x-b|$ is constant in the interval $[a,b]$ (assuming $a\lt b)$ where it takes the value of $b-a.$ This is how it help to solve our problem: the given function is the sum of the simple ones (each of only two terms):

|x|+2|x-1|+|x-2|+|x-4|+|x-6|+2|x-10|

$\begin{align} f(x)&=|x|+|x-10|\\ &+|x-1|+|x-10|\\ &+|x-1|+|x-6|\\ &+|x-2|+|x-4|. \end{align}$

The first of these is constant on the interval $[0,10],$ the others, successively, on $[1,10],$ $[1,6],$ $[2,4],$ the last of which is common to all the pairs. We may even generalize.

Generalization

Given an increasing sequence of real numbers $a_{1}\lt a_{2}\lt a_{3}\lt\ldots\lt a_{n}$ and a sequence of as many positive real coefficients $\{\alpha _{i}\},$ $i=1,2,\ldots ,n.$ Function $\displaystyle f(x)=\sum_{i=1}^{n}\alpha_{i}|x-a_{i}|$ achieves its minimum at one of the intervals $[a_{k},a_{k+1}]$ if and only if the coefficients $\{\alpha _{i}\}$ can be split into two groups with equal sums. Otherwise, the minimum is achieved at one of the given points $\{a_{i}\}.$

Proof

The proof is by induction.

The claim is obvious when there are just one or two terms.

For a larger $n,$ assume without loss of generality that $\alpha _{1}\le\alpha _{2}.$ Then,

$\begin{align} f(x)&=\bigg[\alpha _{1}|x-a_{1}|+|x-a_{n}|\bigg] \\ &\space\space +\bigg[\alpha _{2}|x-a_{2}|+\ldots +\alpha _{n-1}|x-a_{n-1}|+(\alpha _{n}-\alpha_{1})|x-a_{n}|\bigg], \end{align}$

where the function in brackets has fewer than $n$ break points. Also, the coefficients $\alpha_{2},\ldots,\alpha_{n-1},\alpha_{n}-\alpha_{1}$ could be split into two groups of equal sums only if that is true of the original $n$ coefficients. To complete the induction, it suffices to observe that the interval $[a_{1},a_{n}]$ where the first term is constant, contains all the break points of the second term.

Modification

Given an increasing sequence of real numbers $a_{1}\lt a_{2}\lt a_{3}\lt\ldots\lt a_{n}.$ Find the minimum of function $\displaystyle f(x)=\sum_{i=1}^{n}(x-a_{i})^{2}.$

Solution

Notice that

$\begin{align} f(x)-f(y)&=\sum_{i=1}^{n}\bigg[(x-a_{i})^{2}-(y-a_{i})^{2}\bigg]\\ &=\sum_{i=1}^{n}\bigg[(x^{2}-y^{2})-2(x-y)a_{i}\bigg]\\ &=n(x^{2}-y^{2})-2(x-y)\sum_{i=1}^{n}a_{i}. \end{align}$

Letting $\displaystyle y_{0}=\frac{a_{1}+\ldots+a_{n}}{n}$ gives

$\begin{align} f(x)-f(y_{0})&=n(x^{2}-y_{0}^{2})-2(x-y_{0})\sum_{i=1}^{n}a_{i}\\ &=n(x^{2}-y_{0}^{2})-2nxy_{0}+2ny_{0}^{2}\\ &=n(x^{2}-2xy_{0}+y_{0}^{2})=n(x-y_{0})^{2}\ge 0, \end{align}$

implying that the minimum is achieved at $\displaystyle y=\frac{a_{1}+\ldots+a_{n}}{n}.$

Is there a further modification/generalization?

Acknowledgment

The example came from an excellent book by Xu Jiagu, Lecture Notes on Mathematical Olympiad Courses, v 8, (For senior section, v 1), World Scientific, 2012, p.54

Absolute Value

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 62636461

Search by google: