Двойственность в оптимизации: когда задача смотрит в зеркало

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

Представь, что ты тренируешь нейросеть для распознавания котиков 🐱. Одну и ту же задачу можно решать двумя способами:

• Прямой: “Найти наилучшие веса w, минимизирующие ошибку”
• Двойственный: “Найти наихудшие примеры, максимизирующие сложность для модели”

И вот магия - эти задачи математически эквивалентны! 🪄

💼 В индустрии это везде:

• SVM использует двойственность для ядерных методов
• GAN’ы - это игра между генератором и дискриминатором (min-max)
• Reinforcement Learning: оптимальная политика ↔ оптимальная оценочная функция

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

В 1947 году математик Джон фон Нейман доказал теорему о минимаксе для игр. Он показал, что в каждой игре существует равновесие - точка, где стратегии игроков взаимно оптимальны.

Позже выяснилось: любая задача оптимизации - это игра! 🎮

• Один игрок минимизирует функцию потерь
• Другой максимизирует ограничения

💡 Интуиция

Представь, что ты владелец завода по производству смартфонов и планшетов 📱

Прямая задача (как менеджер): “При моих ресурсах (время, материалы, рабочие) - сколько максимум прибыли я могу получить?”

Двойственная задача (как аудитор):
“Если я оценю каждый ресурс по справедливой цене - какую минимальную стоимость всех ресурсов я получу?”

И тут происходит чудо: максимальная прибыль = минимальной стоимости ресурсов!

[МЕДИА: image_01] Описание: Схема показывающая прямую и двойственную задачи как зеркальное отражение Промпт: “mathematical illustration showing primal and dual optimization problems as mirror reflections, factory production setup, smartphones and tablets, resources and constraints, clean modern style, blue and orange colors”

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

Прямая задача линейного программирования:

max c^T x
subject to: Ax ≤ b
           x ≥ 0

Двойственная задача:

min b^T y  
subject to: A^T y ≥ c
           y ≥ 0

Теорема сильной двойственности: Если обе задачи имеют оптимальные решения, то:

max(прямая) = min(двойственная)

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

Для общей задачи:

min f(x)
subject to: g_i(x) ≤ 0
           h_j(x) = 0

Лагранжиан: L(x,λ,μ) = f(x) + Σλᵢgᵢ(x) + Σμⱼhⱼ(x)

Двойственная функция: g(λ,μ) = min_x L(x,λ,μ)

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

Пример 1: Завод смартфонов

Прямая задача: Завод производит смартфоны (прибыль 300₽) и планшеты (прибыль 500₽).

• Время сборки: 2ч на смартфон, 3ч на планшет (≤ 120ч)
• Материалы: 1кг на смартфон, 2кг на планшет (≤ 80кг)

max 300x₁ + 500x₂
s.t. 2x₁ + 3x₂ ≤ 120  (время)
     1x₁ + 2x₂ ≤ 80   (материалы)
     x₁, x₂ ≥ 0

Двойственная задача: Аудитор оценивает ресурсы: y₁ ₽/час, y₂ ₽/кг

min 120y₁ + 80y₂
s.t. 2y₁ + 1y₂ ≥ 300  (смартфон должен окупаться)
     3y₁ + 2y₂ ≥ 500  (планшет должен окупаться)  
     y₁, y₂ ≥ 0

[МЕДИА: image_02] Описание: График показывающий область допустимых решений для прямой и двойственной задач Промпт: “optimization graph showing feasible regions for primal and dual linear programming problems, constraint lines, optimal points marked, coordinate system, mathematical visualization, educational style”

Решение: Оптимум прямой: (x₁*, x₂*) = (20, 30) → прибыль = 21000₽ Оптимум двойственной: (y₁*, y₂*) = (100, 100) → стоимость = 21000₽

Пример 2: SVM через двойственность

Прямая задача SVM:

min ½||w||² + C Σξᵢ
s.t. yᵢ(w^T xᵢ + b) ≥ 1 - ξᵢ
     ξᵢ ≥ 0

Двойственная задача:

max Σαᵢ - ½ΣΣαᵢαⱼyᵢyⱼ⟨xᵢ,xⱼ⟩
s.t. 0 ≤ αᵢ ≤ C
     Σαᵢyᵢ = 0

Магия: в двойственной задаче данные входят только через скалярные произведения ⟨xᵢ,xⱼ⟩ - это позволяет использовать ядерные методы! 🎯

🎮 Практика

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

Задание 1: Напиши двойственную задачу для:

max 4x₁ + 6x₂
s.t. x₁ + 2x₂ ≤ 8
     3x₁ + x₂ ≤ 12
     x₁, x₂ ≥ 0

Задание 2: Если оптимум прямой задачи равен 24, чему равен оптимум двойственной?

Задание 3: В задаче SVM что означает αᵢ = C для некоторого объекта?

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

Задание 4: Покажи, что если прямая задача неограничена сверху, то двойственная несовместна.

Задание 5: Выведи двойственную задачу для:

min x₁² + x₂²
s.t. x₁ + x₂ = 1

Задание 6: Объясни, почему в GAN’ах генератор решает минимизацию, а дискриминатор - максимизацию.

Челлендж 🔴

Задание 7: Докажи слабую двойственность: max(прямая) ≤ min(двойственная).

Задание 8: Реализуй алгоритм, который для заданной прямой задачи ЛП строит двойственную автоматически.

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

❌ Ошибка: “Двойственная задача - это просто другая запись той же задачи” ✅ Правильно: Двойственная задача имеет другой смысл и другие переменные 💡 Почему: Прямые переменные - решение, двойственные - цены ресурсов

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

❌ Ошибка: “Если прямая имеет максимум, то двойственная имеет минимум” ✅ Правильно: Обе задачи могут не иметь решений или быть неограниченными
💡 Почему: Теорема сильной двойственности требует дополнительных условий

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

✅ Суть: Каждая задача оптимизации имеет “зеркального двойника” ✅ Теорема: При выполнении условий max(прямая) = min(двойственная)
✅ Применение: SVM, нейросети, экономика, теория игр

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

Откуда пришли: Условия оптимальности (урок 281) → множители Лагранжа Куда идем: Седловые точки → теория игр → GAN’ы и adversarial training Связано с: Выпуклая оптимизация, KKT-условия, квадратичное программирование