Выпуклая комбинация

Выпуклая комбинация — одно из ключевых понятий выпуклой геометрии; линейная комбинация точек (которые могут быть векторами, скалярами или точками аффинного пространства), где все коэффициенты неотрицательны, и их сумма равна 1[1][2].

Даны три точки

x_{1},x_{2},x_{3}

на плоскости. Точка

P

является выпуклой комбинацией этих трёх точек, в то время как

Q

не является.
(

Q

является, однако, аффинной комбинацией этих трёх векторов, поскольку их аффинная оболочка совпадает со всей плоскостью.)

Более формально, если задано конечное число точек $x_{1},x_{2},\dots ,x_{n}$ в векторном пространстве над некоторым полем, содержащем поле вещественных чисел[1], выпуклая комбинация этих точек имеет вид

\alpha _{1}x_{1}+\alpha _{2}x_{2}+\cdots +\alpha _{n}x_{n}

,

где вещественные числа $\alpha _{i}$ удовлетворяют условиям $\alpha _{i}\geqslant 0$ и $\alpha _{1}+\alpha _{2}+\cdots +\alpha _{n}=1$ .

В частности, любая выпуклая комбинация двух точек лежит на отрезке между этими точками.

Все выпуклые комбинации точек лежат внутри выпуклой оболочки этих точек.

Существуют подмножества векторного пространства, замкнутые относительно выпуклой комбинации, но не замкнутые относительно линейной. Например, интервал $[0,1]$ является выпуклым, но линейные комбинации точек этого интервала дают всю прямую. Другой пример — выпуклое множество распределений вероятностей.

Другие объекты

Подобно выпуклой комбинации векторов, выпуклая комбинация $X$ распределений вероятностей $Y_{i}$ — это взвешенная сумма (где $\alpha _{i}$ удовлетворяют тем же ограничениям, что и выше) распределений вероятностей с плотностью вероятности
$f_{X}(x)=\sum _{i=1}^{n}\alpha _{i}f_{Y_{i}}(x)$ .

Связанные построения

Коническая комбинация — это линейная комбинация с неотрицательными коэффициентами.
Средние арифметические взвешенные — это, функционально, то же самое, что и выпуклая комбинация, но используются другие обозначения. Для коэффициентов (весов) во взвешенном среднем не требуется равенство единице суммы весов. Вместо этого линейную комбинацию делят на сумму весов.
Аффинные комбинации подобны выпуклым комбинациям, но не требуется неотрицательность коэффициентов. Ввиду этого аффинные комбинации определены на векторном пространстве над любым полем.

Неравенства

Выпуклые комбинации вещественных чисел подчиняются простым, но часто используемым неравенствам[1].

Если задан набор вещественных чисел $x_{1},\dots ,x_{n}$ , то для любой их выпуклой комбинации с коэффициентами $a_{1},\dots ,a_{n}\geqslant 0,a_{1}+\dots +a_{n}=1$ имеют место оценки:

\min _{1\leqslant i\leqslant n}x_{i}\leqslant \sum _{i=1}^{n}a_{i}x_{i}\leqslant \max _{1\leqslant i\leqslant n}x_{i}

.

Различные классические неравенства можно вывести, рассматривая простые выпуклые функции $f(\cdot )$ , например:

f{\Big (}\sum _{i=1}^{n}a_{i}x_{i}{\Big )}\leqslant \sum _{i=1}^{n}a_{i}f(x_{i})

,

где $a_{i}\geqslant 0,a_{1}+\dots +a_{n}=1$ .

Применение последнего неравенства к строго выпуклой функции $f(x)=-log~x$ приводит к неравенству между арифметическим и геометрическим средними с весами:

\sum _{i=1}^{n}a_{i}x_{i}\geqslant \prod _{i=1}^{n}x_{i}^{a_{i}},\,x_{i}\geqslant 0

.

Когда все $a_{i}$ равны 1/n, приходим к неравенству между арифметическим и геометрическим средними:

{\frac {1}{n}}\sum _{i=1}^{n}x_{i}\geqslant {\Big (}\prod _{i=1}^{n}x_{i}{\Big )}^{1/n},\,x_{i}\geqslant 0

.

См. также

Примечания

Р. Хорн, Ч. Джонсон. Матричный анализ. — М.: Мир, 1989. — С. 630—637. — ISBN 5-03-001042-4.
Е. Е. Тыртышников. 13.5 Выпуклые множества // Матричный анализ и линейная алгебра: Учебное пособие. — Москва: Московский Университет (eBook), 2005. — С. 90.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Horn-1] Р. Хорн, Ч. Джонсон. Матричный анализ. — М.: Мир, 1989. — С. 630—637. — ISBN 5-03-001042-4.

[2] Е. Е. Тыртышников. 13.5 Выпуклые множества // Матричный анализ и линейная алгебра: Учебное пособие. — Москва: Московский Университет (eBook), 2005. — С. 90.