Выпуклые множества

Почему GPS строит маршрут за секунды, а не за часы? Почему нейросеть обучается, а не застревает навечно? За всем этим стоит одна геометрическая идея: выпуклость. Если область поиска выпуклая - спуск вниз гарантированно приводит к лучшему решению. Без ловушек, без тупиков.

• **Logistics:** задачи маршрутизации сводятся к оптимизации на выпуклых многогранниках - пересечениях ограничений на ресурсы
• **Machine Learning:** функция потерь в линейной регрессии выпуклая - gradient descent находит глобальный минимум
• **Finance:** множество допустимых портфелей (ограничения на доли активов) - выпуклый многогранник

Выпуклое множество

Аналогия: резинка, натянутая между двумя кнопками на доске. Если вся резинка всегда остаётся внутри фигуры - фигура **выпуклая**. Если резинка вылезает наружу - нет.

Формально: множество S называется **выпуклым**, если для любых двух точек x, y из S и любого коэффициента 0 <= t <= 1 точка tx + (1-t)y тоже принадлежит S. Другими словами, отрезок между любыми двумя точками множества полностью лежит внутри.

**Ключевое свойство:** пересечение любого количества выпуклых множеств - снова выпуклое множество. Это позволяет строить сложные выпуклые области из простых.

Полупространство

**Полупространство** - это множество всех точек по одну сторону от гиперплоскости. В 2D это полуплоскость (всё выше прямой), в 3D - полупространство (всё ниже плоскости). Математически: {x | aᵀx <= b}, где a - вектор нормали, b - смещение.

Вектор **a** задаёт направление нормали к границе. Граница - это гиперплоскость {x | aᵀx = b}. Все точки с aᵀx < b лежат строго внутри, точки на границе удовлетворяют aᵀx = b.

**Почему это важно:** полупространство - простейшее выпуклое множество после всего пространства. Линейные ограничения в оптимизации (ax <= b) - это именно полупространства.

Доказать выпуклость полупространства просто. Пусть x, y удовлетворяют aᵀx <= b и aᵀy <= b. Тогда для 0 <= t <= 1: aᵀ(tx + (1-t)y) = t(aᵀx) + (1-t)(aᵀy) <= tb + (1-t)b = b. Линейность скалярного произведения всё делает за нас.

Многогранники

**Многогранник (polyhedron)** - это пересечение конечного числа полупространств. Каждое линейное неравенство отсекает часть пространства, и то, что остаётся в пересечении - многогранник.

В компактной записи многогранник - это {x | Ax <= b, Cx = d}, где A - матрица коэффициентов неравенств, C - матрица равенств. Каждая строка матрицы A задаёт одно полупространство.

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

Многогранник может быть ограниченным (политоп) или неограниченным. Например, {x | x₁ >= 0, x₂ >= 0} - первый квадрант, неограниченный многогранник. Политоп - это многогранник, который можно поместить в шар конечного радиуса.

Выпуклый конус

**Выпуклый конус** - это множество C, замкнутое относительно положительного масштабирования: если x принадлежит C, то и tx принадлежит C для любого t >= 0. Конус обязательно содержит начало координат (при t = 0).

Выпуклый конус - это конус, который одновременно является выпуклым множеством. То есть для любых x, y из C и t1, t2 >= 0: t1·x + t2·y тоже принадлежит C. Это называется **коническая комбинация**.

**Иерархия оптимизации:** LP (линейное) использует ортант R₊ⁿ, SOCP (second-order cone) - конус Лоренца, SDP (semidefinite) - PSD-конус. Каждый следующий тип мощнее, но сложнее вычислительно.

Вернёмся к нашей резинке: конус - это как два луча из начала координат и всё пространство между ними. Растяжение любой точки вдоль луча из нуля оставляет её в конусе. Именно поэтому конусы описывают ограничения вида 'неотрицательность', 'порядок' и 'полуопределённость' - фундаментальные для оптимизации.

Ключевые идеи

• **Выпуклое множество:** отрезок между любыми двумя точками целиком лежит внутри
• **Полупространство** {x | aᵀx <= b} - атом выпуклости, из которого строятся сложные области
• **Многогранник** - пересечение конечного числа полупространств, допустимая область LP
• **Выпуклый конус** - замкнут относительно масштабирования и сложения, основа иерархии LP → SOCP → SDP

Связанные темы

Выпуклые множества - фундамент для всей теории оптимизации:

• Выпуклые функции — Определяются через эпиграф - выпуклое множество в пространстве на 1 размерность больше
• Задача выпуклой оптимизации — Допустимое множество задачи - пересечение выпуклых множеств

Вопросы для размышления

• Пересечение выпуклых множеств выпукло. А что с объединением? Приведите контрпример.
• Как геометрически выглядит PSD-конус для матриц 2x2? Подсказка: матрица [[a,b],[b,c]] PSD тогда, когда a >= 0, c >= 0, ac >= b².
• Почему GPS и маршрутизация - задачи на многогранниках, а не на произвольных выпуклых множествах?

Связанные уроки

• la-12-vector-spaces