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

Почему выпуклость важна?

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

Определение выпуклого множества

Множество C ⊆ ℝⁿ называется выпуклым, если для любых двух точек x, y ∈ C и любого числа θ ∈ [0,1] выполняется:

θx + (1−θ)y ∈ C

Что это означает словами? Возьмите любые две точки множества. Соедините их отрезком. Если весь этот отрезок целиком лежит внутри множества — оно выпуклое. Параметр θ «пробегает» от 0 до 1, описывая все точки между x и y: при θ=1 получаем x, при θ=0 — y, при θ=0.5 — середину отрезка.

Геометрический тест: нарисуйте фигуру. Если можно найти две точки внутри неё, соединённые отрезком, частично выходящим за границу — фигура невыпуклая. Буква «C» — невыпуклая. Круг, квадрат, треугольник — выпуклые.

Классические примеры выпуклых множеств

Гиперплоскость: {x ∈ ℝⁿ : aᵀx = b}, где a ≠ 0 — фиксированный вектор, b — число. Это n-1-мерная «плоскость» в пространстве. Пример в ℝ²: прямая 2x₁ + 3x₂ = 6. Любые две точки на прямой соединены отрезком, лежащим на прямой — выпуклость очевидна.

Полупространство: {x : aᵀx ≤ b} — одна «сторона» от гиперплоскости. В ℝ² это полуплоскость по одну сторону прямой.

Шар: {x : ‖x − xc‖ ≤ r} — все точки на расстоянии не более r от центра xc. Выпуклость: если две точки лежат в шаре (расстояние до xc ≤ r), то любая точка между ними тоже в шаре — это следует из неравенства треугольника.

Эллипсоид: {x : (x−xc)ᵀP⁻¹(x−xc) ≤ 1}, где P — положительно определённая матрица. Это «вытянутый шар» по разным осям. Активно используется в теории управления для описания допустимых областей состояний.

Конус второго порядка (SOCP): {(x, t) : ‖x‖ ≤ t, t ≥ 0} — «мороженое» в пространстве. Поверхность конуса — это точки с ‖x‖ = t, внутренность — с ‖x‖ < t.

Множество положительно полуопределённых матриц: Sⁿ₊ = {X ∈ ℝⁿˣⁿ : X = Xᵀ, uᵀXu ≥ 0 для всех u}. Это выпуклый конус в пространстве симметричных матриц.

Операции, сохраняющие выпуклость

Одно из ключевых свойств: многие операции над выпуклыми множествами порождают новые выпуклые множества. Это позволяет строить сложные выпуклые структуры из простых кирпичиков.

Пересечение: если C₁ и C₂ выпуклые, то C₁ ∩ C₂ — тоже выпуклое. Доказательство: если x, y ∈ C₁ ∩ C₂, то x, y ∈ C₁ → отрезок xy ⊆ C₁, и x, y ∈ C₂ → отрезок xy ⊆ C₂, значит отрезок xy ⊆ C₁ ∩ C₂. Следствие: многогранник (политоп) — пересечение конечного числа полупространств — выпуклый.

Образ при линейном преобразовании: f(C) = {Ax + b : x ∈ C} — выпуклое, если C выпуклое. Аффинные преобразования «сохраняют» выпуклость.

Прообраз: если f: ℝⁿ → ℝᵐ аффинная (f(x) = Ax+b) и D — выпуклое, то f⁻¹(D) = {x : f(x) ∈ D} — выпуклое.

Сумма Минковского: C₁ + C₂ = {x + y : x ∈ C₁, y ∈ C₂} — выпуклая, если C₁, C₂ выпуклые.

Теорема разделяющей гиперплоскости

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

Теорема: если C₁ и C₂ — непустые выпуклые множества с пустым пересечением (C₁ ∩ C₂ = ∅), то существует вектор a ≠ 0 и число b такие, что:

aᵀx ≤ b для всех x ∈ C₁
aᵀx ≥ b для всех x ∈ C₂

Смысл: гиперплоскость {x : aᵀx = b} «разделяет» два множества. Это геометрически очевидно в ℝ²: два непересекающихся выпуклых множества на плоскости всегда можно разделить прямой.

Опорная гиперплоскость: в граничной точке x₀ выпуклого C существует вектор g ≠ 0 такой, что gᵀ(x − x₀) ≤ 0 для всех x ∈ C. Это «касательная» гиперплоскость к C в точке x₀, лежащая «снаружи».

Проекция на выпуклое множество

Для замкнутого выпуклого множества C ортогональная проекция точки x определяется как:

P_C(x) = argmin_{y ∈ C} ‖y − x‖²

Существование и единственность: такая точка всегда существует и единственна. Единственность — следствие строгой выпуклости функции ‖y − x‖².

Характеризация: y* = P_C(x) тогда и только тогда, когда (x − y*)ᵀ(z − y*) ≤ 0 для всех z ∈ C. Это означает, что вектор (x − y*) образует тупой угол со всеми направлениями внутри C из точки y*.

Практическое значение: проекционный градиентный спуск — важнейший алгоритм оптимизации с ограничениями. На каждом шаге делаем шаг градиента, затем «проецируем» обратно на допустимое множество C.

Полный разбор примера

Задача: найти ближайшую к точке x = (3, 4) точку в квадрате C = {y ∈ ℝ² : 0 ≤ y₁ ≤ 1, 0 ≤ y₂ ≤ 1}.

Решение: Проекция на квадрат — это покоординатная отсечка: P_C(x) = (min(max(x₁, 0), 1), min(max(x₂, 0), 1)).

Для x = (3, 4): y₁* = min(max(3, 0), 1) = 1, y₂* = min(max(4, 0), 1) = 1. Ответ: P_C(3, 4) = (1, 1) — угловая точка квадрата.

Проверка условия: вектор x − y* = (2, 3). Для любого z ∈ C: (x − y*)ᵀ(z − y*) = 2(z₁ − 1) + 3(z₂ − 1). Поскольку z₁ ≤ 1 и z₂ ≤ 1, оба слагаемых ≤ 0. Условие выполнено.

Реальные приложения

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