Условия оптимальности Каруша-Куна-Таккера (KKT)

🎯 Зачем это нужно?

Представь, что ты тренируешь нейросеть для распознавания лиц в Instagram 📸. Модель должна быть максимально точной, НО при этом не может превышать определенный размер (ограничение памяти телефона) и время обработки (пользователи не любят ждать). Классическая задача оптимизации с ограничениями!

🚗 Tesla Autopilot: максимизировать безопасность при ограничениях на скорость реакции 💰 Портфель акций: максимизировать доходность при ограничении на максимальный риск
🤖 GPT-модели: минимизировать ошибку при ограничении на количество параметров

📚 История вопроса

В 1939 году математик Уильям Караш работал над военными задачами оптимизации. Позже, в 1951, Гарольд Кун и Альберт Таккер обобщили его результаты. Но настоящая слава пришла к KKT условиям в 1990-х с изобретением SVM (Support Vector Machines) - алгоритма, который буквально построен на этих условиях!

Интересный факт: каждый раз, когда ты используешь поиск Google или получаешь рекомендации в TikTok, где-то в глубине алгоритмов работают KKT условия 🔥

💡 Интуиция

Представь, что ты катаешься на скейтборде в скейт-парке 🛹. Хочешь добраться до самой высокой точки (максимизировать высоту), но есть препятствия - стены и границы парка (ограничения).

[МЕДИА: image_01] Описание: Скейтбордист в скейт-парке, показывающий концепцию оптимизации с ограничениями Промпт: “educational illustration of skateboarder in skate park, showing optimization with constraints concept, person trying to reach highest point while respecting park boundaries, modern clean style, suitable for technical audience”

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

1. Внутри области: действуют обычные правила (∇f = 0)
2. На границе: градиент цели должен быть “параллелен” градиенту ограничения
3. Неактивные ограничения: не влияют на решение (как далёкие стены в парке)

📐 Формальное определение

Задача условной оптимизации:

minimize f(x)
subject to: gᵢ(x) ≤ 0, i = 1,...,m    (неравенства)
           hⱼ(x) = 0, j = 1,...,p    (равенства)

KKT условия для точки x:*

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

2. Допустимость: gᵢ(x*) ≤ 0, hⱼ(x*) = 0

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

4. Двойственная допустимость: λᵢ ≥ 0 для всех i

где λᵢ, μⱼ - множители Лагранжа.

🔍 Примеры с разбором

Пример 1: Простая задача SVM

Найдём оптимальную разделяющую гиперплоскость для двух классов точек:

minimize ½||w||²
subject to: yᵢ(w·xᵢ + b) ≥ 1, i = 1,...,n

[МЕДИА: image_02] Описание: Визуализация SVM с опорными векторами и разделяющей гиперплоскостью Промпт: “SVM visualization showing support vectors, separating hyperplane, margin boundaries, two classes of data points in different colors, mathematical elegance, technical illustration style”

Шаг 1: Переписываем в стандартном виде

minimize ½||w||²  
subject to: 1 - yᵢ(w·xᵢ + b) ≤ 0

Шаг 2: Составляем лагранжиан

L(w,b,λ) = ½||w||² + Σᵢ λᵢ[1 - yᵢ(w·xᵢ + b)]

Шаг 3: KKT условия

• ∇w L = w - Σᵢ λᵢyᵢxᵢ = 0 ⟹ w = Σᵢ λᵢyᵢxᵢ
• ∂L/∂b = -Σᵢ λᵢyᵢ = 0 ⟹ Σᵢ λᵢyᵢ = 0
• λᵢ[1 - yᵢ(w·xᵢ + b)] = 0 (дополняющая нежёсткость)
• λᵢ ≥ 0

Главный инсайт: λᵢ > 0 только для опорных векторов! Остальные точки не влияют на решение.

Пример 2: Портфельная оптимизация

Максимизируем доходность при ограничении на риск:

maximize μᵀx - γ·xᵀΣx    (доходность - штраф за риск)
subject to: Σᵢ xᵢ = 1    (всё в портфеле)
           xᵢ ≥ 0         (нельзя короткие позиции)

🎮 Практика

Базовый уровень 🟢

Задание 1: Найди минимум f(x,y) = x² + y² при ограничении x + y = 1

Задание 2: Для задачи minimize x² subject to x ≥ 2, проверь KKT условия в точке x = 2

Задание 3: Объясни, почему в SVM λᵢ = 0 для точек, далёких от разделяющей гиперплоскости

Продвинутый уровень 🟡

Задание 4: Реши задачу: minimize x₁² + x₂² subject to x₁ + x₂ ≥ 1, x₁,x₂ ≥ 0

Задание 5: Докажи, что для выпуклой задачи KKT условия являются достаточными для оптимальности

Задание 6: В нейросети с L2-регуляризацией выведи KKT условия для весов

Челлендж 🔴

Задание 7: Покажи связь между KKT условиями и двойственной задачей в SVM

Задание 8: Для задачи квадратичного программирования с ограничениями-неравенствами выведи алгоритм активного множества

⚠️ Частые ошибки

❌ Ошибка: “KKT условия всегда дают глобальный минимум” ✅ Правильно: Только для выпуклых задач! Для невыпуклых - лишь локальный 💡 Почему: В невыпуклых задачах может быть много локальных минимумов

❌ Ошибка: Забыть проверить дополняющую нежёсткость λᵢ·gᵢ(x) = 0 ✅ Правильно: Это ключевое условие! Оно определяет активные ограничения 💡 Почему: Если ограничение неактивно (gᵢ < 0), то λᵢ = 0

❌ Ошибка: Неправильный знак в условии стационарности ✅ Правильно: ∇f + Σλᵢ∇gᵢ = 0 (плюс для gᵢ ≤ 0) 💡 Почему: Знак зависит от того, как записано ограничение

❌ Ошибка: “Если KKT условия выполнены, точка обязательно оптимальна” ✅ Правильно: Нужна ещё регулярность ограничений (LICQ, MFCQ и др.) 💡 Почему: В некоторых “плохих” точках KKT условия могут быть некорректными

🎓 Главное запомнить

✅ Суть: KKT условия - необходимые условия оптимальности для задач с ограничениями ✅ Формула: ∇f + Σλᵢ∇gᵢ = 0, λᵢ·gᵢ = 0, λᵢ ≥ 0 ✅ Применение: SVM, портфельная оптимизация, обучение нейросетей с ограничениями

🔗 Связь с другими темами

Назад: Множители Лагранжа (урок 278) - частный случай KKT для ограничений-равенств Вперёд: Двойственность в оптимизации, алгоритмы внутренних точек, Sequential Quadratic Programming (SQP)