Двойственность 🪞

Возьми любую задачу оптимизации с ограничениями — и у неё почти всегда найдётся зеркальный близнец: другая задача, с другими переменными, часто с противоположным направлением оптимизации, но связанная с исходной настолько тесно, что решение одной задачи почти даром отдаёт тебе решение другой. Эту вторую задачу называют двойственной (dual), а исходную — прямой (primal). На первый взгляд это выглядит как математическая забава: зачем решать вторую задачу, если нужна первая? Ответ в том, что двойственная задача иногда решается сильно проще прямой, иногда даёт строгую нижнюю (или верхнюю) оценку на прямую без её точного решения, а иногда — как в случае SVM — двойственная формулировка становится единственной практически реализуемой версией задачи.

Именно так устроен метод опорных векторов. В прямой постановке SVM ищет вектор весов $w$ и смещение $b$, минимизируя $\frac12\|w\|^2$ при ограничениях, что каждая точка обучающей выборки лежит по правильную сторону разделяющей полосы. Это выпуклая задача, но она напрямую работает в пространстве признаков — а признаковое пространство ядерных методов может быть бесконечномерным, и явно вычислить в нём $w$ попросту невозможно. Переход к двойственной задаче меняет всё: неизвестными становятся множители Лагранжа $\alpha_i$ — по одному на каждый обучающий пример, — а сами исходные признаки $x_i$ входят в задачу только через скалярные произведения $x_i \cdot x_j$. Это наблюдение — не побочный эффект, а главная причина, по которой работает kernel trick (ядерный трюк): скалярное произведение можно заменить произвольной ядерной функцией $K(x_i, x_j)$, которая неявно вычисляет скалярное произведение в пространстве высокой (или бесконечной) размерности, ни разу не строя это пространство явно. Без перехода к двойственной задаче ядерный трюк был бы физически неосуществим.

Этот урок — про то, откуда вообще берётся двойственная задача и почему её можно доверять. Ты увидишь, как из функции Лагранжа, знакомой тебе по условиям KKT из урока 279, механически строится двойственная задача для любой задачи оптимизации — выпуклой или нет. Дальше разберём слабую двойственность — факт, который выполняется всегда, без всяких условий на выпуклость, и доказывается в три строки. Затем — сильную двойственность, которая выполняется уже не всегда, а только при определённых условиях (для выпуклых задач это условие Слейтера), и именно она превращает двойственную задачу из «просто нижней оценки» в «точное решение прямой задачи под другим углом». И наконец — экономическую интерпретацию множителей Лагранжа как теневых цен, которая напрямую объясняет условие дополняющей нежёсткости из KKT: почему множитель при неактивном ограничении обязан быть равен нулю.

Если тебе предстоит когда-нибудь реализовывать SVM с ядрами, разбираться в том, почему регуляризация L1 и L2 связаны двойственностью с ограничениями на норму весов, или читать статьи по оптимизации, где авторы небрежно бросают фразу «переходя к двойственной задаче» без единого объяснения — этот урок даёт тебе словарь и математический аппарат, чтобы понимать, что именно происходит за этой фразой.

История

Идея двойственности выросла не из одной дисциплины, а сошлась сразу из нескольких направлений почти одновременно в середине XX века. В теории игр Джон фон Нейман ещё в 1928 году доказал теорему о минимаксе: в антагонистической игре двух игроков значение, которое минимизирующий игрок гарантированно не превысит, и значение, которое максимизирующий игрок гарантированно получит, совпадают в седловой точке. Это утверждение — по сути ранняя форма сильной двойственности, хотя тогда никто ещё не называл её этим словом.

Параллельно в 1947 году Джордж Данциг, придумавший симплекс-метод (урок 281), обсуждал свою работу с фон Нейманом, и именно фон Нейман предложил Данцигу явную формулировку двойственной задачи линейного программирования и указал на связь с теорией игр. Формальное доказательство теоремы двойственности линейного программирования опубликовали в начале 1950-х Дэвид Гейл, Гарольд Кун и Альберт Такер — те же Кун и Такер, чьи имена носят условия KKT. Это не случайное совпадение: KKT-условия и теория двойственности выросли из одного и того же математического аппарата — функции Лагранжа — и исторически развивались одной и той же небольшой группой математиков практически синхронно.

К 1990-м годам, когда Владимир Вапник и Коринна Кортес формулировали метод опорных векторов, теория двойственности Лагранжа была уже полностью зрелым инструментом — и именно поэтому переход к двойственной формулировке SVM не потребовал изобретения ничего нового: он оказался прямым применением полувековой давности теории к новой задаче. С тех пор двойственность перестала быть красивой теоретической конструкцией и стала рабочим инструментом всего машинного обучения: она стоит за ядерными методами, за анализом сходимости алгоритмов, за постановкой регуляризованных задач и даже за интерпретацией состязательного обучения в GAN как задачи с седловой точкой.

Построение двойственной задачи через функцию Лагранжа

Интуиция: спрятать ограничения внутрь штрафа

Возьми задачу с ограничениями и попробуй временно забыть, что ограничения вообще существуют, — просто добавь к целевой функции штраф за их нарушение, взвешенный множителями $\lambda_i \ge 0$. Получившаяся функция, функция Лагранжа, при правильном подборе множителей ведёт себя как исходная задача без ограничений: если множитель достаточно велик, минимизировать её без ограничений — то же самое, что минимизировать исходную функцию с ограничениями. Вопрос лишь в том, что считать «правильным подбором» множителей — и именно ответ на этот вопрос и есть двойственная задача.

Определение

Функция Лагранжа и двойственная задача. Пусть прямая задача имеет вид

$$\text{minimize } f_0(x) \quad \text{при } g_i(x)\le0,\ i=1,\dots,m,\quad h_j(x)=0,\ j=1,\dots,p$$

Функция Лагранжа: $L(x,\lambda,\nu) = f_0(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x)$, где $\lambda_i \ge 0$. Двойственная функция: $q(\lambda,\nu) = \inf_x L(x,\lambda,\nu)$ — минимум по $x$ при фиксированных множителях. Двойственная задача: $\text{maximize } q(\lambda,\nu)$ при $\lambda \ge 0$. Двойственная функция $q$ всегда вогнута (даже если исходная задача невыпуклая), поэтому двойственная задача всегда — задача выпуклой оптимизации, независимо от природы прямой задачи.

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

Пример 1: линейное программирование — классическая пара max/min

Возьмём задачу распределения ресурсов дата-центра: нужно решить, сколько серверов типа A ($x_1$) и типа B ($x_2$) развернуть, чтобы максимизировать прибыль в тысячах долларов:

Первое ограничение — лимит поставок процессоров типа A, второе — лимит охлаждающих модулей, третье — лимит человеко-часов сборки. Чтобы построить двойственную задачу через Лагранжиан, сначала перепишем максимизацию как минимизацию: $\text{minimize } -3x_1-5x_2$ при $x_1-4\le0$, $2x_2-12\le0$, $3x_1+2x_2-18\le0$, $-x_1\le0$, $-x_2\le0$.

Лагранжиан: $L = -3x_1-5x_2 + y_1(x_1-4)+y_2(2x_2-12)+y_3(3x_1+2x_2-18) - \mu_1 x_1 - \mu_2 x_2$, где все множители $\ge0$. Сгруппируем по $x_1$ и $x_2$:

Минимум по $x_1\in\mathbb R$ (без ограничения на знак — знак уже учтён отдельным множителем $\mu$) равен $-\infty$, если коэффициент при $x_1$ не равен нулю, и не зависит от $x_1$, если коэффициент равен нулю. Значит, чтобы $\inf_x L$ было конечным (а только конечные значения нам и интересны в двойственной задаче), нужно потребовать $-3+y_1+3y_3-\mu_1=0$ и $-5+2y_2+2y_3-\mu_2=0$. Поскольку $\mu_1,\mu_2\ge0$, это эквивалентно $y_1+3y_3\ge3$ и $2y_2+2y_3\ge5$ (переменные $\mu$ просто «поглощают» избыток и после исключения из формулировки не влияют на ответ). Двойственная функция при этом равна $q(y)=-4y_1-12y_2-18y_3$, и, возвращаясь к исходной максимизации, двойственная задача — это

Каждая переменная $y_i$ — это «цена» соответствующего ресурса (процессоры, охлаждение, человеко-часы), а каждое ограничение двойственной задачи говорит: суммарная цена ресурсов, потраченных на единицу продукта, должна быть не меньше прибыли от этого продукта — иначе выгоднее просто перепродать ресурсы, чем делать из них сервер.

Пример 2: гладкая задача с ограничением-неравенством

Возьмём $\text{minimize } x^2+y^2$ при $x+y\ge1$, то есть $1-x-y\le0$. Лагранжиан: $L(x,y,\lambda) = x^2+y^2+\lambda(1-x-y)$, $\lambda\ge0$. Минимум по $x,y$ находится обнулением частных производных: $\partial L/\partial x = 2x-\lambda=0 \Rightarrow x=\lambda/2$; аналогично $y=\lambda/2$. Подставляем обратно:

Двойственная задача — $\text{maximize}_{\lambda\ge0}\ \lambda-\frac{\lambda^2}2$. Это одномерная гладкая задача: $q'(\lambda)=1-\lambda=0\Rightarrow\lambda^*=1$ (условие $\lambda\ge0$ выполнено), $q(1)=1-\frac12=\frac12$.

Пример 3: SVM — двойственная задача, на которой держится kernel trick

Прямая задача жёсткого зазора SVM: $\text{minimize } \frac12\|w\|^2$ при $1-y_i(w\cdot x_i+b)\le0$ для всех $i=1,\dots,n$. Лагранжиан: $L(w,b,\lambda) = \frac12\|w\|^2 + \sum_i\lambda_i\bigl[1-y_i(w\cdot x_i+b)\bigr]$. Берём частные производные и приравниваем нулю:

Подставляем $w=\sum_i\lambda_iy_ix_i$ обратно в Лагранжиан. Слагаемое с $b$ исчезает благодаря второму условию. После упрощения $\frac12\|w\|^2 = \frac12\sum_i\sum_j\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)$, а перекрёстный член $\sum_i\lambda_iy_i(w\cdot x_i)$ равен $w\cdot w=\|w\|^2$, поэтому в сумме остаётся:

Двойственная задача: $\text{maximize}\ q(\lambda)$ при $\lambda_i\ge0$ и $\sum_i\lambda_iy_i=0$. Обрати внимание на структуру этого выражения: переменные $x_i$ входят в задачу исключительно как скалярные произведения $x_i\cdot x_j$. Это значит, что для решения задачи не нужно знать сами векторы $x_i$ — достаточно знать все попарные скалярные произведения. А раз так, скалярное произведение можно заменить на ядерную функцию $K(x_i,x_j)$, которая соответствует скалярному произведению в некотором (возможно, бесконечномерном) пространстве признаков — не вычисляя это пространство явно. Именно эта замена и называется kernel trick, и она была бы попросту невозможна в прямой формулировке, где $w$ — вектор в самом этом пространстве.

Почему это важно

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

Слабая двойственность

Интуиция: любая нижняя оценка снизу — всё ещё оценка снизу

Даже не решая двойственную задачу до конца, любое допустимое значение множителей $\lambda,\nu$ (то есть $\lambda\ge0$) даёт тебе гарантированную нижнюю оценку на оптимум прямой задачи. Это работает всегда — для выпуклых задач, для невыпуклых, для задач с целочисленными переменными, для чего угодно. Причина в одной короткой цепочке неравенств, которая не использует вообще никаких предположений о структуре задачи, кроме знака множителей.

Теорема

Слабая двойственность. Пусть $p^*$ — оптимальное значение прямой задачи $\text{minimize } f_0(x)$ при $g_i(x)\le0$, $h_j(x)=0$, а $d^*$ — оптимальное значение двойственной задачи $\text{maximize}_{\lambda\ge0,\nu} q(\lambda,\nu)$. Тогда всегда, без каких-либо дополнительных условий, $d^*\le p^*$.

Доказательство. Возьмём произвольную допустимую точку прямой задачи $x$ (то есть $g_i(x)\le0$ для всех $i$, $h_j(x)=0$ для всех $j$) и произвольную допустимую точку двойственной задачи $\lambda\ge0,\nu$. Тогда

потому что каждое слагаемое $\lambda_i g_i(x)$ — произведение неотрицательного числа на неположительное, то есть неположительно, а каждое $\nu_j h_j(x)=0$ из-за допустимости $x$. Далее, по определению двойственной функции как инфимума по всем $x$ (не только по допустимым):

Это неравенство верно для любой допустимой $x$ — значит, верно и для оптимальной $x^*$, где $f_0(x^*)=p^*$. Значит, $q(\lambda,\nu)\le p^*$ для любых допустимых $\lambda,\nu$. Взяв супремум по всем допустимым $\lambda,\nu$ слева, получаем $d^*\le p^*$. $\blacksquare$

Пример 1: проверка на LP из дата-центра

В примере с серверами прямая задача даёт $p^*=36$ (тыс. долларов, точка $x_1=2,x_2=6$). Возьмём произвольную, не обязательно оптимальную допустимую точку двойственной задачи, например $y_1=1,y_2=2,y_3=1$: проверим допустимость — $y_1+3y_3=1+3=4\ge3$ ✓, $2y_2+2y_3=4+2=6\ge5$ ✓. Значение двойственной функции: $4\cdot1+12\cdot2+18\cdot1=4+24+18=46$. Слабая двойственность обещает $46\ge36$ (для пары max-примой/min-двойственной неравенство разворачивается: прямая максимизация всегда $\le$ двойственной минимизации) — и действительно $46\ge36$, хотя выбранная точка совсем не оптимальна для двойственной задачи.

Пример 2: проверка на гладкой QP-задаче

Для задачи $\min x^2+y^2$ при $x+y\ge1$ (где $p^*=\frac12$) возьмём заведомо не оптимальный, но допустимый множитель $\lambda=0$. Тогда $q(0)=\inf_{x,y} x^2+y^2 = 0$ (достигается в $x=y=0$, и никакого ограничения на $x,y$ при $\lambda=0$ уже нет — Лагранжиан при $\lambda=0$ совпадает с исходной целевой функцией без ограничений). Слабая двойственность обещает $q(0)\le p^*$, то есть $0\le\frac12$ — выполняется, хотя $\lambda=0$ — заведомо худший из всех допустимых множителей.

Пример 3: слабая двойственность держится и без выпуклости

Возьмём задачу $\text{minimize}\ f(x)=-x$ на дискретном (невыпуклом!) множестве $x\in X=\{0,2\}$ при ограничении $x\le1$. Единственная допустимая точка — $x=0$ (поскольку $2>1$ не проходит по ограничению), значит $p^*=-0=0$. Лагранжиан: $L(x,\lambda)=-x+\lambda(x-1)=(\lambda-1)x-\lambda$. При $\lambda=2$: $L(0,2)=-2$, $L(2,2)=2(2-1)-2\cdot2\cdot\ldots$ — посчитаем аккуратно: $(\lambda-1)x-\lambda$ при $\lambda=2,x=2$ равно $1\cdot2-2=0$; при $x=0$ равно $-2$. Значит $q(2)=\min\{-2,0\}=-2\le0=p^*$ — неравенство держится, несмотря на то что множество $X$ невыпуклое, а значит формальных предпосылок для сильной двойственности здесь нет вовсе.

Почему это важно

Слабая двойственность — это твоя страховка: какую бы точку двойственной задачи ты ни нашёл, даже не решив её до конца, ты получаешь гарантированную оценку снизу (или сверху, в зависимости от направления оптимизации) на решение прямой задачи, которую иначе, возможно, решить нельзя вовсе — например, потому что прямая задача невыпуклая и NP-трудная. Именно на этом принципе держится, например, метод ветвей и границ в целочисленном программировании: релаксация Лагранжа даёт быструю нижнюю оценку, которая отсекает заведомо неоптимальные ветви перебора, даже когда точное решение прямой задачи недостижимо за разумное время.

Сильная двойственность

Интуиция: когда зазор между оценками схлопывается до нуля

Слабая двойственность гарантирует $d^*\le p^*$ всегда, но ничего не говорит о том, насколько $d^*$ меньше $p^*$. Разница $p^*-d^*$ называется двойственным зазором (duality gap), и в общем случае она может быть сколь угодно большой — двойственная задача превращается в бесполезную, слишком грубую оценку. Но для широкого и важного класса задач — выпуклых, при дополнительном условии регулярности — этот зазор оказывается ровно нулевым: решение двойственной задачи даёт точное значение прямой, просто с другой стороны.

Теорема

Сильная двойственность при условии Слейтера. Пусть прямая задача выпуклая: $f_0$ и все $g_i$ выпуклы, а $h_j$ аффинны (линейны). Если существует строго допустимая точка $\tilde x$, то есть $g_i(\tilde x)<0$ для всех $i$ и $h_j(\tilde x)=0$ для всех $j$ (условие Слейтера), то сильная двойственность выполняется: $d^*=p^*$. Более того, если оптимумы $p^*$ и $d^*$ достигаются в точках $x^*$ и $(\lambda^*,\nu^*)$, то эта пара точек удовлетворяет условиям KKT.

Отдельно для линейного программирования (частный случай, где все ограничения аффинны): достаточно, чтобы прямая задача была допустима и ограничена — условие Слейтера автоматически ослабляется до простой допустимости, строгая внутренняя точка не требуется. Это и есть основная теорема двойственности линейного программирования: если у прямой и двойственной задач ЛП есть оптимальные решения, их значения совпадают в точности.

Пример 1: линейное программирование — зазор всегда нулевой

Продолжим пример с дата-центром. Мы уже нашли $p^*=36$ (прямая) и, решая двойственную задачу через дополняющую нежёсткость, получили $y_1=0,\ y_2=1.5,\ y_3=1$, откуда $d^*=4\cdot0+12\cdot1.5+18\cdot1=18+18=36$. Значения совпали в точности — зазор равен нулю, как и обещает фундаментальная теорема двойственности ЛП, без всякой проверки условия Слейтера (для линейных ограничений оно не нужно в строгой форме).

from scipy.optimize import linprog

# Прямая задача: max 3x1+5x2  <=>  min -3x1-5x2
c = [-3, -5]
A_ub = [[1, 0], [0, 2], [3, 2]]
b_ub = [4, 12, 18]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None)] * 2)
print(-res.fun, res.x)   # 36.0 [2. 6.]

Пример 2: выпуклая гладкая задача — зазор тоже нулевой

Для задачи $\min x^2+y^2$ при $x+y\ge1$ мы уже нашли $d^*=\frac12$ (при $\lambda^*=1$). Прямой оптимум: минимизировать сумму квадратов на прямой $x+y=1$ — по симметрии оптимум в $x=y=\frac12$, значение $\frac14+\frac14=\frac12$. Совпадает: $p^*=d^*=\frac12$. Условие Слейтера здесь выполняется тривиально: возьми, например, $\tilde x=\tilde y=1$, тогда $1-\tilde x-\tilde y=-1<0$ — строгая допустимость есть, задача выпуклая (квадратичная целевая функция и линейное ограничение), значит сильная двойственность гарантирована теоремой заранее, ещё до вычислений.

Пример 3: без выпуклости зазор может быть строго положительным

Вернёмся к невыпуклому примеру из предыдущего раздела: $\min -x$ при $x\le1$, $x\in\{0,2\}$. Мы получили $p^*=0$. Найдём $d^*$ полностью: $q(\lambda)=\min\{L(0,\lambda),L(2,\lambda)\}=\min\{-\lambda,\ (\lambda-1)\}$ (подставляя $x=0$ и $x=2$ в $L=(\lambda-1)x-\lambda$). При $\lambda\le1$ минимум — это $\lambda-2$... пересчитаем аккуратно: $L(0,\lambda)=-\lambda$, $L(2,\lambda)=2(\lambda-1)-\lambda=\lambda-2$. Сравнение: $-\lambda\le\lambda-2 \iff \lambda\ge1$. Значит $q(\lambda)=\lambda-2$ при $\lambda\le1$ и $q(\lambda)=-\lambda$ при $\lambda\ge1$ — кусочно-линейная функция, растущая до $\lambda=1$ и убывающая после. Максимум в $\lambda=1$: $q(1)=-1$. Значит $d^*=-1$, а $p^*=0$ — зазор $p^*-d^*=1>0$. Условие Слейтера здесь неприменимо в принципе, потому что $X=\{0,2\}$ не выпукло: сама теорема о сильной двойственности требует выпуклости допустимого множества, и без неё ничего не гарантирует нулевой зазор.

Почему это важно

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

Теневые цены и связь с условиями ККТ

Интуиция: множитель Лагранжа как цена на единицу ресурса

Вернись к экономической интерпретации примера с дата-центром: множитель $y_2^*=1.5$ при ограничении на охлаждающие модули — это не абстрактное число, а буквально предельная стоимость одного дополнительного охлаждающего модуля, выраженная в той же валюте, что и прибыль. Если ты немного ослабишь это ограничение — получишь чуть больше ресурса, — оптимальная прибыль вырастет примерно на $y_2^*$ за каждую дополнительную единицу ресурса. Экономисты называют такие величины теневыми ценами (shadow prices): это не рыночная цена, которую ты платишь за ресурс, а внутренняя, «теневая» ценность этого ресурса именно для этой конкретной задачи оптимизации.

Теорема

Интерпретация множителей как чувствительности оптимума. Пусть прямая задача выпуклая, выполняется сильная двойственность, и функция $p^*(u)$ — оптимальное значение задачи с ослабленным ограничением $g_i(x)\le u_i$ — дифференцируема в точке $u=0$. Тогда $\dfrac{\partial p^*}{\partial u_i}\Big|_{u=0} = -\lambda_i^*$ для минимизационной формы задачи (для максимизационной формы, как в LP-примере выше, знак меняется на противоположный: рост правой части ограничения на единицу увеличивает оптимум примерно на величину соответствующего множителя).

Условие дополняющей нежёсткости как следствие сильной двойственности. Если $x^*$ и $(\lambda^*,\nu^*)$ — оптимальные пары прямой и двойственной задач при $d^*=p^*$, то $\lambda_i^* g_i(x^*)=0$ для всех $i$.

Доказательство дополняющей нежёсткости. Повторим цепочку неравенств из доказательства слабой двойственности, но теперь для оптимальных $x^*,\lambda^*,\nu^*$, и используем, что по условию сильной двойственности первое и последнее звенья цепочки равны:

Левый и правый концы этой цепочки равны $p^*$ — значит, все неравенства внутри неё на самом деле равенства. В частности, $\sum_i\lambda_i^*g_i(x^*)=0$. Но каждое слагаемое этой суммы неположительно ($\lambda_i^*\ge0$, $g_i(x^*)\le0$), а сумма неположительных чисел равна нулю только тогда, когда каждое слагаемое равно нулю по отдельности. Значит, $\lambda_i^*g_i(x^*)=0$ для каждого $i$ — это и есть третье условие KKT из урока 279, но теперь ты видишь не просто список условий, а откуда оно берётся: это прямое алгебраическое следствие того, что зазор между прямой и двойственной задачей стал нулевым. $\blacksquare$

Пример 1: теневая цена в LP подтверждается пересчётом

Возьмём тот же дата-центр и увеличим лимит охлаждающих модулей на единицу: $2x_2\le13$ вместо $2x_2\le12$. Пересчитаем оптимум: активными остаются те же два ограничения, $2x_2=13\Rightarrow x_2=6.5$, и $3x_1+2\cdot6.5=18\Rightarrow x_1=\frac53\approx1.667$ (по-прежнему $\le4$, ограничение 1 не активно). Новая прибыль: $3\cdot\frac53+5\cdot6.5=5+32.5=37.5$. Прирост прибыли составил ровно $37.5-36=1.5$ — точно теневая цена $y_2^*=1.5$, найденная ранее из дополняющей нежёсткости, без всякого пересчёта всей задачи заново.

Пример 2: нулевая цена у неактивного ограничения

В том же примере $y_1^*=0$ — множитель при ограничении на процессоры $x_1\le4$. Это ограничение в оптимуме не активно ($x_1^*=2<4$), и дополняющая нежёсткость требует именно нулевого множителя. Экономический смысл: у тебя есть избыток процессоров, они не являются узким местом производства, и предельная теневая цена лишней единицы этого ресурса равна нулю — лишний процессор просто не будет использован.

Пример 3: опорные векторы SVM как активные ограничения

В двойственной задаче SVM условие дополняющей нежёсткости имеет вид $\lambda_i\bigl[1-y_i(w\cdot x_i+b)\bigr]=0$. Это значит: если $\lambda_i>0$, то ограничение обязано быть активным, $y_i(w\cdot x_i+b)=1$ — точка лежит ровно на границе зазора. Такие точки называют опорными векторами, и это ровно те объекты, у которых «теневая цена» ненулевая: они и только они определяют положение разделяющей гиперплоскости. Для всех остальных объектов $\lambda_i=0$, и их можно было бы вообще удалить из обучающей выборки, не изменив решение ни на йоту — их «ограничение» не активно, ресурс не дефицитен, теневая цена нулевая.

Почему это важно

Теневые цены переводят абстрактные множители Лагранжа на язык, понятный без всякой теории: это ответ на вопрос «на сколько улучшится решение, если чуть-чуть ослабить это конкретное ограничение». А условие дополняющей нежёсткости, которое из KKT-урока могло выглядеть как одно из четырёх формальных условий в списке, здесь оказывается прямым следствием единственного факта — равенства $p^*=d^*$. В SVM это условие буквально отвечает за то, что итоговая модель зависит только от небольшого подмножества обучающих точек — опорных векторов, — а не от всей выборки целиком, что и даёт методу его название.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Построй двойственную задачу для $\text{maximize } 2x_1+3x_2$ при $x_1+x_2\le4$, $x_1\le3$, $x_1,x_2\ge0$.

Задание 2: Для прямой задачи $\text{maximize } 5x$ при $x\le10$, $x\ge0$ найди $p^*$ и постройся двойственную, найди $d^*$, проверь совпадение.

Задание 3: Известно, что двойственная задача (минимизация) допустима, но прямая (максимизация) неограничена сверху. Что это означает для двойственной задачи?

Задание 4: Запиши функцию Лагранжа для задачи $\text{minimize } x^2$ при $x\ge2$.

Задание 5: Для задачи из задания 4 найди двойственную функцию $q(\lambda)$ и двойственную задачу.

Задание 6: Реши двойственную задачу из задания 5 и сравни с прямым оптимумом $x^*=2$, $p^*=4$.

Задание 7: В прямой задаче SVM объясни, что произойдёт с решением, если удалить из выборки объект с $\lambda_i=0$.

Задание 8: Дана пара прямая/двойственная ЛП с $p^*=20$, $d^*=20$. Что можно сказать про точки, где оба оптимума достигаются?

Задание 9: Почему двойственная функция $q(\lambda,\nu)$ всегда вогнута, даже если прямая задача невыпуклая?

Задание 10: Сформулируй условие Слейтера для задачи $\text{minimize } x^2+y^2$ при $x^2+y^2\le1$, $x+y=1$, и проверь, выполняется ли оно.

Средние задания (11–20)

Задание 11: Докажи слабую двойственность для пары максимизационной прямой $\text{maximize } c^Tx$ при $Ax\le b,\ x\ge0$ и минимизационной двойственной $\text{minimize } b^Ty$ при $A^Ty\ge c,\ y\ge0$ напрямую, без перехода к общей форме Лагранжа.

Задание 12: Для задачи дата-центра ($\text{max } 3x_1+5x_2$ при $x_1\le4,\ 2x_2\le12,\ 3x_1+2x_2\le18$) найди двойственную задачу и подтверди дополняющей нежёсткостью, что $y_1^*=0$.

Задание 13: Реши двойственную задачу из задания 12 (найди $y_2^*,y_3^*$), используя $y_1^*=0$ и активность двух других прямых ограничений.

Задание 14: Правило Лопиталя тут ни при чём, но проверь: посчитай значение двойственной функции из задания 13 и сравни с $p^*=36$.

Задание 15: Дана невыпуклая задача $\text{minimize}\ -x$ при $x\in\{0,3\}$, $x\le2$. Найди $p^*$ и покажи, что $p^*=-0=0$.

Задание 16: Для задачи из задания 15 построй $q(\lambda)$ и найди $d^*$; сравни зазор с примером из теоретической части, где было $X=\{0,2\}$.

Задание 17: В SVM найди, чему равно $\sum_i \lambda_i^* y_i x_i \cdot x_i$ через норму $\|w^*\|^2$, если известно, что $w^*=\sum_i\lambda_i^*y_ix_i$.

Задание 18: Ядро $K(x,z)=(x\cdot z+1)^2$ задаёт полиномиальное отображение в пространство признаков высокой размерности. Почему двойственная (а не прямая) формулировка SVM необходима, чтобы использовать такое ядро?

Задание 19: Для задачи $\text{minimize } x^2$ при $x=3$ (только ограничение-равенство) построй Лагранжиан и найди двойственную функцию.

Задание 20: Реши двойственную задачу из задания 19 (заметь: $\nu$ не ограничен по знаку, так как это множитель равенства) и сравни с $p^*=9$ (при $x^*=3$).

Продвинутые задания (21–30)

Задание 21: Построй Лагранжиан и двойственную задачу для $\text{minimize } c^Tx$ при $Ax=b$ (только равенства, без неравенств) — общая форма ЛП без ограничения на знак $x$.

Задание 22: Для LP-пары дата-центра пересчитай оптимум, увеличив лимит человеко-часов сборки (третье ограничение, $18\to19$), и подтверди теневую цену $y_3^*=1$.

Задание 23: Рассмотрим прямую задачу SVM с мягким зазором: $\text{minimize } \frac12\|w\|^2+C\sum_i\xi_i$ при $y_i(w\cdot x_i+b)\ge1-\xi_i,\ \xi_i\ge0$. Составь Лагранжиан с множителями $\lambda_i\ge0$ (за первое ограничение) и $\mu_i\ge0$ (за $\xi_i\ge0$).

Задание 24: Для задачи из задания 23 возьми производную по $\xi_i$ и покажи, что она даёт ограничение $0\le\lambda_i\le C$ на двойственные переменные — знаменитый «box constraint» мягкого зазора.

Задание 25: Объясни экономически, почему в примере с дата-центром одновременное увеличение лимита охлаждения на 1 единицу и лимита человеко-часов на 1 единицу должно увеличить прибыль примерно на $y_2^*+y_3^*=1.5+1=2.5$ (тыс. долларов), а не на что-то другое.

Задание 26: Приведи пример задачи, где прямая задача неразрешима (нет допустимых точек), но покажи, что тогда двойственная задача обязана быть неограниченной (при условии, что она вообще допустима).

Задание 27: В портфельной оптимизации: $\text{minimize } x^T\Sigma x$ (риск) при $\mathbf 1^Tx=1$ (веса в сумме дают единицу), $x\ge0$. Составь Лагранжиан с множителем $\nu$ за равенство и $\mu\ge0$ за $x\ge0$, и выпиши стационарность по $x$.

Задание 28: В задаче регуляризации LASSO ($\min \|y-X\beta\|^2$ при $\|\beta\|_1\le t$) множитель Лагранжа при ограничении на норму — это в точности параметр регуляризации $\lambda$ из привычной штрафной формы $\min \|y-X\beta\|^2+\lambda\|\beta\|_1$. Объясни, почему это соответствие — прямое следствие построения двойственной задачи через Лагранжиан.

Задание 29: Покажи, что для задачи $\text{minimize } f_0(x)$ без ограничений вовсе (пустой набор $g_i,h_j$) прямая и двойственная задачи совпадают тривиально.

Задание 30: Дан невыпуклый пример из теоретического раздела ($X=\{0,2\}$, $\min -x$ при $x\le1$, $p^*=0$, $d^*=-1$). Как метод ветвей и границ использует эту двойственную оценку $d^*=-1$ на практике, если реальный ответ $p^*=0$?

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

Ошибка 1. Считают, что двойственная задача — это просто другая запись той же самой задачи с переставленными местами переменными.

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

Почему возникает: совпадение оптимальных значений $p^*=d^*$ при сильной двойственности создаёт иллюзию, что задачи идентичны, а не просто дают одно и то же число разными путями.

Как правильно: помнить, что двойственные переменные $\lambda,\nu$ имеют собственный смысл (теневые цены, множители Лагранжа), а восстановление прямого решения $x^*$ по двойственному оптимуму требует отдельного шага — например, для SVM это $w^*=\sum_i\lambda_i^*y_ix_i$, а не сам вектор $\lambda^*$.

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

Как выглядит: сразу приравнивают $p^*=d^*$, как только построена двойственная задача, не проверив выпуклость $f_0,g_i$ и аффинность $h_j$.

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

Как правильно: прежде чем полагаться на равенство $p^*=d^*$, явно проверить выпуклость прямой задачи и условие Слейтера (или использовать факт, что для линейного программирования достаточно простой допустимости) — как показано в примере с невыпуклым $X=\{0,2\}$, без этого зазор может быть строго положительным.

Ошибка 3. Путают направление неравенства слабой двойственности в зависимости от того, максимизация это или минимизация.

Как выглядит: механически пишут $d^*\le p^*$ для пары, где прямая задача — максимизация, хотя в этом случае правильное направление $p^*\le d^*$.

Почему возникает: общая теория (Бойда и большинства учебников по выпуклой оптимизации) формулируется для минимизационной прямой задачи, а классическая теория ЛП — для максимизационной, и при переносе интуиции забывают о развороте неравенства.

Как правильно: держать в голове одно простое правило: минимизирующая задача пары всегда даёт оценку сверху, максимизирующая — оценку снизу, независимо от того, какая из них названа «прямой», а какая «двойственной».

Ошибка 4. Забывают, что множитель при ограничении-равенстве $\nu_j$ не ограничен по знаку, в отличие от множителя при неравенстве $\lambda_i\ge0$.

Как выглядит: при построении Лагранжиана для задачи со смешанными ограничениями требуют $\nu_j\ge0$ так же, как для $\lambda_i$.

Почему возникает: визуальное сходство записи $\lambda_ig_i(x)+\nu_jh_j(x)$ создаёт впечатление, что оба типа множителей подчиняются одному и тому же правилу знака.

Как правильно: помнить происхождение знака: ограничение $g_i(x)\le0$ может быть нарушено только в одну сторону, и штраф должен быть неотрицательным при нарушении — отсюда $\lambda_i\ge0$. Равенство $h_j(x)=0$ может быть нарушено в обе стороны одинаково «плохо», поэтому множитель $\nu_j$ свободен по знаку (см. задание 19–21).

Ошибка 5. Считают дополняющую нежёсткость отдельным, независимым от остальных KKT-условием, которое нужно просто запомнить.

Как выглядит: заучивают $\lambda_ig_i(x^*)=0$ как формулу без понимания, откуда она берётся, и не могут объяснить, почему она вообще должна выполняться.

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

Как правильно: понимать, что это условие — прямое алгебраическое следствие равенства $p^*=d^*$ (сильной двойственности), выводимое в три строки из цепочки неравенств слабой двойственности, как показано в разделе про теневые цены.

Ошибка 6. Пытаются использовать kernel trick в прямой формулировке SVM.

Как выглядит: пытаются подставить ядерную функцию вместо $x_i\cdot x_j$ в формулу для $w$ или в прямые ограничения, не переходя к двойственной задаче.

Почему возникает: kernel trick воспринимается как отдельный «трюк», применимый к SVM вообще, а не как следствие конкретной алгебраической структуры именно двойственной задачи.

Как правильно: помнить, что замена скалярного произведения на ядро корректна только там, где данные действительно входят исключительно через скалярные произведения — а это верно только для двойственной задачи (и для предсказания $\text{sign}(\sum_i\lambda_iy_iK(x_i,x)+b)$), но не для прямой формулировки, где явно фигурирует вектор $w$ в пространстве признаков.

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

• Функция Лагранжа $L(x,\lambda,\nu)=f_0(x)+\sum_i\lambda_ig_i(x)+\sum_j\nu_jh_j(x)$ с $\lambda_i\ge0$ — отправная точка построения двойственной задачи для любой задачи оптимизации, выпуклой или нет.

• Двойственная функция $q(\lambda,\nu)=\inf_xL(x,\lambda,\nu)$ всегда вогнута, а двойственная задача $\text{maximize}_{\lambda\ge0,\nu}q(\lambda,\nu)$ всегда является задачей выпуклой оптимизации — независимо от природы прямой задачи.

• Слабая двойственность ($d^*\le p^*$ для минимизационной прямой задачи) выполняется всегда, без каких-либо условий на выпуклость, и доказывается в три строки через $q(\lambda,\nu)\le L(x,\lambda,\nu)\le f_0(x)$.

• Сильная двойственность ($d^*=p^*$) требует дополнительных условий: для выпуклых задач достаточно условия Слейтера (существования строго допустимой точки), для линейного программирования — достаточно простой допустимости и ограниченности.

• Для линейного программирования двойственная задача строится по прямому рецепту: максимизация становится минимизацией, ограничения-неравенства становятся переменными, а переменные — ограничениями, и зазор двойственности всегда равен нулю.

• Теневая цена — экономическая интерпретация множителя $\lambda_i^*$: она показывает, насколько изменится оптимальное значение при малом ослаблении $i$-го ограничения; у неактивных ограничений теневая цена всегда равна нулю.

• Условие дополняющей нежёсткости $\lambda_i^*g_i(x^*)=0$ из условий KKT (урок 279) — не самостоятельная аксиома, а прямое алгебраическое следствие равенства $p^*=d^*$ при сильной двойственности.

• Двойственная задача SVM $\max_\lambda \sum_i\lambda_i-\frac12\sum_{i,j}\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)$ при $\lambda_i\ge0,\ \sum_i\lambda_iy_i=0$ вводит данные только через скалярные произведения — это единственная причина, по которой kernel trick вообще возможен.

• Опорные векторы в SVM — это в точности объекты с $\lambda_i^*>0$, то есть объекты с ненулевой теневой ценой; все остальные объекты можно удалить из обучающей выборки без изменения решения.

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

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на условия KKT (урок 279): функция Лагранжа и множители $\lambda,\nu$, введённые там для формулировки условий оптимальности точки, здесь становятся полноценными переменными новой задачи — двойственной. Условие дополняющей нежёсткости, которое в уроке 279 было просто одним из четырёх пунктов списка, здесь получает строгое обоснование как следствие сильной двойственности. Также используются понятия выпуклой функции и выпуклого множества (уроки 277–278) — без них условие Слейтера и теорема о сильной двойственности не имеют смысла, — а сама конструкция «прямая задача → двойственная задача» для линейного программирования — это прямое обобщение симплекс-метода (урок 281) и линейного программирования (урок 280): любую задачу ЛП, для которой ты умеешь строить допустимую область и находить оптимум по угловым точкам, теперь можно превратить в её зеркального двойника с полностью другим набором переменных.

Что изучить дальше

В следующем уроке, 283 «Квадратичное программирование», двойственность становится не теоретической конструкцией, а рабочим алгоритмическим инструментом: именно двойственная задача SVM, построенная в этом уроке, представляет собой задачу квадратичного программирования с линейными ограничениями, и стандартные QP-солверы (такие как SMO — метод последовательной минимальной оптимизации) решают именно её, а не прямую задачу. Понимание того, как строится двойственная задача и почему сильная двойственность гарантирует совпадение оптимумов, необходимо, чтобы разбираться, почему QP-солвер, работающий с $\lambda$, действительно возвращает корректный классификатор.

Где это нужно в жизни

🤖 ML/AI — метод опорных векторов. Вся практическая реализация SVM с ядрами (RBF, полиномиальные, строковые ядра для текстов) существует только благодаря двойственной формулировке: данные входят исключительно через $K(x_i,x_j)$, что превращает нелинейную классификацию в линейную задачу в неявном пространстве признаков произвольной размерности. Опорные векторы — объекты с ненулевым множителем — это ровно то, что определяет решающую границу, а условие $0\le\lambda_i\le C$ в мягком зазоре напрямую следует из двойственной формулировки штрафа за нарушения (задания 23–24).

📉 Регуляризация и разреженные модели. Связь между ограниченной формой LASSO ($\|\beta\|_1\le t$) и штрафной формой ($\lambda\|\beta\|_1$) — это в точности связь между прямой и двойственной (точнее, лагранжевой релаксацией) формулировками одной и той же задачи (задание 28); параметр регуляризации $\lambda$, который ты подбираешь кросс-валидацией, буквально является множителем Лагранжа.

💰 Портфельная оптимизация. Задача Марковица (минимизация риска при фиксированной ожидаемой доходности и бюджетном ограничении) естественно формулируется через двойственность: множитель при бюджетном ограничении интерпретируется как теневая цена капитала — предельная выгода от дополнительной единицы средств для инвестирования (задание 27).

🎮 Теория игр и состязательное обучение. Минимаксная теорема фон Неймана, с которой исторически начиналась теория двойственности, напрямую описывает обучение GAN: генератор и дискриминатор решают противоположно направленные задачи оптимизации, и седловая точка их совместной игры — это в точности точка, где прямая и двойственная задачи достигают общего значения.

Интересные факты

• Джордж Данциг вспоминал, что именно короткий разговор с Джоном фон Нейманом в 1947 году, длившийся около часа, дал ему сразу и явную формулировку двойственной задачи линейного программирования, и указание на связь с минимаксной теоремой теории игр — притом что сам фон Нейман в тот момент работал совершенно в другой области и, по собственным словам Данцига, набросал доказательство «на салфетке», едва дослушав постановку задачи.

• В экономике теневая цена ресурса из двойственной задачи линейного программирования исторически стала одним из первых строгих математических обоснований ценообразования в плановой экономике: советские экономисты, в первую очередь Леонид Канторович (нобелевский лауреат по экономике 1975 года, разделивший премию именно за работы по оптимальному распределению ресурсов), использовали двойственные оценки как способ вычислить «объективно обусловленные оценки» ресурсов без обращения к рыночным механизмам.

• Алгоритм SMO (метод последовательной минимальной оптимизации), который Джон Платт предложил в 1998 году и который до сих пор лежит в основе большинства библиотечных реализаций SVM (включая scikit-learn), работает исключительно с двойственной задачей и решает её, оптимизируя по два множителя $\lambda_i,\lambda_j$ за раз — этот выбор был продиктован именно тем, что ограничение $\sum_i\lambda_iy_i=0$ в двойственной задаче делает невозможным менять один множитель изолированно, не трогая остальные.

• Двойственный зазор — не только теоретическая неприятность: в комбинаторной оптимизации (например, в задаче о коммивояжёре) разность между лучшей известной релаксацией Лагранжа и точным решением служит стандартной мерой качества эвристики и до сих пор активно используется как критерий остановки в промышленных решателях смешанного целочисленного программирования.

Лайфхаки

1. Строй Лагранжиан по одному и тому же чек-листу каждый раз: сначала перепиши все ограничения в форму $g_i(x)\le0$ или $h_j(x)=0$ (никаких $\ge$ или других знаков), затем добавь по одному множителю на каждое ограничение, и только потом минимизируй по прямым переменным. Пропуск шага «привести к стандартной форме» — самый частый источник ошибок со знаком.

2. Перед тем как искать $\inf_x L$, проверь, ограничена ли функция снизу по $x$ при произвольных (пока ещё не найденных) множителях. Если Лагранжиан линеен по какой-то из переменных и коэффициент при ней не равен нулю, инфимум будет $-\infty$ — это не ошибка, а сигнал, что соответствующее слагаемое даёт дополнительное ограничение на множители (как в задании 1, где линейность по $x_1,x_2$ дала именно ограничения двойственной задачи).

3. Используй дополняющую нежёсткость как ярлык, а не как последний шаг проверки. Если ты уже знаешь прямой оптимум $x^*$ и видишь, какие ограничения активны, а какие нет, можно сразу написать $\lambda_i^*=0$ для всех неактивных ограничений и решить оставшуюся систему для активных — это часто быстрее, чем решать двойственную задачу «с нуля» (см. задания 12–13).

4. Для проверки своих вычислений в задачах ЛП пересчитывай оптимум напрямую при небольшом изменении правой части одного из ограничений и сравнивай прирост с найденным множителем — если совпадает (как в заданиях 22 и 25), ты, скорее всего, не ошибся в дополняющей нежёсткости.

5. Не путай проверку выпуклости с проверкой линейности. Линейные функции одновременно и выпуклые, и вогнутые — поэтому в линейном программировании условие Слейтера тривиально ослабляется, и об этом легко забыть при переходе к нелинейным задачам, где выпуклость $f_0$ и $g_i$ нужно проверять отдельно и по-настоящему.

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

Двойственность — это тот редкий момент в курсе, где одна и та же математическая конструкция одновременно даёт тебе строгую теорию (слабая и сильная двойственность, условия Слейтера, вывод KKT из первых принципов) и прямой практический рычаг, без которого целые классы алгоритмов машинного обучения просто не существовали бы в нынешнем виде. В следующий раз, когда ты вызовешь SVC(kernel='rbf') в scikit-learn, будет полезно помнить, что где-то внутри библиотека решает не ту красивую задачу про разделяющую гиперплоскость, которую рисуют на слайдах, а её зеркального двойника — задачу про множители $\lambda_i$, построенную ровно теми методами, которые ты только что разобрал.