KKT-условия

SVM использует миллионы примеров для обучения. Но решение - гиперплоскость разделения - определяется только единицами: support vectors. Почему? KKT complementary slackness: $\alpha_i(y_i(w^Tx_i+b)-1) = 0$. Либо $\alpha_i = 0$ (не support vector), либо точка лежит ровно на границе отступа. Это не случайность и не эвристика - это структура оптимальной точки, продиктованная условиями первого порядка. Каруш, Кун и Такер в 1951 году написали четыре страницы, не подозревая, что внутри каждого SVM, каждого interior point solver и каждого constrained RL-агента будет проверяться именно их система.

• **SVM и sparse solutions:** complementary slackness принуждает большинство $\alpha_i = 0$ - только support vectors влияют на классификатор
• **CVXPY / scipy.optimize:** interior point методы используют KKT как критерий остановки и для построения dual certificate
• **RLHF с ограничениями:** KKT-условия для safety constraints в PPO с KL-penalty - constrained policy optimization
• **LASSO регрессия:** L1-регуляризация эквивалентна ограничению $\|w\|_1 \leq t$; KKT даёт разреженные коэффициенты

Предварительные знания

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

Четыре условия KKT

**1951. Каруш, Кун, Такер. Четыре страницы.** Статья о необходимых условиях оптимума в задачах с ограничениями. Авторы не знали, что через 40 лет эти условия войдут в каждый алгоритм обучения SVM, в каждый constrained RL-агент, в каждый scipy.optimize solver. KKT-условия - это язык, на котором оптимальная точка общается с ограничениями.

Задача с ограничениями в стандартной форме: $$\min_{x} f(x) \quad \text{при} \quad g_i(x) \leq 0,\; i=1,\ldots,m \quad h_j(x) = 0,\; j=1,\ldots,p$$ Множители Лагранжа $\lambda_i \geq 0$ (для неравенств) и $\nu_j$ (для равенств). Лагранжиан: $\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x)$.

**KKT-условия - необходимые условия оптимальности** (при регулярности; достаточные при выпуклости): 1. **Стационарность** (Stationarity): $\nabla_x \mathcal{L} = 0$, то есть $\nabla f(x^*) + \sum_i \lambda_i^* \nabla g_i(x^*) + \sum_j \nu_j^* \nabla h_j(x^*) = 0$ 2. **Допустимость по примали** (Primal feasibility): $g_i(x^*) \leq 0$ и $h_j(x^*) = 0$ 3. **Допустимость по дуали** (Dual feasibility): $\lambda_i^* \geq 0$ 4. **Complementary slackness**: $\lambda_i^* \cdot g_i(x^*) = 0$ для всех $i$ Нарушь любое - точка не оптимальна. Выполни все (при выпуклости) - гарантированно оптимум.

**Complementary slackness** - самое содержательное из четырёх: произведение $\lambda_i \cdot g_i(x) = 0$ означает, что либо $\lambda_i = 0$ (ограничение неактивно, его можно было не добавлять), либо $g_i(x) = 0$ (ограничение активно, точка на его границе). Не могут оба быть ненулевыми.

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

Условие стационарности $\nabla f(x^*) + \sum_i \lambda_i \nabla g_i(x^*) = 0$ читается так: **градиент objective - линейная комбинация градиентов активных ограничений**. Нет свободного направления спуска: куда бы ни пошла - натыкаемся на границу. Оптимум - это ловушка из активных ограничений.

Геометрически: в точке $x^*$ градиент $\nabla f$ направлен в нормальный конус активных ограничений. Каждое ограничение "тянет" на себя с весом $\lambda_i \geq 0$. Сумма тяг уравновешивает градиент целевой функции - это и есть стационарность.

**Нормальный конус** $N_C(x^*)$ - множество направлений, допустимых только снаружи множества $C$: $N_C(x^*) = \{d \mid d^T(x - x^*) \leq 0 \; \forall x \in C\}$ **KKT стационарность** = $-\nabla f(x^*) \in N_C(x^*)$: Оптимум достигнут, когда направление наискорейшего спуска $-\nabla f$ указывает наружу из допустимого множества. **Частный случай - безграничный minimum:** нет активных ограничений, $N_C = \{0\}$, $\nabla f(x^*) = 0$. Знакомое условие первого порядка для безусловной оптимизации.

**Регулярность (constraint qualification):** KKT - необходимые условия только при некоторой регулярности допустимого множества. Наиболее проста LICQ (Linear Independence CQ): градиенты активных ограничений линейно независимы. Для выпуклых задач достаточно условия Слейтера: существует строго допустимая точка (interior point).

SVM и support vectors через KKT

SVM обучается на миллионах примеров. Но после обучения решение зависит только от нескольких - тех, что лежат ровно на границе отступа (margin). Остальные примеры можно удалить - гиперплоскость не изменится. Это не эвристика. Это прямое следствие KKT complementary slackness.

**SVM - задача оптимизации:** $$\min_{w,b} \frac{1}{2}\|w\|^2 \quad \text{при} \quad y_i(w^T x_i + b) \geq 1,\; \forall i$$ Двойственная форма (после преобразования Лагранжа): $$\max_{\alpha} \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^T x_j \quad \text{при} \quad \alpha_i \geq 0,\; \sum_i \alpha_i y_i = 0$$ **KKT complementary slackness:** $\alpha_i^* \cdot [y_i(w^T x_i + b) - 1] = 0$ Либо $\alpha_i^* = 0$ (обычный пример, не влияет на $w$), либо $y_i(w^T x_i + b) = 1$ (support vector на границе). **Вывод**: $w^* = \sum_i \alpha_i^* y_i x_i$ - только support vectors дают ненулевой $\alpha_i^*$.

**Разреженность через complementary slackness** - общий принцип: в задачах с неравенствами большинство $\alpha_i = 0$ (неактивные ограничения). Только активные ограничения дают ненулевые множители. LASSO регрессия (L1-регуляризация) - тот же механизм: KKT-условия принуждают большинство коэффициентов к нулю.

Алгоритмы: как KKT используются на практике

KKT - не только теоретический результат. Три главных класса алгоритмов выпуклой оптимизации используют KKT-условия как операциональный механизм. В scipy.optimize, CVXPY и PyTorch они работают под капотом каждый раз, когда решается задача с ограничениями.

**Три алгоритмических класса через KKT:** **1. Метод внутренней точки (Interior point / barrier method)**: Замена ограничений барьерной функцией $-\mu \sum_i \log(-g_i(x))$. Траектория оптимума при $\mu \to 0$ - "центральный путь". KKT - условия для каждой точки пути. Используется в scipy, CVXPY, SCS. **2. Active set method**: Отслеживает, какие ограничения активны. На каждой итерации решает задачу равенств (KKT без CS) на текущем активном множестве. Добавляет/удаляет ограничения при нарушениях. Эффективен для QP. **3. Projected gradient descent**: $x_{k+1} = \Pi_C(x_k - \eta \nabla f(x_k))$, где $\Pi_C$ - проекция на допустимое множество. Каждая проекция - это QP с KKT. ProxSGD, Frank-Wolfe, Mirror descent - все используют это неявно.

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

• **Четыре условия KKT:** stationarity, primal feasibility, dual feasibility ($\lambda_i \geq 0$), complementary slackness ($\lambda_i g_i = 0$)
• **Complementary slackness:** либо ограничение неактивно ($g_i < 0$, $\lambda_i = 0$), либо активно ($g_i = 0$, $\lambda_i \geq 0$) - объясняет разреженность SVM
• **При выпуклости:** KKT необходимы и достаточны для глобального оптимума - это основа CVXPY, scipy, SCS
• **Практика:** interior point (barrier method), active set, projected gradient - все алгоритмы используют KKT

Что дальше

KKT - условия оптимальности. Алгоритмы их используют для поиска оптимума:

• Методы внутренней точки — Barrier method и central path - использование KKT в interior point алгоритмах
• SVM — Support vectors как следствие KKT complementary slackness

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

• LASSO (L1-регуляризация) даёт разреженные решения. Как это связано с KKT complementary slackness для ограничения $\|w\|_1 \leq t$?
• Nash equilibrium в zero-sum играх определяется условиями, аналогичными KKT. Какое условие соответствует complementary slackness?
• scipy.optimize.minimize с методом 'SLSQP' (Sequential Quadratic Programming) использует KKT на каждой итерации. Что происходит, если начальная точка сильно нарушает primal feasibility?

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

• cvx-04 — Двойственность Лагранжа - необходимый фундамент для KKT
• cvx-06 — Методы внутренней точки используют KKT на каждой итерации
• ml-13-svm — SVM и support vectors - прямое следствие KKT complementary slackness
• ml-09-gradient-descent — Проекционный градиентный спуск - неявное решение KKT-задачи на каждом шаге
• calc-19-gradient — Условие стационарности KKT требует понимания градиента и цепного правила