Midrange tramite minimax
Avvertimento: crossposted a Statistics 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 \}$.
Relazionato
Centroide sotto la distanza di Chebyshev
La mediana minimizza la somma delle deviazioni assolute (il $ {\ell}_{1} $ norma)
Media di minimo e massimo nel set
Cosa riduce al minimo la distanza di Chebyshev?
Termine per il centro del set di dati
Risposte
Non riesco a seguire il passaggio "da qui". Le due disuguaglianze che hai sono equivalenti a:$$y \geq \max\{a_1, a_2, \ldots, a_n\} - x$$ $$y \geq x -\min\{a_1, a_2, \ldots, a_n\}$$ quindi l'obiettivo è: $$\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\}\}$$Questa è una funzione convessa univariata con pendenza -1 a sinistra del punto di interruzione e pendenza +1 a destra del punto di interruzione. Quindi il minimo viene raggiunto al breakpoint. Al punto di interruzione,$x$ soddisfa $$\max\{a_1, a_2, \ldots, a_n\} - x = x - \min\{a_1, a_2, \ldots, a_n\}$$ così $$x = \frac{\min\{a_1, a_2, \ldots, a_n\} + \max\{a_1, a_2, \ldots, a_n\}}{2}$$
Ecco una prova alternativa basata sulla teoria della dualità. Il duplice 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} Il terzo passaggio utilizza una forte dualità, l'ultimo passaggio utilizza la norma coniugata di $y$. Permettere$z$ essere un vettore con valore $0.5$ in una posizione in cui $a$ ha il suo elemento più grande, $-0.5$ in una posizione in cui $a$ ha il suo elemento più piccolo e $0$ dappertutto, allora il duplice valore oggettivo è $0.5(a_{max} - a_{min})$. Per dualità debole, il valore oggettivo del duale è un limite inferiore per il primale, dimostrando che la soluzione primaria che hai trovato è ottimale.