Оптимизация
Ограниченная оптимизация
Как обучить автопилот Tesla не нарушать правила дорожного движения? Или оптимизировать торговый портфель с ограничением по риску? Это ограниченная оптимизация. KKT условия - язык, на котором описываются все ограниченные задачи: от SVM до policy gradient в RL.
- **SVM:** обучение SVM - это KKT задача; support vectors - точки с lambda_i > 0 (активные ограничения); dual formulation позволяет kernel trick
- **Safe RL:** ограниченный policy gradient (CPO, TRPO, PPO) использует KKT для ограничений на нарушение - основа безопасных автономных систем
- **Federated Learning:** ADMM разбивает задачу обучения на клиентские подзадачи; применяется в FL с privacy constraints (Apple, Google)
Предварительные знания
Лагранжиан и множители
Ограниченная задача: min f(x) s.t. hᵢ(x) = 0, gⱼ(x) ≤ 0. Метод **лагранжевых множителей** объединяет цель и ограничения в одну функцию - Лагранжиан: L(x, λ, μ) = f(x) + Σλᵢhᵢ(x) + Σμⱼgⱼ(x). Множители λᵢ (для равенств) и μⱼ ≥ 0 (для неравенств) - «цены» нарушения ограничений.
**Экономический смысл:** λᵢ - «теневая цена» ограничения hᵢ = 0. Если немного ослабить ограничение (hᵢ ≤ ε), оптимум изменится на ≈ λᵢ · ε. Это то же самое, что dual variables в LP - чувствительность оптимума к изменению ограничений.
В задаче min f(x) s.t. g(x)=0 множитель Лагранжа λ = 5. Что произойдёт с оптимумом, если ослабить ограничение до g(x) ≤ 0.1?
KKT условия
**KKT условия** (Karush-Kuhn-Tucker, 1951) - необходимые условия оптимальности для ограниченной задачи. Для выпуклых задач они также достаточны. Любой оптимум x* должен удовлетворять четырём группам условий.
| KKT условие | Математика | Смысл |
|---|---|---|
| Стационарность | nabla_x L(x*,lambda*,mu*) = 0 | Оптимум по x при фиксированных множителях |
| Прим. допустимость | g_i(x*) <= 0, h_j(x*) = 0 | Решение удовлетворяет ограничениям |
| Двойств. допустимость | lambda_i >= 0 | Для неравенств множители неотрицательны |
| Дополн. нежёсткость | lambda_i * g_i(x*) = 0 | Активны только 'tight' ограничения |
**Дополняющая нежёсткость** - самое интуитивное KKT условие: либо ограничение активно (gᵢ=0), либо его цена нулевая (λᵢ=0). Нельзя одновременно иметь и активное ограничение, и нулевую цену (кроме вырожденных случаев). Это объясняет, почему в SVM только support vectors имеют ненулевые αᵢ.
В оптимуме задачи min f(x) s.t. g(x) ≤ 0 имеем g(x*) = -3 (ограничение неактивно). Что можно сказать о λ*?
Penalty и Augmented Lagrangian
Что если хочется решить ограниченную задачу методами для безограниченных? **Penalty method** добавляет квадратичный штраф: min f(x) + (ρ/2)||h(x)||² → при ρ→∞ решение приближается к ограниченному оптимуму. Проблема: плохая обусловленность при больших ρ. **Augmented Lagrangian** комбинирует Лагранжиан и penalty: Lₐ = f + λᵀh + (ρ/2)||h||² - конечный ρ достаточен.
**Augmented Lagrangian vs простой penalty:** простой penalty нужен ρ→∞ для точного удовлетворения ограничений (плохая обусловленность). Augmented Lagrangian обновляет λ и конечный ρ дает точное решение. Это метод multipliers Хестенеса-Пауэлла (1969) - основа ADMM.
Почему Augmented Lagrangian лучше простого penalty method для точного удовлетворения ограничений?
ADMM: распределённая оптимизация
**ADMM** (Alternating Direction Method of Multipliers) - расширение Augmented Lagrangian для задач типа min f(x) + g(z) s.t. Ax + Bz = c. Разбивает задачу на два подпространства, решая их поочерёдно: x-update и z-update. Идеально для распределённого ML.
**Safe RL через ограниченную оптимизацию:** задачу обучения с ограничениями (max reward s.t. E[нарушения] ≤ δ) решают через CPO (Constrained Policy Optimization) или ADMM. KKT дают условия оптимальности для policy gradient с constraint.
KKT условия - только для теоретического анализа, на практике не применяются
KKT условия лежат в основе всех промышленных ограниченных солверов: interior point методы решают возмущённые KKT системы, SVM строится через dual KKT, ADMM обновляет dual variables (λ) согласно KKT.
Primal-dual IPM на каждой итерации решает систему: nabla_x L = 0, h(x)=0, g(x)<=0, lambda>=0, lambda*g=0 с барьерным смягчением. Это и есть KKT система. SVM через dual: условие KKT w=sum(alpha_i*yi*xi) прямо используется для предсказания. KKT - не только теория, это алгоритмическая основа современной оптимизации.
Почему ADMM популярен для распределённых ML задач?
Ключевые идеи
- **Лагранжиан** L(x,λ,μ) объединяет цель и ограничения; множители - теневые цены ограничений
- **KKT:** стационарность + прямая допустимость + двойственная допустимость + дополняющая нежёсткость - необходимые условия оптимума (достаточные для выпуклых задач)
- **Augmented Lagrangian** решает ограниченные задачи методами без ограничений; обновление λ даёт точное выполнение ограничений при конечном ρ
- **ADMM** разбивает составные задачи на подзадачи; стандарт для распределённого ML и federated learning
Связанные темы
KKT и Лагранжиан - язык всей ограниченной оптимизации:
- Выпуклая оптимизация — Для выпуклых задач KKT необходимы и достаточны; strong duality гарантирует прим-дуал gap = 0
- Метод внутренней точки — Primal-dual IPM решает возмущённые KKT условия; барьер смягчает дополняющую нежёсткость
- Байесовская оптимизация — BO с ограничениями использует Augmented Lagrangian для ограниченного HPO
Вопросы для размышления
- Дополняющая нежёсткость говорит, что либо ограничение активно, либо его цена нулевая. Почему нельзя иметь обе ситуации одновременно? Как это связано с SVM support vectors?
- Gradient descent не умеет обрабатывать ограничения явно. Почему Augmented Lagrangian преобразует ограниченную задачу в серию безограниченных и как это помогает?
- Как ADMM применяется в federated learning? Что является x-update, z-update и dual update в этом контексте?