Лагранж и ККТ

Почему нужно новое условие

Из урока 020: в минимуме градиент равен нулю — но только для внутренней точки. На границе это неверно. Минимум $x^2$ на отрезке $[1,2]$ достигается в $x = 1$, где $f' = 2 \ne 0$: уйти вниз хочется, но нельзя.

Правильная формулировка: в оптимуме градиент не обязан быть нулём, он обязан быть полностью погашен ограничениями.

Равенства: метод Лагранжа

Для задачи $\min f(x)$ при $g(x) = 0$ вводим

$$\htmlData{k=lag}{\mathcal{L}(x, \lambda) = f(x) + \htmlData{k=mult}{\lambda}\, g(x)}, \qquad \nabla_x \mathcal{L} = 0, \quad g(x) = 0$$

Геометрический смысл первого условия: $\nabla f = -\lambda \nabla g$, то есть градиенты параллельны. Иначе существовала бы компонента градиента вдоль поверхности ограничения, и по ней можно было бы спуститься, не нарушая условия.

Проверим на примере: $\min \frac12(x^2+y^2)$ при $x + y = c$. Условия дают $x = y = c/2$ и $\lambda = c/2$. Для $c = 2$: точка $(1,1)$, значение $1$, множитель $1$.

цель: ½(x²+y²)штрафная версия

f(x, y)

1

градиент

1, 1

норма градиента

1.41

Второй ландшафт стоит посмотреть: штрафной метод — самый простой способ учесть ограничение, и у него есть цена. При конечном коэффициенте минимум не лежит на ограничении точно, а при большом коэффициенте задача становится плохо обусловленной — ровно та проблема, которой посвящён урок 050.

Неравенства: условия ККТ

Для $\min f(x)$ при $g(x) \le 0$ добавляются два новых требования.

$\nabla f + \lambda \nabla g = 0, \qquad g(x) \le 0, \qquad \underbrace{\lambda \ge 0}_{\text{знак}}, \qquad \underbrace{\lambda \, g(x) = 0}_{\text{комплементарность}}$

Два последних условия — вся суть, и оба содержательны.

Знак множителя. Для равенства $\lambda$ мог быть любым; для неравенства он обязан быть неотрицательным. Причина: ограничение давит только с одной стороны. Если бы $\lambda < 0$, условие «толкало» бы решение внутрь допустимой области, где оно и так свободно.

Комплементарность $\lambda g(x) = 0$ означает: в оптимуме либо ограничение активно ($g = 0$), либо его множитель нулевой ($\lambda = 0$). Иначе говоря — неактивные ограничения не влияют ни на что.

Проверим на $\min \frac12(x^2+y^2)$ при $x + y \ge c$:

$c$	решение	$\lambda$	активно?
$-1$	$(0,0)$	$0$	нет
$0$	$(0,0)$	$0$	на границе
$2$	$(1,1)$	$1$	да
$5$	$(2.5, 2.5)$	$2.5$	да

При $c \le 0$ безусловный оптимум $(0,0)$ уже удовлетворяет ограничению, значит ограничение неактивно и $\lambda = 0$. Произведение $\lambda \cdot (\text{зазор})$ равно нулю в каждой строке — в первой потому, что нулевой множитель, в остальных потому, что нулевой зазор.

Множитель — это цена

Самая полезная интерпретация: $\lambda$ показывает, насколько изменится оптимальное значение при ослаблении ограничения на единицу.

$\lambda^* = \frac{\partial f^*}{\partial c}$

Проверим по таблице выше: при $c = 2$ оптимум равен $1$, при $c = 5$ равен $6.25$. Производная $f^*(c) = c^2/4$ равна $c/2$, то есть $1$ при $c=2$ и $2.5$ при $c=5$ — в точности множители из таблицы.

Отсюда экономическое название «теневая цена»: $\lambda$ — сколько вы готовы заплатить за ослабление ограничения. Ноль означает «ограничение бесплатно», большое значение — «оно вам дорого стоит».

Двойственность, коротко

Определим двойственную функцию $d(\lambda) = \min_x \mathcal{L}(x, \lambda)$. Она обладает двумя свойствами:

• всегда даёт нижнюю границу на оптимум прямой задачи (слабая двойственность), потому что минимум по $x$ без ограничений не больше минимума при ограничениях;
• всегда вогнута, даже если прямая задача невыпукла — минимум семейства линейных по $\lambda$ функций вогнут.

Для выпуклых задач при мягких условиях граница точна (сильная двойственность), и тогда можно решать любую из двух задач. Это не только теория: двойственная формулировка SVM — то, что делает «ядерный трюк» возможным, потому что в ней данные входят только через скалярные произведения.

Где это встречается в машинном обучении

место	ограничение
SVM	отступы $\ge 1$; двойственная задача даёт ядра
максимальная энтропия	нормировка и заданные моменты → откуда экспоненциальное семейство
trust region, PPO	шаг или KL ограничены (уроки ветки B)
проекционные методы	параметры остаются в допустимом множестве
L1-регуляризация	эквивалентна ограничению $\|w\|_1 \le t$

Последняя строка — важный частный случай. Задача «минимизировать лосс при $\|w\|_1 \le t$» и задача «минимизировать лосс $+ \lambda\|w\|_1$» эквивалентны при подходящем соответствии $t \leftrightarrow \lambda$, и $\lambda$ здесь — тот самый множитель Лагранжа. То есть всякая регуляризация с коэффициентом — это ограничение, записанное через свою теневую цену. Ровно так же, как в блоке 3 всякий регуляризатор оказался prior.