0

For $n$ scalars $a_1,...,a_n$, find the solution of $$\min_{x \in \mathbb R}\sum^n_{i=1} |x - a_i|$$ I denoted $$\delta(x) = \sum^n_{i=1} |x - a_i| $$ and found $$ \delta'(x) = \sum^n_{i=1} \frac{x-a_i}{|x - a_i|}$$

However, this function is not convex so just finding the critical points won't help. In any case, I still attempted it and got to the following equation $$\mathbf b^T \mathbf c= \mathbf b^T \mathbf a $$ where $$ \mathbf a = \begin{bmatrix} a_1 \\ \vdots \\ a_n \\ \end{bmatrix}, \mathbf b = \begin{bmatrix} \frac {1}{c+a_1} \\ \vdots \\ \frac {1}{c+a_n} \\ \end{bmatrix}, \ \mathbf c = \begin{bmatrix} c \\ \vdots \\ c \\ \end{bmatrix}, $$ with $c$ being such that $$ \delta' (c) = 0$$

I am not sure if I am going in the right direction and if there is a straightforward method for approaching this problem.

Lucas Alanis
  • 1,406

1 Answers1

1

Suppose all $a_i$ are distinct.

Just remark that, when you have more points on one side than on the other side, you can always move towards the direction with more points to reduce the value function.

So finally, if the number of $a_i$ are odd, take $x$ equal to the median. If the number of $a_i$ are even, take any $x$ between the two $a_i$'s in the middle.

Petite Etincelle
  • 14,767