Mid-range via minimax
Aviso: crossposted em Statistics SE.
Dado vetor ${\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}$$
é a média (aritmética) das entradas do vetor${\rm a} \in \Bbb R^n$, enquanto que
$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_1\end{array} \tag{median}$$
é uma mediana das entradas do vetor${\rm a} \in \Bbb R^n$. Usando o$\infty$-norm em vez disso, o que é o seguinte?
$$\color{blue}{\boxed{\,\\\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array}}}$$
Parece ser a faixa intermediária . Anexo uma prova baseada na programação linear. Supondo que não cometi erros e que minha prova esteja realmente correta, estou interessado em outras provas e em referências .
Minha prova
$$\begin{array}{ll} \underset{x \in {\Bbb R}}{\text{minimize}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array} $$
Apresentando a variável de otimização $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} $$
ou alternativamente,
$$\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}$$
Deixe as entradas do vetor ${\rm a} \in \Bbb R^n$ ser denotado por $a_1, a_2, \dots, a_n$. Observe que existem muitas desigualdades redundantes:
o conjunto de $n$ desigualdades ${\rm a} \leq (x + y) {\Bbb 1}_n$ pode ser substituído por $$x + y \geq \max \{ a_1, a_2, \dots, a_n \}$$
o conjunto de $n$ desigualdades $(x - y) {\Bbb 1}_n \leq {\rm a}$ pode ser substituído por $$x - y \leq \min \{ a_1, a_2, \dots, a_n \}$$
Conseqüentemente,
$$\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}}$$
Alguns chamam esse valor de intervalo médio de$\{ a_1, a_2, \dots, a_n \}$.
Relacionados
Centróide sob a distância Chebyshev
A mediana minimiza a soma dos desvios absolutos (o $ {\ell}_{1} $ norma)
Média de mínimo e máximo no conjunto
O que minimiza a distância de Chebyshev?
Termo para centro do conjunto de dados
Respostas
Não posso seguir o passo 'daí'. As duas desigualdades que você tem são equivalentes a:$$y \geq \max\{a_1, a_2, \ldots, a_n\} - x$$ $$y \geq x -\min\{a_1, a_2, \ldots, a_n\}$$ então o objetivo é: $$\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\}\}$$Esta é uma função convexa univariada com inclinação -1 à esquerda do ponto de interrupção e inclinação +1 à direita do ponto de interrupção. Portanto, o mínimo é atingido no ponto de interrupção. No breakpoint,$x$ satisfaz $$\max\{a_1, a_2, \ldots, a_n\} - x = x - \min\{a_1, a_2, \ldots, a_n\}$$ então $$x = \frac{\min\{a_1, a_2, \ldots, a_n\} + \max\{a_1, a_2, \ldots, a_n\}}{2}$$
Aqui está uma prova alternativa baseada na teoria da dualidade. O duplo problema é:\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} A terceira etapa usa dualidade forte, a última etapa usa a norma conjugada de $y$. Deixei$z$ ser um vetor com valor $0.5$ em uma posição onde $a$ tem seu maior elemento, $-0.5$ em uma posição onde $a$ tem seu menor elemento, e $0$ em qualquer outro lugar, então o valor objetivo duplo é $0.5(a_{max} - a_{min})$. Por dualidade fraca, o valor objetivo do dual é um limite inferior para o primal, provando que a solução primal que você encontrou é ótima.