Множители Лагранжа

Множители Лагранжа находят минимум на ограничении, требуя, чтобы градиенты цели и ограничения были параллельны.

Метод множителей Лагранжа: в условном минимуме при ограничении $g(x)=0$ выполняется $\nabla f(x^*)=\lambda\,\nabla g(x^*)$ для некоторого числа $\lambda$.

Зачем

До сих пор мы искали минимум, требуя $\nabla f=0$. Но если есть ограничение-равенство (например, «потратить ровно весь бюджет» $g(x)=0$), минимум обычно лежит не там, где $\nabla f=0$, а на самой кривой ограничения. Лагранж даёт условие оптимальности для такого случая.

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

Представьте линии уровня цели $f$ и кривую ограничения $g(x)=0$. Двигаясь вдоль кривой, мы пересекаем линии уровня, меняя $f$. Минимум на кривой достигается там, где кривая ограничения касается линии уровня цели (дальше двигаться — значит снова повышать $f$). А в точке касания градиенты перпендикулярны общей касательной, то есть параллельны друг другу:

$$\nabla f(x^*)=\lambda\,\nabla g(x^*).$$

Коэффициент пропорциональности $\lambda$ и называется множителем Лагранжа.

Функция Лагранжа

Удобно ввести $\mathcal{L}(x,\lambda)=f(x)-\lambda\,g(x)$. Тогда условия оптимальности — это просто $\nabla_x\mathcal{L}=0$ и $\nabla_\lambda\mathcal{L}=0$ (последнее воспроизводит ограничение $g=0$). Условная задача с ограничением превратилась в безусловный поиск стационарной точки функции $\mathcal{L}$ по расширенному набору переменных $(x,\lambda)$.

Пример: коробка максимального объёма

Классика: найти прямоугольник максимальной площади с периметром $20$. Переменные — стороны $x,y$; цель $f=xy\to\max$; ограничение $g=2x+2y-20=0$. Лагранж: $\nabla f=(y,x)$, $\nabla g=(2,2)$, условие $y=2\lambda,\ x=2\lambda\Rightarrow x=y$. С ограничением $x=y=5$. Проверим перебором по кривой ограничения.

# ограничение: 2x + 2y = 20  ->  y = 10 - x
best = None
for x10 in range(1, 100):           # x от 0.1 до 9.9
    x = x10 / 10
    y = 10 - x                       # точно на ограничении
    area = x * y
    if best is None or area > best[2]:
        best = (x, y, area)
print("Оптимум на ограничении: x=%.1f y=%.1f площадь=%.2f" % best)
print("Предсказание Лагранжа (x=y): x=y=5, площадь=25")

Вывод:

Оптимум на ограничении: x=5.0 y=5.0 площадь=25.00
Предсказание Лагранжа (x=y): x=y=5, площадь=25

Перебор по кривой ограничения подтвердил предсказание Лагранжа: квадрат $5\times5$ — лучший прямоугольник. Условие $\nabla f=\lambda\nabla g$ сразу дало $x=y$, не перебирая.

Смысл множителя $\lambda$

Как и теневая цена в LP, множитель $\lambda$ показывает чувствительность: на сколько изменится оптимум $f^*$, если чуть ослабить ограничение (сдвинуть $g=0$ на $g=\varepsilon$). Это не абстрактное число, а «цена» ограничения. Поэтому Лагранж и двойственность LP — две грани одной теории.

Как работает под капотом

Несколько ограничений-равенств $g_1=\dots=g_m=0$ обобщаются прямо: $\nabla f=\sum_i\lambda_i\nabla g_i$ — градиент цели лежит в плоскости, натянутой на градиенты ограничений. Решение системы $\nabla_x\mathcal{L}=0,\ g_i=0$ — это $n+m$ уравнений на $n+m$ неизвестных; для нелинейных ограничений её решают численно (тем же Ньютоном). Важно: Лагранж даёт необходимое условие; чтобы убедиться, что это минимум, а не максимум или седло, проверяют второй порядок (окаймлённый гессиан).

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

• Искать $\nabla f=0$ при наличии ограничения. Условный минимум обычно не совпадает с безусловным.
• Забыть само ограничение. Условие $\nabla f=\lambda\nabla g$ нужно решать вместе с $g=0$.
• Принять любое решение системы за минимум. Это может быть максимум или седло — проверяйте знак.

Итоги

• В условном минимуме при $g=0$ градиенты параллельны: $\nabla f=\lambda\nabla g$ (касание линий уровня).
• Функция Лагранжа $\mathcal{L}=f-\lambda g$ сводит условную задачу к безусловной по $(x,\lambda)$.
• Множитель $\lambda$ — чувствительность оптимума к ослаблению ограничения.