Midrange tramite minimax

Question

_{Avvertimento: crossposted at Mathematics SE.}

---

Dato vettore ${\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}$$

è la media (aritmetica) delle voci del vettore${\rm a} \in \Bbb R^n$, mentre

$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_1\end{array} \tag{median}$$

è una mediana delle voci del vettore${\rm a} \in \Bbb R^n$. Usando il$\infty$-normale invece, cos'è il seguente?

$$\color{blue}{\boxed{\,\\\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array}}}$$

Sembra essere la fascia media . Aggiungo una dimostrazione basata sulla programmazione lineare. Supponendo che non abbia commesso errori e che la mia dimostrazione sia effettivamente corretta, mi interessano altre prove e riferimenti .

---

La mia prova

$$\begin{array}{ll} \underset{x \in {\Bbb R}}{\text{minimize}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_{\infty}\end{array} $$

Introduzione della variabile di ottimizzazione $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} $$

o, in alternativa,

$$\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}$$

Lasciate che le voci di vettore ${\rm a} \in \Bbb R^n$ essere denotato da $a_1, a_2, \dots, a_n$. Nota che ci sono molte disuguaglianze ridondanti:

• il set di $n$ disuguaglianze ${\rm a} \leq (x + y) {\Bbb 1}_n$ può essere sostituito da $$x + y \geq \max \{ a_1, a_2, \dots, a_n \}$$

• il set di $n$ disuguaglianze $(x - y) {\Bbb 1}_n \leq {\rm a}$ può essere sostituito da $$x - y \leq \min \{ a_1, a_2, \dots, a_n \}$$

Quindi,

$$\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}}$$

Alcuni chiamano questo valore la fascia media di$\{ a_1, a_2, \dots, a_n \}$.

Answer 1

1. Dimostrazione grafica

Le componenti del vettore $a$ sono indicati con segni di spunta blu (un "intreccio di tappeti"). $\tilde m$è la gamma media. Si verifica al valore più basso possibile dell'inviluppo superiore dei grafici delle funzioni di distanza$x\to |x-a_i|,$ mostrato in rosso.

2. Dimostrazione elementare utilizzando le proprietà dei numeri

Questa dimostrazione spiega essenzialmente il grafico in modo rigoroso: indica che l'involucro rosso superiore è costituito da due bracci inclinati che si incontrano nella gamma media.

Per prima cosa impostiamo una notazione.

Questa funzione obiettivo è la distanza massima tra il numero $x$ e l'insieme di componenti di $a$(un sottoinsieme dei numeri reali). Scrivi$a_1$ per il minimo di quei componenti e $a_n$per il più grande. Permettere$\tilde m = (a_1+a_n)/2$ essere la loro gamma media, per la quale la distanza massima è $r = (a_n-a_1)/2.$

Ecco, quindi, la dimostrazione:

Se $x \lt \tilde m$ poi $|x-a_n| \gt r$ e se $x \gt \tilde m$ poi $x-a_1 \gt r.$ Di conseguenza, l'unico possibile candidato per ridurre al minimo la funzione obiettivo è $\tilde m$stesso, QED.