Mid-range via minimax

Question

_{Aviso: crossposted em Mathematics 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 média . 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 \}$.

Answer 1

1. Demonstração gráfica

Os componentes do vetor $a$ são mostrados com marcas azuis (um "gráfico de tapete"). $\tilde m$é o médio. Ocorre no menor valor possível do envelope superior dos gráficos das funções de distância$x\to |x-a_i|,$ mostrado em vermelho.

2. Demonstração elementar usando propriedades numéricas

Esta demonstração explica essencialmente o gráfico de forma rigorosa: ela mostra que o envelope vermelho superior consiste em dois braços inclinados que se encontram na faixa média.

Primeiro, vamos configurar alguma notação.

Esta função objetivo é a distância máxima entre o número $x$ e o conjunto de componentes de $a$(um subconjunto dos números reais). Escreva$a_1$ pelo menos desses componentes e $a_n$para o maior. Deixei$\tilde m = (a_1+a_n)/2$ ser sua gama média, para a qual a distância máxima é $r = (a_n-a_1)/2.$

Aqui, então, está a demonstração:

E se $x \lt \tilde m$ então $|x-a_n| \gt r$ e se $x \gt \tilde m$ então $x-a_1 \gt r.$ Consequentemente, o único candidato possível para minimizar a função objetivo é $\tilde m$em si, QED.