Mid-range via minimax Warning: crossposted at Statistics SE.

Given vector ${\rm a} \in \Bbb R^n$,
$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_2^2\end{array} = \frac1n {\Bbb 1}_n^\top {\rm a} \tag{mean}$$
is the (arithmetic) mean of the entries of vector ${\rm a}  \in \Bbb R^n$, whereas
$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_1\end{array} \tag{median}$$
is a median of the entries of vector ${\rm a}  \in \Bbb R^n$. Using the $\infty$-norm instead, what is the following?
$$\color{blue}{\boxed{\,\\\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array}}}$$
It appears to be the mid-range. I append a proof based on linear programming. Assuming that I have made no mistakes and my proof is indeed correct, I am interested in other proofs and in references.

My proof
$$\begin{array}{ll} \underset{x \in {\Bbb R}}{\text{minimize}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array} $$
Introducing optimization variable $y \in {\Bbb R}$,
$$\begin{array}{ll} \underset{x, y \in {\Bbb R}}{\text{minimize}} & \qquad\qquad y\\ \text{subject to} & -y {\Bbb 1}_n \leq x {\Bbb 1}_n - {\rm a} \leq y {\Bbb 1}_n\end{array} $$
or, alternatively,
$$\begin{array}{lrl} \underset{x, y \in {\Bbb R}}{\text{minimize}} & y & \\ \text{subject to} & {\rm a} & \leq (x + y) {\Bbb 1}_n \\ & (x - y) {\Bbb 1}_n & \leq {\rm a}\end{array}$$
Let the entries of vector ${\rm a} \in \Bbb R^n$ be denoted by $a_1, a_2, \dots, a_n$. Note that there are many redundant inequalities:

*

*the set of $n$ inequalities ${\rm a} \leq (x + y) {\Bbb 1}_n$ can be replaced by $$x + y \geq \max \{ a_1, a_2, \dots, a_n \}$$


*the set of $n$ inequalities $(x - y) {\Bbb 1}_n \leq {\rm a}$ can be replaced by $$x - y \leq \min \{ a_1, a_2, \dots, a_n \}$$
Subtracting the latter inequality from the former inequality,
$$y \geq \frac{ \max \{ a_1, a_2, \dots, a_n \} - \min \{ a_1, a_2, \dots, a_n \} }{2} =: y_{\min}$$
and, thus,
$$ \begin{aligned} x &\geq \max \{ a_1, a_2, \dots, a_n \} - y_{\min} = \frac{ \min \{ a_1, a_2, \dots, a_n \} + \max \{ a_1, a_2, \dots, a_n \} }{2} \\\\ x &\leq \min \{ a_1, a_2, \dots, a_n \} + y_{\min} = \frac{ \min \{ a_1, a_2, \dots, a_n \} + \max \{ a_1, a_2, \dots, a_n \} }{2} \end{aligned} $$
Hence,
$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array} = \color{blue}{\frac{ \min \{ a_1, a_2, \dots, a_n \} + \max \{ a_1, a_2, \dots, a_n \} }{2}}$$
Some call this value the mid-range of $\{ a_1, a_2, \dots, a_n \}$.

Related

*

*Centroid under the Chebyshev distance


*The median minimizes the sum of absolute deviations (the $ {\ell}_{1} $ norm)


*Average of minimum and maximum in set


*What minimizes the Chebyshev Distance?


*Term for center of dataset
 A: I cannot follow the 'hence' step. The two inequalities you have are equivalent to:
$$y \geq \max\{a_1, a_2, \ldots, a_n\} - x$$
$$y \geq x -\min\{a_1, a_2, \ldots, a_n\}$$
so the objective is:
$$\arg\min_{x \in \Bbb R} \max\{\max\{a_1, a_2, \ldots, a_n\} - x, x -\min\{a_1, a_2, \ldots, a_n\}\}$$
This is a univariate convex function with slope -1 left of the breakpoint and slope +1 right of the breakpoint. So the minimum is attained at the breakpoint. At the breakpoint, $x$ satisfies
$$\max\{a_1, a_2, \ldots, a_n\} - x = x - \min\{a_1, a_2, \ldots, a_n\}$$
so
$$x = \frac{\min\{a_1, a_2, \ldots, a_n\} + \max\{a_1, a_2, \ldots, a_n\}}{2}$$
A: Here is an alternative proof based on duality theory. The dual problem is:
\begin{align}
\min_x ||x1-a||_\infty &= \min_{x,y} \left\{ ||y||_\infty : y=x1-a \right\} \\
&= \min_{x,y} \max_z \left\{ ||y||_\infty + z^T(y-x1+a) \right\} \\
&= \max_z \min_{x,y} \left\{ ||y||_\infty + z^T(y-x1+a) \right\} \\
&= \max_z \left\{ z^Ta - \max_y\{-z^Ty - ||y||_\infty\} + \min_x \{ -x z^T1\} \right\} \\
&= \max_z \left\{ z^Ta : ||z||_1\leq 1, z^T1=0 \right\} \\
\end{align}
The third step uses strong duality, the last step uses the conjugate norm of $y$. Let $z$ be a vector with value $0.5$ at a position where $a$ has its largest element, $-0.5$ at a position where $a$ has its smallest element, and $0$ everywhere else, then the dual objective value is $0.5(a_{max} - a_{min})$. By weak duality, the objective value of the dual is a lower bound for the primal, proving that the primal solution you found is optimal.
