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

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

Даны три точки $x_1,x_2,x_3$$x_{1},x_{2},x_{3}$ на плоскости. Точка $P$$P$ является выпуклой комбинацией этих трёх точек, в то время как $Q$$Q$ не является.
($Q$$Q$ является, однако, аффинной комбинацией этих трёх векторов, поскольку их аффинная оболочка совпадает со всей плоскостью.)

Более формально, если задано конечное число точек $x_1,x_2,\dots <!--\; \dots \; -->,x_n$$x_{1},x_{2},\dots ,x_{n}$ в векторном пространстве над некоторым полем, содержащем поле вещественных чисел, выпуклая комбинация этих точек имеет вид

${\mathrm{\alpha <!--\; \alpha \; -->}}_1{x}_1+{\mathrm{\alpha <!--\; \alpha \; -->}}_2{x}_2+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_n{x}_n$$\alpha _{1}x_{1}+\alpha _{2}x_{2}+\cdots +\alpha _{n}x_{n}$,

где вещественные числа ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$ удовлетворяют условиям ${\mathrm{\alpha <!--\; \alpha \; -->}}_i⩾<!--\; ⩾\; -->0$$\alpha _{i}\geqslant 0$ и ${\mathrm{\alpha <!--\; \alpha \; -->}}_1+{\mathrm{\alpha <!--\; \alpha \; -->}}_2+\cdots <!--\; \cdots \; -->+{\mathrm{\alpha <!--\; \alpha \; -->}}_n=1$$\alpha _{1}+\alpha _{2}+\cdots +\alpha _{n}=1$.

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

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

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

Другие объектыПравить

• Подобно выпуклой комбинации векторов, выпуклая комбинация $X$$X$  распределений вероятностей $Y_i$$Y_{i}$  — это взвешенная сумма (где ${\mathrm{\alpha <!--\; \alpha \; -->}}_i$$\alpha_i$  удовлетворяют тем же ограничениям, что и выше) распределений вероятностей с плотностью вероятности

  $f_X(x)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}_i{f}_{Y_i}(x)$$f_{X}(x)=\sum _{i=1}^{n}\alpha _{i}f_{Y_{i}}(x)$ .

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

Подробнее см. Линейная комбинация § Аффинная, коническая и выпуклая комбинации

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

НеравенстваПравить

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

Если задан набор вещественных чисел $x_1,\dots <!--\; \dots \; -->,x_n$$x_{1},\dots ,x_{n}$ , то для любой их выпуклой комбинации с коэффициентами $a_1,\dots <!--\; \dots \; -->,a_n⩾<!--\; ⩾\; -->0,a_1+\cdots <!--\; \cdots \; -->+a_n=1$$a_{1},\dots ,a_{n}\geqslant 0,a_{1}+\dots +a_{n}=1$  имеют место оценки:

$\underset{1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->n}{min}{x}_i⩽<!--\; ⩽\; -->\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_i{x}_i⩽<!--\; ⩽\; -->\underset{1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->n}{max}{x}_i$$\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 <!--\; \cdot \; -->)$$f(\cdot )$ , например:

$f(\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_i{x}_i)⩽<!--\; ⩽\; -->\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_{i}f(x_i)$$f{\Big (}\sum _{i=1}^{n}a_{i}x_{i}{\Big )}\leqslant \sum _{i=1}^{n}a_{i}f(x_{i})$ ,

где $a_i⩾<!--\; ⩾\; -->0,a_1+\cdots <!--\; \cdots \; -->+a_n=1$$a_{i}\geqslant 0,a_{1}+\dots +a_{n}=1$ .

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

$\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_i{x}_i⩾<!--\; ⩾\; -->\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{x}_i^{a_i},x_i⩾<!--\; ⩾\; -->0$$\sum _{i=1}^{n}a_{i}x_{i}\geqslant \prod _{i=1}^{n}x_{i}^{a_{i}},\,x_{i}\geqslant 0$ .

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

$\frac{1}{n}\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{x}_i⩾<!--\; ⩾\; -->(\underset{i=1}{\overset{n}{\prod <!--\; \prod \; -->}}{x}_i{)}^{1/n},x_i⩾<!--\; ⩾\; -->0$${\frac {1}{n}}\sum _{i=1}^{n}x_{i}\geqslant {\Big (}\prod _{i=1}^{n}x_{i}{\Big )}^{1/n},\,x_{i}\geqslant 0$ .

См. такжеПравить

• Аффинная оболочка
• Теорема Каратеодори о выпуклой оболочке
• Выпуклая оболочка
• Симплекс
• Барицентрические координаты