Средний через минимакс

Question

_{Предупреждение: размещено на сайте Mathematics SE.}

---

Данный вектор ${\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}$$

это (арифметическое) среднее значение элементов вектора${\rm a} \in \Bbb R^n$, в то время как

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

является медианой элементов вектора${\rm a} \in \Bbb R^n$. Используя$\infty$-Норм вместо этого, что следующее?

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

Похоже, что это средний диапазон . Прилагаю доказательство, основанное на линейном программировании. Если предположить, что я не сделал ошибок и мое доказательство действительно верно, меня интересуют другие доказательства и ссылки .

---

Мое доказательство

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

Введение в переменную оптимизации $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} $$

или, альтернативно,

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

Пусть элементы вектора ${\rm a} \in \Bbb R^n$ обозначать $a_1, a_2, \dots, a_n$. Обратите внимание, что существует множество повторяющихся неравенств:

• набор $n$ неравенство ${\rm a} \leq (x + y) {\Bbb 1}_n$ можно заменить на $$x + y \geq \max \{ a_1, a_2, \dots, a_n \}$$

• набор $n$ неравенство $(x - y) {\Bbb 1}_n \leq {\rm a}$ можно заменить на $$x - y \leq \min \{ a_1, a_2, \dots, a_n \}$$

Следовательно,

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

Некоторые называют это значение по середине диапазона от$\{ a_1, a_2, \dots, a_n \}$.

Answer 1

1. Графическая демонстрация

Компоненты вектора $a$ показаны синими галочками («коврик»). $\tilde m$это средний диапазон. Это происходит при минимально возможном значении верхней огибающей графиков функций расстояния$x\to |x-a_i|,$ показан красным.

2. Элементарная демонстрация с использованием числовых свойств.

Эта демонстрация по существу объясняет график строго: он указывает, что верхняя красная огибающая состоит из двух наклонных плеч, пересекающихся в середине диапазона.

Сначала давайте настроим некоторые обозначения.

Эта целевая функция представляет собой максимальное расстояние между числом $x$ и набор компонентов $a$(подмножество действительных чисел). Написать$a_1$ для наименьшего из этих компонентов и $a_n$для величайшего. Позволять$\tilde m = (a_1+a_n)/2$ их средний диапазон, для которого максимальное расстояние $r = (a_n-a_1)/2.$

Итак, вот демонстрация:

Если $x \lt \tilde m$ тогда $|x-a_n| \gt r$ и если $x \gt \tilde m$ тогда $x-a_1 \gt r.$ Следовательно, единственный возможный кандидат на минимизацию целевой функции - это $\tilde m$сама, QED.