Двойственность (оптимизация)

Материал из MachineLearning.

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium в режиме агента ChatGPT Work) и проверена участником Aleksei Kovalenko 19:00, 15 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Двойственность (оптимизация).

Содержание

1 Прямая и двойственная задачи
2 Выпукло-аналитическая основа
3 Построение двойственной задачи
- 3.1 Практическая схема
- 3.2 Интерпретация множителей
4 Сильная двойственность и условия оптимальности
5 Частные случаи
6 Применения в машинном обучении
7 Сопоставление видов двойственности
8 Когда двойственная задача предпочтительнее
9 Ограничения и типичные ошибки
- 9.1 Ограничения теории
- 9.2 Ошибки при выводе
10 Классические результаты и современные алгоритмические направления
11 См. также
12 Примечания
13 Литература

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

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

Прямая и двойственная задачи

Общая лагранжева конструкция

Рассмотрим задачу

$p^*=\inf_{x\in D} f_0(x)$

при ограничениях

$f_i(x)\leq 0,\quad i=1,\ldots,m,\qquad h_j(x)=0,\quad j=1,\ldots,r.$

Здесь $D\subseteq\mathbb R^n$ — область определения; значение $p^*=+\infty$ соответствует несовместности, а $p^*=-\infty$ — неограниченности снизу. Эта задача называется прямой. Её Лагранжиан равен

$L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{j=1}^r\nu_j h_j(x),$

где множители неравенств выбираются из неотрицательного ортанта, $\lambda_i\geq0$ , а множители равенств $\nu_j$ свободны по знаку. Причина знакового ограничения элементарна: для допустимого $x$ произведение $\lambda_i f_i(x)$ неположительно, поэтому

$L(x,\lambda,\nu)\leq f_0(x).$

Двойственная функция Лагранжа

$g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu)$

является поточечным инфимумом аффинных функций переменных $(\lambda,\nu)$ и потому всегда вогнута, даже если прямая задача невыпукла. Двойственная задача Лагранжа имеет вид

$d^*=\sup_{\lambda\geq0,\,\nu}g(\lambda,\nu).$

В соглашении для прямой максимизации знаки и направления меняются. Надёжнее сначала переписать задачу как минимизацию с ограничениями вида $f_i\leq0$ , чем запоминать отдельные правила.

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

Для любого допустимого прямого $x$ и двойственно допустимых $(\lambda,\nu)$

$g(\lambda,\nu)\leq L(x,\lambda,\nu)\leq f_0(x).$

Следовательно,

$d^*\leq p^*.$

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

$\Delta(x,\lambda,\nu)=f_0(x)-g(\lambda,\nu)\geq0$

есть разрыв двойственности для данной допустимой пары и вычислимый сертификат: если $\Delta\leq\varepsilon$ , то прямое решение не более чем на $\varepsilon$ хуже оптимума. Если оба оптимальных значения конечны, оптимальный разрыв равен $p^*-d^*$ . Слабая двойственность не утверждает, что этот разрыв нулевой.

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

Для простоты без равенств введём множество достижимых значений

$\mathcal G=\{(u,t):\ \exists x\in D,\ f_i(x)\leq u_i,\ f_0(x)\leq t\}.$

Оптимальное значение — нижняя координата пересечения $\mathcal G$ с прямой $u=0$ . В выпуклой задаче $\mathcal G$ выпукло. Двойственный вектор задаёт гиперплоскость с нормалью $(\lambda,1)$ , поддерживающую $\mathcal G$ снизу. Слабая двойственность означает, что такая гиперплоскость не пересекает эпиграф ниже допустимого оптимума. Сильная двойственность возникает, когда в точке $(0,p^*)$ существует невырожденная опорная гиперплоскость с последней компонентой нормали, отличной от нуля. Условие Слейтера обеспечивает именно эту невырожденность в конечномерном выпуклом случае.^[1]

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

Экономическая интерпретация и чувствительность

Пусть правые части ограничений возмущены:

$f_i(x)\leq u_i,\qquad h_j(x)=v_j,$

а $p(u,v)$ — соответствующее оптимальное значение. Из слабой двойственности для оптимального двойственного решения невозмущённой задачи следует

$p(u,v)\geq p(0,0)-\lambda^{*T}u-\nu^{*T}v.$

Если функция значения дифференцируема в нуле и выполнены условия сильной двойственности, то

$\lambda_i^*=-\frac{\partial p}{\partial u_i}(0,0),\qquad \nu_j^*=-\frac{\partial p}{\partial v_j}(0,0).$

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

Выпукло-аналитическая основа

Сопряжённая функция

Для расширеннозначной функции $f:\mathbb R^n\to\mathbb R\cup\{+\infty\}$ её сопряжённая по Фенхелю функция определяется как

$f^*(y)=\sup_x\{\langle y,x\rangle-f(x)\}.$

Функция $f^*$ всегда выпукла и полунепрерывна снизу. Неравенство Фенхеля — Юнга утверждает

$f(x)+f^*(y)\geq\langle x,y\rangle.$

Для собственной замкнутой выпуклой функции равенство эквивалентно любому из условий

$y\in\partial f(x),\qquad x\in\partial f^*(y).$

По теореме Фенхеля — Моро $f^{**}=f$ для собственной замкнутой выпуклой функции; для произвольной собственной функции бисопряжённая функция задаёт её замкнутую выпуклую оболочку.^[1]

Если $f$ дифференцируема и строго выпукла на открытой области, то соответствие $y=\nabla f(x)$ локально обращается как $x=\nabla f^*(y)$ . В гладком случае это классическое Преобразование Лежандра; формула Фенхеля — Лежандра является его расширением на негладкие, нестрого выпуклые и расширеннозначные функции. Эти понятия не следует отождествлять без оговорки о предпосылках.

Полезные примеры:

Для $f(x)=\frac12\|x\|_2^2$ имеем $f^*(y)=\frac12\|y\|_2^2$ .
Для индикатора выпуклого множества $\delta_C(x)$ , равного нулю на $C$ и $+\infty$ вне $C$ , сопряжённая функция есть Опорная функция $\sigma_C(y)=\sup_{x\in C}\langle y,x\rangle$ .
Для нормы $f(x)=\|x\|$ сопряжённая равна индикатору единичного шара двойственной нормы: $f^*(y)=\delta_{\{\|y\|_*\leq1\}}(y)$ .
Для $f(x)=\lambda\|x\|$ радиус двойственного шара равен $\lambda$ .

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

Двойственность Фенхеля — Рокафеллара

Для собственных замкнутых выпуклых функций $f$ и $g$ и линейного оператора $A$ рассмотрим

$\inf_x\{f(x)+g(Ax)\}.$

Используя представление $g(Ax)=\sup_y\{\langle y,Ax\rangle-g^*(y)\}$ , получают двойственную задачу

$\sup_y\{-f^*(-A^Ty)-g^*(y)\}.$

Слабая двойственность следует из неравенства Фенхеля — Юнга. В конечномерном пространстве достаточным условием сильной двойственности и достижения двойственного максимума является

$\operatorname{ri}(A\,\operatorname{dom}f)\cap\operatorname{ri}(\operatorname{dom}g)\ne\emptyset,$

либо более сильное условие: существует $x_0\in\operatorname{dom}f$ , в точке $Ax_0$ функция $g$ конечна и непрерывна. Здесь $\operatorname{ri}$ — относительная внутренность. Условия оптимальности имеют вид

$-A^Ty^*\in\partial f(x^*),\qquad y^*\in\partial g(Ax^*).$

Это двойственность Фенхеля: она строится из сопряжённых функций и композиции с линейным оператором. Лагранжева двойственность строится путём дуализации ограничений. Они приводят к эквивалентным парам после кодирования ограничений индикаторами, но исходные конструкции и регулярностные условия различны.

Функция возмущений

Наиболее общий язык связывает обе конструкции. Пусть $F(x,u)$ — выпуклая функция прямой переменной и параметра возмущения, а

$p(u)=\inf_x F(x,u).$

Прямая задача имеет значение $p(0)$ . Двойственная функция получается сопряжением по параметру:

$d(y)=-F^*(0,y),\qquad d^*=\sup_y d(y)=p^{**}(0).$

Поэтому разрыв двойственности — различие между функцией значения и её замкнутой выпуклой оболочкой в нуле. Сильная двойственность есть локальная замкнутость функции значения; существование двойственного решения связано с существованием опорной гиперплоскости, то есть непустотой $\partial p(0)$ . Эта формулировка особенно важна в бесконечномерных пространствах, где конечномерные условия внутренности часто пусты.

Седловые задачи и минимакс

Лагранжиан выпуклой задачи выпукл по $x$ и вогнут по двойственным переменным. Пара $(x^*,\lambda^*,\nu^*)$ является седловой, если

$L(x^*,\lambda,\nu)\leq L(x^*,\lambda^*,\nu^*)\leq L(x,\lambda^*,\nu^*)$

для всех допустимых аргументов. Тогда

$\inf_x\sup_{\lambda\geq0,\nu}L(x,\lambda,\nu)=\sup_{\lambda\geq0,\nu}\inf_xL(x,\lambda,\nu).$

Левая часть кодирует прямую задачу, правая — двойственную. Для произвольной функции всегда верно минимаксное неравенство

$\sup_y\inf_x\Phi(x,y)\leq\inf_x\sup_y\Phi(x,y),$

но перестановка $\inf$ и $\sup$ требует условий минимаксной теоремы: например, выпуклости-вогнутости, полунепрерывности и компактности одной из областей в теореме Сиона. Седловая формулировка — задача сама по себе; наличие выпукло-вогнутой структуры не гарантирует автоматически достижение седловой точки.

Построение двойственной задачи

Практическая схема

Привести прямую задачу к однозначной конвенции: минимизация, неравенства $f_i(x)\leq0$ , равенства $h_j(x)=0$ .
Включить область определения в $D$ или записать её индикатором; не дуализировать ограничения, которые удобнее оставить явными.
Ввести $\lambda_i\geq0$ для каждого неравенства и свободный $\nu_j$ для каждого равенства.
Составить $L$ , аккуратно сгруппировать коэффициенты при прямых переменных.
Вычислить инфимум по всем прямым переменным. Если инфимум равен $-\infty$ вне некоторого множества множителей, это множество становится двойственными ограничениями.
Максимизировать полученную вогнутую функцию по двойственно допустимым множителям.
Отдельно проверить сильную двойственность, достижение оптимумов и возможность восстановления прямого решения. Сам вывод двойственной задачи их не доказывает.

Выбор дуализируемых ограничений не единственен. Частичная двойственность оставляет часть простых ограничений в области инфимума. Это может дать более сильную оценку и более удобную декомпозицию. Расширенный лагранжиан добавляет квадратичный штраф за нарушение равенств; его двойственная функция отличается от обычной, хотя оптимальные множители при подходящих условиях совпадают.

Интерпретация множителей

Геометрически множители — компоненты нормали к опорной гиперплоскости множества возмущений.
Аналитически они взвешивают нарушение ограничений и являются субградиентами функции оптимального значения.
Экономически они измеряют предельную стоимость ресурса.
Алгоритмически они аккумулируют нарушение ограничений; двойственный подъём увеличивает цену систематически нарушаемого ограничения.
В распределённых задачах множители согласования играют роль цен, посредством которых узлы достигают консенсуса без передачи всех локальных данных.

Масштаб множителя зависит от масштаба ограничения. Замена $f_i(x)\leq0$ на $c f_i(x)\leq0$ при $c>0$ делит соответствующий оптимальный множитель на $c$ , не меняя экономического произведения «цена на единицу исходного ресурса».

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

Выпуклые задачи и условие Слейтера

Задача называется выпуклой, если $f_0,f_1,\ldots,f_m$ выпуклы, равенства аффинны, а область $D$ выпукла. Обозначим через $\mathcal I$ множество индексов неаффинных ограничений-неравенств. Условие Слейтера требует существования точки $\bar x\in\operatorname{ri}D$ , для которой

$f_i(\bar x)<0\quad(i\in\mathcal I),\qquad f_i(\bar x)\leq0\quad(i\notin\mathcal I),\qquad h_j(\bar x)=0\quad(j=1,\ldots,r).$

Аффинные неравенства достаточно удовлетворить нестрого; корректная формулировка использует относительную внутренность области с учётом аффинных ограничений. Если оптимальное значение конечно и условие Слейтера выполнено, то $d^*=p^*$ , а двойственный максимум достигается.^[1] Условие Слейтера достаточно, но вообще не необходимо.

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

Условия Каруша — Куна — Таккера

Для дифференцируемой задачи Условия Каруша — Куна — Таккера состоят из:

прямой допустимости

$f_i(x^*)\leq0,\qquad h_j(x^*)=0;$

двойственной допустимости

$\lambda_i^*\geq0;$

дополняющей нежёсткости

$\lambda_i^*f_i(x^*)=0;$

стационарности

$\nabla f_0(x^*)+\sum_i\lambda_i^*\nabla f_i(x^*)+\sum_j\nu_j^*\nabla h_j(x^*)=0.$

В негладком выпуклом случае стационарность заменяется включением

$0\in\partial f_0(x^*)+\sum_i\lambda_i^*\partial f_i(x^*)+\sum_j\nu_j^*\partial h_j(x^*)+N_D(x^*),$

где $N_D$ — Нормальный конус. Точная формула суммы субдифференциалов требует соответствующей квалификации; безопасная исходная запись — $0\in\partial_x L(x^*,\lambda^*,\nu^*)+N_D(x^*)$ .

В выпуклой задаче любая точка, удовлетворяющая KKT, глобально оптимальна, а соответствующие множители двойственно оптимальны: это достаточность, не требующая Слейтера. Если дополнительно выполнено условие Слейтера и оптимум достигается, KKT также необходимы. В невыпуклой задаче KKT при квалификации ограничений обычно необходимы лишь для локального минимума и не гарантируют ни глобальной оптимальности, ни нулевого разрыва.^[1]

Квалификации ограничений

Квалификация ограничений исключает вырожденные описания допустимого множества и позволяет нормализовать условия Фрица Джона так, чтобы множитель при целевой функции был ненулевым. Распространённые варианты:

LICQ: градиенты активных неравенств и равенств линейно независимы.
MFCQ: градиенты равенств независимы и существует направление, строго уменьшающее все активные неравенства при сохранении равенств в первом порядке.
CRCQ и CPLD: более слабые условия постоянного ранга или положительной линейной зависимости.
Условие Слейтера: глобальная выпуклая квалификация, ориентированная на сильную двойственность.
Условие относительной внутренности в теореме Фенхеля — Рокафеллара: квалификация для суммы и линейной композиции выпуклых функций.

LICQ влечёт MFCQ, а MFCQ влечёт существование KKT-множителей в гладкой конечномерной задаче, но обратные импликации вообще неверны. Наличие KKT-множителя в одной точке слабее сильной двойственности всей задачи. Смешение этих утверждений — частая логическая ошибка.

Линейное программирование

Для пары в стандартной форме

$\min_{x\geq0}\{c^Tx:\ Ax\geq b\}$

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

$\max_{y\geq0}\{b^Ty:\ A^Ty\leq c\}.$

Слабая двойственность непосредственно следует из $b^Ty\leq y^TAx\leq c^Tx$ . Теорема сильной двойственности линейного программирования утверждает: если одна задача имеет конечный оптимум, то другая также имеет оптимум и значения равны. Если прямая неограниченна, двойственная несовместна; несовместность прямой сама по себе не определяет, будет ли двойственная несовместна или неограниченна. Дополняющая нежёсткость принимает вид

$y_i(Ax-b)_i=0,\qquad x_j(c-A^Ty)_j=0.$

ЛП-двойственность является частным случаем лагранжевой и конической двойственности. Её особенность — симметричная табличная структура и полиэдральная геометрия; строгая выпуклость отсутствует, поэтому оптимизаторы могут быть неединственны.

Коническая форма

Многие задачи удобно писать как

$\inf_x\{\langle c,x\rangle:\ Ax-b\in K\},$

где $K$ — замкнутый выпуклый конус. Двойственный конус

$K^*=\{y:\ \langle y,z\rangle\geq0\quad\forall z\in K\}$

даёт двойственную задачу с условием $y\in K^*$ и линейным равенством, возникающим после инфимизации по $x$ . Выбор ортанта даёт ЛП, конуса Лоренца — Коническое программирование второго порядка, конуса положительно полуопределённых матриц — Полуопределённое программирование. Для общих конических задач сильная двойственность также требует регулярности; даже при конечных значениях достижение может отсутствовать.

Частные случаи

Квадратичное программирование

Рассмотрим выпуклую квадратичную задачу

$\inf_x\left\{\frac12x^TQx+c^Tx:\ Ax=b\right\},\qquad Q\succeq0.$

Лагранжиан равен $\frac12x^TQx+c^Tx+\nu^T(Ax-b)$ . Если $Q\succ0$ , минимум по $x$ достигается при

$x(\nu)=-Q^{-1}(c+A^T\nu),$

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

$\sup_\nu\left\{-\frac12(c+A^T\nu)^TQ^{-1}(c+A^T\nu)-b^T\nu\right\}.$

При сингулярной $Q$ следует использовать псевдообратную и дополнительное условие $c+A^T\nu\in\operatorname{range}Q$ ; механическая запись $Q^{-1}$ ошибочна. Неравенства добавляют неотрицательные множители. Для невыпуклого $Q$ двойственная функция остаётся вогнутой, но инфимум часто равен $-\infty$ и разрыв может быть положительным.

Задачи на нормы

Двойственность норм следует из формулы

$\|x\|=\sup_{\|y\|_*\leq1}\langle y,x\rangle.$

Например, задача базисного преследования

$\inf_x\{\|x\|_1:\ Ax=b\}$

имеет двойственную

$\sup_y\{b^Ty:\ \|A^Ty\|_\infty\leq1\}.$

Двойственно допустимый $y$ , для которого $(A^Ty)_j=\operatorname{sign}(x_j)$ на носителе $x$ и модуль строго меньше единицы вне носителя, служит сертификатом оптимальности и, при дополнительных условиях, единственности разреженного решения. Аналогично сопряжённость ядерной и спектральной норм используется в задачах низкого ранга.

Регуляризованный эмпирический риск

Общий шаблон линейного предиктора:

$\inf_w\left\{P(w)=\frac1n\sum_{i=1}^n\phi_i(a_i^Tw)+\lambda R(w)\right\},$

где потери $\phi_i$ и регуляризатор $R$ — собственные замкнутые выпуклые функции, $\lambda>0$ . Введя $z=Aw$ и применив двойственность Фенхеля, получаем

$\sup_\alpha\left\{D(\alpha)=-\frac1n\sum_{i=1}^n\phi_i^*(-\alpha_i)-\lambda R^*\left(\frac{A^T\alpha}{\lambda n}\right)\right\}.$

Знаки могут быть заменены переобозначением $\alpha$ . При $R(w)=\frac12\|w\|_2^2$

$D(\alpha)=-\frac1n\sum_i\phi_i^*(-\alpha_i)-\frac{1}{2\lambda n^2}\|A^T\alpha\|_2^2,$

а прямой вектор восстанавливается как

$w(\alpha)=\frac{1}{\lambda n}A^T\alpha.$

Это базовая форма для SDCA. При $\lambda$ -сильной выпуклости регуляризатора двойственная задача часто гладкая в связанных направлениях, а разрыв $P(w)-D(\alpha)$ даёт критерий остановки.^[1]

Применения в машинном обучении

Метод опорных векторов

Мягко-разделяющий линейный SVM в прямой форме:

$\inf_{w,b,\xi}\left\{\frac12\|w\|_2^2+C\sum_{i=1}^n\xi_i:\ y_i(w^Tx_i+b)\geq1-\xi_i,\ \xi_i\geq0\right\}.$

После введения множителей и инфимизации по $w,b,\xi$ получается

$\sup_\alpha\left\{\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j:\ 0\leq\alpha_i\leq C,\ \sum_i\alpha_i y_i=0\right\}.$

Стационарность даёт $w^*=\sum_i\alpha_i^*y_ix_i$ . Ненулевые $\alpha_i$ отмечают опорные векторы, а дополняющая нежёсткость связывает их с точками на полосе или внутри неё. Замена скалярных произведений ядром $k(x_i,x_j)$ даёт ядерный SVM без явного построения признакового пространства. Двойственная задача особенно выгодна, когда число объектов умеренно, пространство признаков очень велико или доступно только ядро; при огромном числе объектов и сравнительно малой размерности прямая линейная постановка обычно дешевле.

Логистическая регрессия

Для логистической потери $\phi(t)=\log(1+\exp(-t))$ сопряжённая конечна на интервале $[-1,0]$ :

$\phi^*(u)=(-u)\log(-u)+(1+u)\log(1+u),\qquad -1\leq u\leq0.$

Поэтому двойственные переменные регуляризованной логистической регрессии имеют интервальные ограничения, а двойственная целевая функция содержит отрицательную бинарную энтропию. В отличие от hinge-потери SVM, логистическая потеря гладкая и её сопряжённая строго выпукла внутри области. Двойственная координатная оптимизация полезна при разреженной матрице признаков и позволяет поддерживать $A^T\alpha$ инкрементально; методы Ньютона по прямой задаче часто предпочтительнее при умеренной размерности и хорошо обусловленной плотной матрице.

Разреженность и регуляризация

В лассо

$\inf_w\left\{\frac12\|Aw-b\|_2^2+\lambda\|w\|_1\right\}$

двойственная задача может быть записана как

$\sup_\theta\left\{-\frac12\|\theta\|_2^2-b^T\theta:\ \|A^T\theta\|_\infty\leq\lambda\right\}.$

При иной замене переменной встречается эквивалентная форма проекции $b$ на множество $\{u:\|A^Tu\|_\infty\leq\lambda\}$ . KKT связывают остаток с двойственной переменной и дают правила безопасного исключения признаков: если верхняя оценка на $|a_j^T\theta^*|$ строго меньше $\lambda$ , то $w_j^*=0$ . Современные Gap Safe-правила строят область, гарантированно содержащую двойственный оптимум, по текущему разрыву двойственности; это даёт безопасное, а не эвристическое, сокращение признаков.^[1]

Та же геометрия действует для группового лассо, ядерной нормы и структурированных штрафов: форма единичного шара двойственной нормы определяет двойственно допустимое множество и сертификат зануления блока.

Максимальная энтропия и экспоненциальные семейства

Задача максимизации энтропии распределения при линейных моментных ограничениях имеет вид

$\sup_{p\in\Delta}\left\{-\sum_xp(x)\log p(x):\ \sum_xp(x)\phi(x)=\mu\right\}.$

Стационарность Лагранжиана даёт экспоненциальное семейство

$p_\theta(x)=\exp\{\langle\theta,\phi(x)\rangle-A(\theta)\},\qquad A(\theta)=\log\sum_x\exp\langle\theta,\phi(x)\rangle.$

Двойственная задача минимизирует $A(\theta)-\langle\theta,\mu\rangle$ . Логарифм статистической суммы и отрицательная энтропия сопряжены; градиент $\nabla A$ отображает естественные параметры в средние. Эта двойственность лежит в основе моделей максимальной энтропии, условных случайных полей и геометрии экспоненциальных семейств.

Вариационный вывод

Для вероятностной меры $P$ и измеримой функции $f$ , для которой экспоненциальный момент конечен, вариационная формула Гиббса — Донскера — Варадана утверждает

$\log\mathbb E_P\exp f=\sup_{Q\ll P}\{\mathbb E_Q f-\operatorname{KL}(Q\|P)\}.$

Это сопряжённость логарифмического функционала момента и KL-дивергенции. Подстановка $f=\log p(x,z)-\log q(z)$ приводит к нижней вариационной оценке

$\log p(x)\geq\mathbb E_q\log p(x,z)-\mathbb E_q\log q(z)=\operatorname{ELBO}(q).$

Разрыв равен $\operatorname{KL}(q(z)\|p(z\mid x))$ . Здесь слово «двойственность» относится к вариационному сопряжению функционалов; ограничение семейства $q$ создаёт аппроксимационный разрыв, который не следует путать с лагранжевым разрывом исходной конечномерной задачи. Вариационные представления $f$ -дивергенций аналогично используются при оценивании отношений плотностей и обучении генеративных моделей.^[1]

Распределённая оптимизация

Для суммы локальных функций вводят копии параметра и ограничения согласования:

$\inf_{x_1,\ldots,x_K,z}\sum_{k=1}^K f_k(x_k),\qquad x_k=z.$

Множители ограничений разделяют вычисления по узлам. Двойственный субградиентный метод обновляет цены согласования; ADMM применяет попеременную минимизацию расширенного лагранжиана и двойственное обновление. Для замкнутых собственных выпуклых функций и существующей седловой точки классический двухблочный ADMM сходится при стандартных условиях; для произвольного многоблочного параллельного варианта сходимость без модификаций не гарантирована.^[1]

В распределённом ERM двойственные координаты естественно привязаны к объектам, а общая величина $A^T\alpha$ агрегируется между узлами. Это уменьшает передачу исходных данных, но не устраняет стоимость синхронизации и может быть невыгодно при сильной связанности двойственной квадратичной части.

Первично-двойственные алгоритмы

Задача $\min_x f(x)+g(Ax)$ эквивалентна седловой

$\min_x\max_y\{f(x)+\langle Ax,y\rangle-g^*(y)\}.$

Методы PDHG и Шамболя — Пока выполняют проксимальные шаги по $f$ и $g^*$ . В базовой евклидовой версии достаточное условие выбора постоянных шагов имеет вид

$\tau\sigma\|A\|^2<1.$

При общей выпуклости усреднённый первично-двойственный разрыв убывает как $O(1/k)$ на ограниченных тестовых множествах; сильная выпуклость позволяет ускорение при дополнительных предпосылках.^[1] Стохастические и координатные варианты используют разложимость по двойственным блокам; их оценки зависят от схемы выборки, гладкости и сильной выпуклости, поэтому перенос скорости одной версии на другую без проверки условий неправомерен.^[1]

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

Подход	Исходная форма и предпосылки	Геометрия	Результат и типичные применения
Лагранжева двойственность	Ограниченная задача; слабая двойственность без выпуклости, сильная — при выпуклости и квалификации либо в специальных невыпуклых классах	Опорные гиперплоскости множества возмущений; цены ограничений	Нижние оценки, KKT, чувствительность, декомпозиция, SVM, конические релаксации
Двойственность Фенхеля — Рокафеллара	Сумма собственных выпуклых функций и линейная композиция; замкнутость и условие относительной внутренности для сильной двойственности	Сопряжённые эпиграфы, субградиентные обратные соответствия	Композитная и негладкая оптимизация, нормы, ERM, проксимальные методы
Двойственность ЛП	Линейная цель и полиэдральные ограничения	Полярность конусов и полиэдров, лемма Фаркаша	Точная симметричная пара при конечном оптимуме; потоки, назначения, сертификаты несовместности
Седловая формулировка	Выпукло-вогнутая функция; для равенства минимакса нужны топологические условия	Пересечение монотонных операторов; равновесие двух игроков	Одновременное обновление прямых и двойственных переменных, PDHG, mirror-prox, состязательное обучение

С вычислительной точки зрения ни одна форма не доминирует. Лагранжева двойственная функция может требовать решения трудной внутренней задачи; сопряжённая функция может не иметь замкнутой формулы; ЛП-двойственная имеет сопоставимый размер; седловый метод может страдать от колебаний простого градиентного спуска-подъёма. Выбор определяется размерностями, разреженностью, доступностью проксимальных операторов, обусловленностью и требуемым сертификатом.

Когда двойственная задача предпочтительнее

Двойственную постановку практически выгодно решать, если выполняется хотя бы одна структурная причина:

двойственных переменных существенно меньше, чем прямых;
двойственная задача разлагается по объектам, ограничениям или вычислительным узлам;
сопряжение превращает негладкий штраф в простое ограничение или, наоборот, сложное ограничение в простой штраф;
требуется ядерный трюк и решение представимо через скалярные произведения обучающих объектов;
двойственные координатные шаги имеют дешёвую замкнутую форму и можно инкрементально поддерживать прямой вектор;
необходимы гарантированные нижние оценки, критерий остановки, safe screening или сертификат несовместности;
прямое восстановление из двойственного решения устойчиво и однозначно, например из-за сильной выпуклости прямой цели.

Двойственный подход может быть хуже, если двойственная размерность равна числу объектов при огромной выборке, матрица Грама плотна, сопряжённые функции дороги, двойственная задача плохо обусловлена или прямое решение нельзя устойчиво восстановить. Нулевой разрыв значений не означает численной эквивалентности алгоритмов.

Ограничения и типичные ошибки

Ограничения теории

В невыпуклой оптимизации двойственная задача обычно описывает выпуклую релаксацию и может иметь положительный разрыв. Хорошая двойственная нижняя оценка не обязательно даёт хорошее прямое решение.
Сильная двойственность может нарушаться даже у выпуклой задачи без замкнутости или квалификации. В бесконечномерных пространствах топология и выбор непрерывного двойственного пространства существенны.
Равенство оптимальных значений не гарантирует достижения ни прямого, ни двойственного оптимума.
Единственность прямого решения не влечёт единственности множителей и наоборот.
Численно малый вычисленный разрыв является сертификатом только для действительно прямого и двойственно допустимого решения и корректно вычисленных целевых значений.
Для невыпуклых нейронных сетей лагранжевые методы ограничений полезны алгоритмически, но стандартная теорема Слейтера для выпуклых задач неприменима. Стационарная седловая точка не равна глобальному решению.

Существуют специальные невыпуклые классы с сильной двойственностью: некоторые квадратичные задачи по S-лемме, задачи с временным разделением, скрытой выпуклостью или выпуклой рандомизацией. Это отдельные теоремы с конкретными предпосылками, а не следствие общей лагранжевой конструкции. Новые работы также изучают двойственно допустимые обучаемые прокси для параметрических конических задач: их ценность состоит в гарантированной оценке при сохранении двойственной допустимости, но качество прямого восстановления и обобщение на новые параметры требуют отдельного анализа.^[1]

Ошибки при выводе

Неверный знак множителя: для минимизации и ограничения $f_i\leq0$ нужен $\lambda_i\geq0$ .
Ограничение знака множителя равенства: такой множитель свободен.
Минимизация Лагранжиана только по допустимым относительно уже дуализированных ограничений переменным. После дуализации эти ограничения должны быть сняты; остаются лишь явно недуализированные ограничения и область определения.
Замена $\inf$ стационарной точкой без проверки ограниченности снизу. Условие градиента необходимо не всегда и недостаточно при невыпуклой зависимости.
Игнорирование области сопряжённой функции; именно она часто порождает ключевые двойственные ограничения.
Утверждение сильной двойственности только на основании выпуклости. Нужны замкнутость и подходящая квалификация либо специальная теорема.
Утверждение, что KKT всегда необходимы и достаточны. Необходимость требует квалификации, достаточность глобального минимума — выпуклости.
Подмена дополняющей нежёсткости двусторонней эквивалентностью: из $\lambda_i^*>0$ следует активность ограничения, но активность не обязана означать положительный множитель.
Потеря коэффициентов нормировки $1/n$ и параметра регуляризации при выводе двойственной ERM-задачи.
Смешение лагранжева разрыва, фенхелева разрыва, вариационного аппроксимационного разрыва и ошибки алгоритма. Иногда они численно совпадают, но это требует доказанного соответствия постановок.

Классические результаты и современные алгоритмические направления

К классическому ядру относятся лемма Фаркаша и двойственность ЛП; преобразование Фенхеля — Лежандра и теорема Фенхеля — Моро; условия Каруша — Куна — Таккера; условие Слейтера; теория возмущений и седловых функций Рокафеллара. Эти результаты устанавливают существование оценок, отсутствие разрыва и условия оптимальности.

Современные работы преимущественно не заменяют классические теоремы, а строят на них масштабируемые методы и более точные сертификаты:

стохастический и ускоренный двойственный координатный подъём для регуляризованного ERM;
первично-двойственные проксимальные алгоритмы, адаптивные шаги, диагональное предобусловливание и случайная выборка блоков;
безопасное исключение признаков и рабочих множеств по локализованным двойственным областям;
распределённые двойственные и расширенно-лагранжевы методы;
вариационные представления дивергенций, оптимального транспорта и робастных рисков;
дифференцируемые оптимизационные слои и обучение допустимых двойственных сертификатов;
последовательные приближённые KKT-условия для невыпуклых алгоритмов, где предельные множители могут не существовать без дополнительной регулярности.

Для регуляризованного ERM первично-двойственные сертификаты позволяют переносить скорость конкретного прямого или двойственного алгоритма на вычислимый разрыв при проверяемых условиях гладкости и сильной выпуклости.^[1] Для стохастических первично-двойственных методов ERM сложность зависит не только от числа объектов и признаков, но и от спектра матрицы данных и выбранной блочной выборки.^[1] Поэтому термин «двойственный метод» обозначает семейство алгоритмов, а не одну универсальную оценку сложности.

См. также

Примечания

Литература

Rockafellar R. T. Convex Analysis. — Princeton: Princeton University Press, 1970. — 451 с.
Rockafellar R. T.; Wets R. J.-B. Variational Analysis. — Berlin: Springer, 1998. — 733 с.
Borwein J. M.; Lewis A. S. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — New York: Springer, 2006.
Boyd S.; Vandenberghe L. Convex Optimization. — Cambridge: Cambridge University Press, 2004. — 716 с.
Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course. — New York: Springer, 2004.
Bauschke H. H.; Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. — 2. — Cham: Springer, 2017.
Slater M. Lagrange Multipliers Revisited // Cowles Foundation Discussion Paper. — 1959. — № 80. — С. 1—13.
Kuhn H. W.; Tucker A. W. Nonlinear Programming // Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. — Berkeley, 1951. — С. 481—492.
Chambolle A.; Pock T. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging // Journal of Mathematical Imaging and Vision. — 2011. — Т. 40. — № 1. — С. 120—145.
Shalev-Shwartz S.; Zhang T. Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization // Journal of Machine Learning Research. — 2013. — Т. 14. — С. 567—599.
Boyd S.; Parikh N.; Chu E.; Peleato B.; Eckstein J. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers // Foundations and Trends in Machine Learning. — 2011. — Т. 3. — № 1. — С. 1—122.
Ndiaye E.; Fercoq O.; Gramfort A.; Salmon J. Gap Safe Screening Rules for Sparsity Enforcing Penalties // Journal of Machine Learning Research. — 2017. — Т. 18. — № 128. — С. 1—33.
Boyd S.; Vandenberghe L. Duality2023.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%28%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F%29»

Категории: Оптимизация | Машинное обучение | Энциклопедия анализа данных | Выпуклый анализ | Математическое программирование