# Стивен Бойд: «Почему двойственность — это основа оптимизации»

Источник: https://www.youtube.com/watch?v=wsRznzNgTS0
Канал: Stanford Online
Опубликовано: 18.03.2024

---

## Двойственность в оптимизации: основы и практическое применение
[[JUMP:0:04]]

Двойственность — фундаментальная концепция в теории оптимизации, позволяющая находить нижние границы для целевой функции даже в сложных, невыпуклых задачах. Профессор Стивен Бойд (Stephen Boyd) из Stanford University в восьмой лекции курса EE364A объясняет, как построение Лагранжиана и двойственной функции помогает анализировать задачи, которые невозможно решить напрямую.

### ⚖️ Концепция двойственности и Лагранжиан
[[JUMP:0:04]]

В основе метода лежит идея включения ограничений задачи непосредственно в целевую функцию с использованием весовых коэффициентов — множителей Лагранжа.

*   **Лагранжиан:** Функция, которая объединяет целевую функцию и ограничения.
*   **Двойственная функция:** Минимум Лагранжиана по переменной $x$. Она всегда дает нижнюю границу ($d^*$) для оптимального значения исходной задачи ($p^*$).
*   **Слабая двойственность:** Утверждение, что двойственная задача всегда дает нижнюю границу оптимального значения, справедливо даже для невыпуклых задач.
*   **Сильная двойственность:** Случай, когда нижняя граница в точности равна оптимальному значению ($p^* = d^*$). По словам Стивена Бойда, это почти всегда верно для выпуклых задач, если выполняются условия регулярности (квалификации ограничений).

### 🛠️ Практические примеры и эвристики
[[JUMP:1:42]]

Методы двойственности позволяют оценивать качество приближенных решений в сложных задачах, таких как задача разбиения (partitioning problem).

*   **Heuristics vs. Bounds:** Даже если вы используете простые алгоритмы (например, «жадные» методы или 1-opt / 2-opt), вы можете найти нижнюю границу с помощью двойственной задачи и понять, насколько вы близки к глобальному оптимуму.
*   **Сертификат оптимальности:** При решении линейных программ (LP) большинство алгоритмов возвращают как прямое (primal), так и двойственное (dual) решение. Двойственное решение служит своего рода «сертификатом», доказывающим, что лучшего значения достичь невозможно.

### 📐 Геометрическая интерпретация
[[JUMP:29:40]]

Визуализация задачи на плоскости, где одна ось — это значение функции ограничения, а вторая — значение целевой функции, позволяет понять природу «зазора» (duality gap).

*   **Невыпуклость:** Зазор возникает, когда множество допустимых пар $(f_1(x), f_0(x))$ имеет «впадину» (невыпуклость).
*   **Выпуклость:** В выпуклых задачах это множество выпукло, и мы всегда можем провести опорную гиперплоскость, что гарантирует отсутствие зазора.

### 💡 Условия Каруша-Куна-Таккера (KKT)
[[JUMP:45:19]]

Условия KKT — это набор условий оптимальности, которые обобщают классические множители Лагранжа из математического анализа для случая с ограничениями-неравенствами.

1.  **Допустимость:** Точка $x$ должна удовлетворять ограничениям.
2.  **Неотрицательность множителей:** $\lambda_i \ge 0$.
3.  **Дополнительная нежесткость (Complementary slackness):** Произведение $\lambda_i f_i(x)$ должно быть равно нулю. Если множитель положителен, ограничение должно быть «жестким» (tight).
4.  **Стационарность:** Градиент Лагранжиана по $x$ равен нулю.

### 📈 Локальная чувствительность и «теневые цены»
[[JUMP:1:00:33]]

Двойственные переменные несут в себе критически важную информацию о том, как изменение ограничений (например, бюджета мощности в системе) повлияет на оптимальную стоимость.

*   **Теневая цена (Shadow price):** Лагранжев множитель показывает чувствительность оптимальной стоимости к возмущению ограничения.
*   **Применение:** В энергетических сетях эти значения известны как «локальные маржинальные цены» (locational marginal prices), а в управлении ресурсами дата-центров помогают оценить стоимость выделения дополнительных ядер или полосы пропускания.