1
$\begingroup$

Let $a_0,a_1,\ldots,a_n$ be a strictly increasing sequence. Find the minimum and maximum of $f(x) = \displaystyle \sum_{k=0}^n (x-a_k)^2$.

Attempt

We have $$\begin{aligned} f(x) &= (x-a_0)^2+(x-a_1)^2+\cdots+(x-a_n)^2 \\ &= (n+1)x^2-2(a_0+\cdots+a_n)x+(a_0^2+\cdots+a_n^2) \end{aligned}$$ so we take the first derivative and set it equal to $0$ to get $x = \dfrac{a_0+\cdots+a_n}{n+1}$. Is this the minimum?

$\endgroup$
2
  • 1
    $\begingroup$ How about computing the second derivative? $\endgroup$ Mar 15, 2016 at 0:13
  • $\begingroup$ By the way, the hypothesis that $a_0,a_1,\ldots,a_n$ is strictly increasing is irrelevant. The result does not depend on this in any way. $\endgroup$
    – user169852
    Mar 15, 2016 at 0:28

1 Answer 1

3
$\begingroup$

Each term in the sum $(x-a_k)^2$ is a convex function. Since the sum of convex functions is convex, $f$ is a convex.

Thus, the point where $f'(x)=0$ is a global minimum. The function has no global maximum.

Note that minimizing this function attempts to find the $x$ that minimizes the "squared error" or rather, Euclidian distance, to a bunch of data points: $a_k$. The minimizer turns out to be the sample mean $\frac{1}{n}\sum a_k$. More formally:

(Edit: note that I will start at $k=1$ while you started at $k=0$. This explains the difference between $n+1$ and $n$ in our final answers)

$$f'(x)=0$$ $$\sum_{k=1}^n2(x-a_k)=0$$ $$2\sum_{k=1}^n(x-a_k)=0$$ $$\sum_{k=1}^n(x-a_k)=0$$ $$\sum_{k=1}^nx=\sum_{k=1}^na_k$$ $$nx=\sum_{k=1}^na_k$$ $$x=\frac{1}{n}\sum_{k=1}^na_k$$

$\endgroup$
4
  • $\begingroup$ I get $x = \dfrac{a_0+\cdots+a_n}{n+1}$. $\endgroup$ Mar 15, 2016 at 0:27
  • $\begingroup$ I see why. You start at $k=0$ I start at $k=1$. $\endgroup$
    – CommonerG
    Mar 15, 2016 at 0:28
  • $\begingroup$ How do we find the minimum value of the function from this $x$ or does it not turn out nicely? $\endgroup$ Mar 15, 2016 at 0:29
  • $\begingroup$ I suspect it won't turn out nicely. $\endgroup$
    – CommonerG
    Mar 15, 2016 at 0:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .