Лагранжева двойственность и теорема Слэйтера

Зачем нужна двойственность?

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

Примальная задача и лагранжиан

Рассмотрим общую задачу оптимизации:

min f(x) при условиях: gᵢ(x) ≤ 0, i = 1,...,m и hⱼ(x) = 0, j = 1,...,p

Здесь f — целевая функция, gᵢ — неравенства, hⱼ — уравнения. Оптимум p*.

Лагранжиан: «смягчаем» ограничения, перемещая их в целевую функцию со штрафами λᵢ и νⱼ:

L(x, λ, ν) = f(x) + Σᵢ λᵢ gᵢ(x) + Σⱼ νⱼ hⱼ(x)

где λᵢ ≥ 0 — «двойственные переменные» (множители Лагранжа) для неравенств, νⱼ — для уравнений (могут быть любого знака).

Физический смысл λᵢ: цена нарушения i-го ограничения. Если gᵢ(x) > 0 (нарушение), за это платим λᵢ gᵢ(x) > 0. При λᵢ = 0 — штрафа нет. При больших λᵢ — нарушение «дорогое».

Двойственная функция: g(λ, ν) = inf_{x} L(x, λ, ν) — минимум лагранжиана по x при фиксированных множителях.

Важное свойство: g — всегда вогнутая функция (как инфимум линейных функций по λ, ν).

Слабая двойственность

Теорема (слабая двойственность): для любых допустимых λ ≥ 0 и ν выполняется:

g(λ, ν) ≤ p*

Доказательство: пусть x* — оптимальное допустимое решение примальной задачи. Тогда:

g(λ, ν) = inf_x L(x, λ, ν) ≤ L(x*, λ, ν) = f(x*) + Σ λᵢ gᵢ(x*) + Σ νⱼ hⱼ(x*)

Поскольку x* допустимо: gᵢ(x*) ≤ 0 и λᵢ ≥ 0 → λᵢ gᵢ(x*) ≤ 0; hⱼ(x*) = 0. Значит правая часть ≤ f(x*) = p*.

Следствие: максимизируя g(λ, ν) по λ ≥ 0, ν, получаем наилучшую нижнюю оценку p*.

Двойственная задача и теорема Слэйтера

Двойственная задача: max_{λ ≥ 0, ν} g(λ, ν).

Оптимум двойственной задачи: d* ≤ p* (слабая двойственность). Зазор двойственности: p* − d* ≥ 0.

Теорема Слэйтера: если задача выпуклая (f, gᵢ — выпуклые, hⱼ — аффинные) и существует строго допустимая точка x̃ такая, что gᵢ(x̃) < 0 строго для всех i (и hⱼ(x̃) = 0), то:

d = p** (сильная двойственность: зазор равен нулю)

и двойственный оптимум d* достигается.

Условия ККТ (Каруша-Куна-Таккера)

При сильной двойственности x*, λ*, ν* оптимальны тогда и только тогда, когда выполняются четыре условия ККТ:

1. Примальная допустимость: gᵢ(x*) ≤ 0, hⱼ(x*) = 0 (x* — допустимо)

2. Двойственная допустимость: λᵢ* ≥ 0

3. Дополняющая нежёсткость: λᵢ* gᵢ(x*) = 0 для всех i

4. Стационарность: ∇f(x*) + Σᵢ λᵢ* ∇gᵢ(x*) + Σⱼ νⱼ* ∇hⱼ(x*) = 0

Интерпретация условия 3: либо ограничение «активно» (gᵢ(x*) = 0), либо его цена нулевая (λᵢ* = 0). Нельзя одновременно «неактивное» ограничение иметь ненулевую цену.

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

Двойственные переменные λᵢ* — это теневые цены ресурсов. Если ослабить i-е ограничение gᵢ(x) ≤ 0 на ε (сделать ≤ ε), то оптимальное значение изменится приблизительно на −λᵢ* ε. То есть λᵢ* показывает, насколько ценно «чуть больше» i-го ресурса.

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

Задача: min (x₁ − 1)² + (x₂ − 1)² при x₁ + x₂ ≤ 1, x₁ ≥ 0, x₂ ≥ 0.

Геометрически: ближайшая к точке (1, 1) точка в треугольнике {x₁ + x₂ ≤ 1, x₁ ≥ 0, x₂ ≥ 0}.

Условие Слэйтера: x̃ = (0.1, 0.1) строго допустима: 0.1 + 0.1 = 0.2 < 1, 0.1 > 0. Сильная двойственность выполнена.

ККТ: Стационарность: 2(x₁* − 1) + λ* − μ₁* = 0, 2(x₂* − 1) + λ* − μ₂* = 0, где λ* — множитель для x₁+x₂ ≤ 1, μ₁*, μ₂* — для x₁ ≥ 0, x₂ ≥ 0.

По симметрии задачи x₁* = x₂*. Проверяем: точка x* = (1/2, 1/2) на границе x₁+x₂ = 1 (ограничение активно, λ* > 0). Из стационарности: 2(1/2 − 1) + λ* = 0 → λ* = 1. Дополняющая нежёсткость: λ*(1/2 + 1/2 − 1) = 0 ✓. Ответ: x* = (1/2, 1/2), p* = 1/4 + 1/4 = 1/2.

Геометрическая интерпретация двойственности

Двойственность Лагранжа имеет глубокий геометрический смысл. Прямая задача ищет нижнюю точку выпуклого тела (надграфика функции). Двойственная задача описывает это же тело через множество всех опорных гиперплоскостей. Каждая гиперплоскость даёт нижнюю оценку для функции; супремум по всем оценкам даёт точное значение в точке оптимума (при условиях Слэйтера).

Седловые точки лагранжиана

Пара (x*, λ*) — седловая точка лагранжиана L(x, λ) = f(x) + Σλᵢgᵢ(x), если L(x*, λ) ≤ L(x*, λ*) ≤ L(x, λ*) для всех допустимых x, λ ≥ 0. При выполнении сильной двойственности седловая точка существует, и x* — оптимум прямой задачи, λ* — оптимум двойственной. Это даёт практический метод: метод Удзавы итеративно обновляет x градиентным спуском по L и λ градиентным подъёмом, сходясь к седловой точке.

Применения двойственности

Машины опорных векторов (SVM): двойственная задача имеет меньшую размерность (число опорных векторов вместо размерности признаков) и допускает ядерный трюк
Декомпозиция Бендерса в оптимизации больших систем: разделение на «лёгкую» и «трудную» части через двойственность
Distributed optimization (ADMM): двойственные переменные служат «координатором» между параллельными решателями
Анализ чувствительности: двойственная переменная λᵢ — это «теневая цена» ограничения, показывающая, насколько улучшится оптимум при ослаблении ограничения на единицу