Minimize $\sum_{i=1}^n|x-a_i|$, $\max \{|x-a_i|, i=1,\cdots,n\}$, $\sum_{i=1}^n|x-a_i|^2$ and maximize $\Pi_{i=1}^n|x-a_i|$

Question

$a_1\le a_2\le \cdots \le a_n$ real numbers.

a) Minimize $\sum_{i=1}^n|x-a_i|$

b) Minimize $\max \{|x-a_i|, i=1,\cdots,n\}$

c) Minimize $\sum_{i=1}^n|x-a_i|^2$

d) Maximize $\Pi_{i=1}^n|x-a_i|$

a), if we take the derivative, we get

$$f(x) = \sum_{i=1}^n|x-a_i|\implies \frac{df}{dx} = \mbox{signal(x)}n$$

So the derivative is never $0$, but I can't say that a minimum for this funciton has to have derivative $0$ because this function is not continuously differentiable. However we can see that for $x>0$ the function is increasing and $x<0$ it is decreasing. I understand that the median is the point, but I need to prove analytically that $f$ indeed is smaller than $f$ in every other point. I've seen The Median Minimizes the Sum of Absolute Deviations (The $ {L}_{1} $ Norm) but I found no analytical proofs for the median being the minimizer, only explanations about how to find with some intuition that the median is smaller

b) I don't have an idea about this one

c) $$f(x) = |x-a_1|^2 + |x-a_2|^2 + \cdots + |a-x_n|^2$$

$$\frac{df}{dx} = 2|x-a_1| + \cdots + 2|x-a_n|$$

The derivative is always positive or 0, so the function is always increasing. This one is continuous so by making it equal to $0$ I should try to find points that satisfy the equality. I don't think there exists one, so I would say the derivative is always positive. How should I proceed?

d) The exercise gives no information about a bounary for $x$, so if I pick larger and larger $x$ shouldn't the funciton grow infinitely?

UPDATE:

b)

Let $x^* = \frac{a_1+a_n}{2}$. If $a_1<x<x^*$ then $\max\{|x-a_i|, i=1,\cdots,n\} = a_n-x$ which is decreasing. If $x>x^*$ then $\max\{|x-a_i|, i=1,\cdots,n\} = x-a_1$ which is increasing. Therefore the minimum must be at $x^*$. I think I need to argue better why, for example, $\max\{|x-a_i|, i=1,\cdots,n\} = a_n-x$

I need a more rigorous proof.

Answer 1

a) The top answer to the linked question does provide the outline of a formal proof, it's just disguised a little. A more formal outline would go something like this: the function $\sum_i|x-a_i|$ is continuous as a function of $x$. It is decreasing on the domain $(-\infty,a_{n/2})$ and increasing on the domain $(a_{n/2},\infty)$. Hence, the minimum must occur at $a_{n/2}$ (of course I'm being quite sloppy when I say $a_{n/2}$. Read the conversation on the linked post for more precise definition of the "median"). This should lead to a perfectly rigorous proof (no derivatives/subgradients required).

b) The answer is the midpoint between $a_1$ and $a_n$ (i.e. $(a_1+a_n)/2$). See if you can work backwards from this answer.

c) Note that

\begin{equation} \sum_{i=1}^n|x-a_i|^2=\sum_{i=1}^n(x-a_i)^2. \end{equation} Taking the derivative w.r.t $x$ we obtain \begin{equation} 2\sum_{i=1}^n(x-a_i)=2nx-2\sum_{i=1}^na_i. \end{equation} Setting this equal to zero and solving for $x$, we obtain \begin{equation} x^*=\frac{1}{n}\sum_{i=1}^na_i, \end{equation} i.e. the arithmetic mean of the $a_i$. Since the function $\sum_i(x-a_i)^2$ is convex and continuously differentiable as a function of $x$, this is sufficient to conclude that $x^*$ is a global minimizer.

d) Your intuition is correct--as stated, the function is unbounded. A more interesting problem might be to consider maximizing the product over the domain $[a_1,a_n]$. This could be a good exercise.