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

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

¶Определение и формальное описание

Пусть заданы точки \(x_1, x_2, \dots, x_n\) в векторном пространстве (например, в \(\mathbb{R}^d\)). Выпуклой комбинацией этих точек называется выражение вида:

\[ y = \lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n, \]

где \(\lambda_i \geq 0\) для всех \(i = 1, \dots, n\) и \(\sum_{i=1}^n \lambda_i = 1\). Коэффициенты \(\lambda_i\) называются весами или барицентрическими координатами точки \(y\) относительно системы точек \(x_i\).

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

¶Свойства

• Выпуклость множества: Множество \(C\) является выпуклым тогда и только тогда, когда оно содержит все выпуклые комбинации любых двух своих точек. По индукции это распространяется на любое конечное число точек.
• Выпуклая оболочка: Множество всех выпуклых комбинаций точек из заданного множества \(S\) называется выпуклой оболочкой \(S\) и обозначается \(\operatorname{conv}(S)\). Это наименьшее выпуклое множество, содержащее \(S\).
• Непрерывность: Выпуклая комбинация является непрерывной функцией от коэффициентов \(\lambda_i\).
• Инвариантность относительно аффинных преобразований: Если применить аффинное преобразование \(T(x) = Ax + b\) к точкам \(x_i\), то выпуклая комбинация преобразованных точек равна \(T(y)\), где \(y\) — исходная выпуклая комбинация.
• Теорема Каратеодори: Любая точка выпуклой оболочки множества \(S \subset \mathbb{R}^d\) может быть представлена как выпуклая комбинация не более чем \(d+1\) точек из \(S\).

¶Геометрическая интерпретация

В евклидовом пространстве \(\mathbb{R}^d\) выпуклая комбинация двух точек — это отрезок, соединяющий эти точки. Выпуклая комбинация трёх неколлинеарных точек — это треугольник (включая его внутренность). Для четырёх точек в трёхмерном пространстве — это тетраэдр. В общем случае выпуклая комбинация \(n\) точек образует выпуклый многогранник, вершинами которого являются некоторые из этих точек (после отбрасывания точек, лежащих внутри выпуклой оболочки).

¶Применение

¶В оптимизации

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

¶В численных методах

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

¶В теории вероятностей и статистике

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

¶В экономике и теории игр

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

¶В компьютерной графике и геометрическом моделировании

• Барицентрические координаты: Используются для интерполяции цветов, текстур и других атрибутов внутри треугольника (в растеризации, в методе конечных элементов).
• Выпуклые оболочки: Алгоритмы построения выпуклой оболочки множества точек (например, алгоритм Джарвиса, алгоритм Грэхема) основаны на поиске точек, которые могут быть вершинами выпуклого многогранника, и последующем представлении всех остальных точек как выпуклых комбинаций вершин.

¶Примеры

1. Числовой пример: Пусть даны числа \(x_1 = 1\), \(x_2 = 5\). Выпуклая комбинация \(y = 0.3 \cdot 1 + 0.7 \cdot 5 = 0.3 + 3.5 = 3.8\). Любое число между 1 и 5 может быть получено как выпуклая комбинация этих двух чисел.
2. Геометрический пример: Точка \(P = (2, 3)\) может быть представлена как выпуклая комбинация точек \(A = (0, 0)\), \(B = (4, 0)\), \(C = (0, 6)\): \(P = 0.5 \cdot A + 0.25 \cdot B + 0.25 \cdot C\).
3. Векторный пример: В \(\mathbb{R}^3\) выпуклая комбинация трёх векторов \(v_1 = (1,0,0)\), \(v_2 = (0,1,0)\), \(v_3 = (0,0,1)\) с весами \((0.2, 0.3, 0.5)\) даёт вектор \((0.2, 0.3, 0.5)\).

¶Связь с другими понятиями

• Выпуклый конус: Если в определении выпуклой комбинации снять ограничение на сумму коэффициентов, но оставить неотрицательность, получается коническая комбинация, порождающая выпуклый конус.
• Аффинная оболочка: Множество всех аффинных комбинаций точек (с весами, сумма которых равна 1, но без ограничения неотрицательности) называется аффинной оболочкой. Выпуклая оболочка является подмножеством аффинной оболочки.
• Барицентр: Если все веса равны, выпуклая комбинация называется барицентром (центром масс) системы точек.

¶Интересные факты

• Понятие выпуклой комбинации восходит к работам Германа Минковского (конец XIX — начало XX века) в области геометрии чисел и выпуклых тел.
• Теорема Каратеодори (1911) гарантирует, что для представления любой точки выпуклой оболочки в \(\mathbb{R}^d\) достаточно не более \(d+1\) точек, что существенно упрощает многие алгоритмы.
• В функциональном анализе и теории меры понятие выпуклой комбинации обобщается до интеграла по вероятностной мере (теорема Шоке о представлении точек компактного выпуклого множества).

¶Источники

• Рокафеллар Р. Т. «Выпуклый анализ». — М.: Мир, 1973.
• Бойд С., Ванденберге Л. «Выпуклая оптимизация». — М.: Издательство МЦНМО, 2018.
• Каратеодори К. «О выпуклых оболочках конечных множеств точек» (Über den Variabilitätsbereich der Fourier’schen Konstanten von positiven harmonischen Funktionen), 1911.
• Препарата Ф., Шеймос М. «Вычислительная геометрия: введение». — М.: Мир, 1989.