Двойственность Лагранжа

За kernel SVM, ADMM в распределённом обучении, constrained generation в LLM - везде двойственность Лагранжа. Primal задача: минимизировать функцию при ограничениях. Dual задача: максимизировать нижние оценки. При сильной двойственности - это одна и та же задача, смотренная с двух сторон. SVM без dual form не мог бы использовать kernel trick - а значит, работал бы только в линейном пространстве.

• **SVM и kernel trick:** dual form SVM заменяет $x_i^\top x_j$ на $K(x_i, x_j)$ - алгоритм мгновенно работает в бесконечномерных пространствах (RBF kernel = бесконечномерный полином)
• **ADMM для federated learning:** Alternating Direction Method of Multipliers делит глобальную задачу на локальные через dual decomposition; агенты обмениваются только dual variables, а не данными
• **Constrained generation в LLM:** длина ответа, safety constraints реализуются через Lagrangian relaxation - нарушение ограничения штрафуется и постепенно исчезает из оптимального решения
• **Boyd & Vandenberghe:** их учебник 'Convex Optimization' используется в Stanford CS229, CMU 10-725 и каждом серьёзном ML-курсе. Глава о двойственности - обязательное чтение
• **Interior Point Methods:** solvers (CPLEX, Gurobi, MOSEK) проверяют сходимость через duality gap - когда $p^* - d^* < \varepsilon$, оптимум найден. Это сертифицируемая гарантия качества

Функция Лагранжа

SVM мог бы работать в исходном пространстве признаков. Но dual form позволяет заменить $x^\top y$ на $K(x,y)$ - и вдруг SVM работает в бесконечномерном пространстве. Двойственность - это не математический трюк. Это смена угла зрения на задачу оптимизации, которая открывает методы, невозможные в исходной формулировке.

Идея Лагранжа (1788): вместо того чтобы выполнять ограничения жёстко, можно их "оштрафовать" - добавить в целевую функцию с множителями. Если задача нарушает ограничение $g_i(x) \leq 0$, штраф $\lambda_i g_i(x)$ растёт. Оптимальное решение либо не нарушает ограничение, либо принимает штраф всерьёз.

**Задача оптимизации (primal):** $\min_x f_0(x)$ $\text{s.t.} \; f_i(x) \leq 0, \; i = 1, \ldots, m$ $\quad\quad h_j(x) = 0, \; j = 1, \ldots, p$ **Функция Лагранжа:** $L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x)$ где $\lambda_i \geq 0$ - двойственные переменные (множители Лагранжа) для неравенств, $\nu_j \in \mathbb{R}$ - для равенств. $L$ - взвешенная сумма: целевой функции и нарушений ограничений.

Двойственная функция и нижние оценки

Двойственная функция - это минимум Лагранжа по прямым переменным $x$ при фиксированных $\lambda, \nu$. Ключевое свойство: для любых допустимых $\lambda \geq 0, \nu$ двойственная функция даёт нижнюю границу для оптимума primal задачи. Это верно всегда, даже без выпуклости.

**Двойственная функция:** $g(\lambda, \nu) = \inf_x L(x, \lambda, \nu) = \inf_x \left[ f_0(x) + \sum_i \lambda_i f_i(x) + \sum_j \nu_j h_j(x) \right]$ **Нижняя оценка:** для любых $\lambda \geq 0$ и любых $\nu$: $g(\lambda, \nu) \leq p^*$ где $p^* = \min\{f_0(x) \mid f_i(x) \leq 0, h_j(x) = 0\}$ - оптимум primal. **Двойственная задача:** $\max_{\lambda \geq 0, \nu} g(\lambda, \nu) = d^*$ $g$ всегда вогнута по $\lambda, \nu$ (как инфимум линейных функций), поэтому двойственная задача всегда выпуклая.

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

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

1951. Гарольд Кун и Альберт Такер вывели условия первого порядка для задачи с ограничениями. KKT-условия войдут в каждый учебник оптимизации на следующие 70 лет - и в каждый solver от scipy до CPLEX. Сейчас мы строим к ним мост.

**Слабая двойственность** (всегда верна): $d^* \leq p^*$ Двойственный оптимум не превышает primal оптимум. Разность $p^* - d^*$ называется duality gap. **Сильная двойственность** ($d^* = p^*$, duality gap = 0): Выполняется при **условии Слейтера:** существует строго допустимая точка (interior point), то есть $\exists \tilde{x}$ такая что $f_i(\tilde{x}) < 0$ для всех $i$. **Следствие:** для выпуклых задач со Slater's condition сильная двойственность выполняется автоматически. Dual задача имеет тот же оптимум, что и primal.

Duality gap = 0 - это сертификат качества решения. В распределённом обучении (ADMM для federated learning) агенты оптимизируют локальные двойственные задачи и обмениваются dual variables. Сходимость к нулевому duality gap гарантирует, что глобальный оптимум достигнут - без обмена сырыми данными.

KKT-условия и SVM dual

KKT-условия - необходимые и достаточные условия оптимальности для выпуклых задач с Slater's condition. Четыре условия, каждое со своим смыслом. И их прямое следствие - dual form SVM, которая позволяет kernel trick.

**KKT-условия** (необходимые при Slater, необходимые и достаточные при выпуклости): 1. **Stationarity:** $\nabla_x L(x^*, \lambda^*, \nu^*) = 0$ (градиент Лагранжа по $x$ равен нулю) 2. **Primal feasibility:** $f_i(x^*) \leq 0$, $h_j(x^*) = 0$ (исходные ограничения выполнены) 3. **Dual feasibility:** $\lambda_i^* \geq 0$ (множители неравенств неотрицательны) 4. **Complementary slackness:** $\lambda_i^* f_i(x^*) = 0$ (либо ограничение активно $f_i = 0$, либо $\lambda_i = 0$) Complementary slackness - ключевое: «неактивные» ограничения не влияют на оптимум ($\lambda_i = 0$ для всех $f_i(x^*) < 0$).

SVM dual - классический пример. Primal SVM: минимизировать $\frac{1}{2}\|w\|^2$ при ограничениях $y_i(w^\top x_i + b) \geq 1$. После подстановки KKT-условий и минимизации по $w, b$ получаем dual: $\max_{\alpha} \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^\top x_j$ $\text{s.t.} \; \alpha_i \geq 0, \; \sum_i \alpha_i y_i = 0$ В dual появляются только скалярные произведения $x_i^\top x_j$. Замените их на $K(x_i, x_j) = \phi(x_i)^\top \phi(x_j)$ - и SVM работает в любом (бесконечномерном) пространстве признаков без явного вычисления $\phi(x)$.

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

• **Лагранжиан** $L(x,\lambda,\nu)$ = целевая функция + взвешенные ограничения; $\lambda \geq 0$ для неравенств
• **Dual function** $g(\lambda,\nu) = \inf_x L$ - всегда вогнута, всегда нижняя оценка для $p^*$
• **Слабая двойственность:** $d^* \leq p^*$ - всегда верна без доп. условий
• **Сильная двойственность:** $d^* = p^*$ - при выпуклой primal и Slater's condition (строго допустимая точка)
• **KKT:** stationarity + primal/dual feasibility + complementary slackness - необходимые и достаточные условия при выпуклости
• **SVM dual:** kernel trick возможен именно потому, что dual зависит от $x_i$ только через скалярные произведения

Что дальше

Двойственность - теория. KKT - инструмент. Методы - практика:

• KKT-условия — Полная система оптимальности: четыре условия, решающие задачу с ограничениями
• Методы внутренней точки — Interior point solvers используют duality gap как критерий остановки

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

• SVM в primal пространстве минимизирует $\|w\|^2$. В dual - максимизирует нижние оценки через $\alpha_i$. Почему это одна и та же задача - и как связаны $w^*$ и $\alpha^*$?
• Duality gap = 0 гарантирует, что найденное решение глобально оптимально. Как это используется в federated learning для проверки сходимости без доступа к централизованным данным?
• Если задача невыпуклая, dual задача всё равно выпуклая. Почему? И чем тогда полезна dual для невыпуклых задач?

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

• cvx-03 — Выпуклые функции и условия оптимальности
• cvx-05 — KKT-условия - следствие двойственности
• opt-02 — Общая оптимизация vs выпуклая - разные гарантии
• ml-09-gradient-descent — SVM dual обучается градиентным спуском по dual
• fa-01 — Гильбертовы пространства - фундамент kernel trick
• la-25-quadratic-forms