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

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

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

Двойная проблема

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

В общем случае даны две двойственные пары разделенных . локально выпуклых пространств $\left(X,X^{*}\right)$ и $\left(Y,Y^{*}\right)$ и функция $f:X\to \mathbb {R} \cup \{+\infty \}$, мы можем определить основную проблему как поиск ${\hat {x}}$ такой, что $f({\hat {x}})=\inf _{x\in X}f(x).\,$Другими словами, если ${\hat {x}}$ существует, $f({\hat {x}})$ является минимумом функции $f$ и достигается нижняя грань (наибольшая нижняя граница) функции.

Если существуют условия ограничения, их можно встроить в функцию $f$ позволяя ${\tilde {f}}=f+I_{\mathrm {constraints} }$ где $I_{\mathrm {constraints} }$ является подходящей функцией на $X$ который имеет минимум 0 на ограничениях и для которого можно доказать, что $\inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {constrained} }f(x)$. Последнее условие тривиально, но не всегда удобно, выполняется для характеристической функции (т. е. $I_{\mathrm {constraints} }(x)=0$ для $x$ удовлетворение ограничений и $I_{\mathrm {constraints} }(x)=\infty$ в противном случае). Затем продлите ${\tilde {f}}$ к функции возмущения $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ такой, что $F(x,0)={\tilde {f}}(x)$.

— Разрыв двойственности это разница правой и левой частей неравенства.

$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,$

где $F^{*}$ является выпуклым сопряжением по обеим переменным и $\sup$ обозначает супремум (минимальную верхнюю границу).

Разрыв двойственности

Основная статья: Разрыв двойственности

Разрыв двойственности — это разница между значениями любых первичных решений и любых двойственных решений. Если $d^{*}$ является оптимальным двойным значением и $p^{*}$ – оптимальное простое значение, то разрыв двойственности равен $p^{*}-d^{*}$. Это значение всегда больше или равно 0 (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность . В противном случае разрыв строго положителен и сохраняется слабая двойственность .

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

Линейный случай

Основная статья: Двойная линейная программа

линейного программирования Задачи — это задачи оптимизации в которых целевая функция и ограничения линейны , . В основной задаче целевая функция представляет собой линейную комбинацию n переменных. Существует m ограничений, каждое из которых накладывает верхнюю границу на линейную комбинацию n переменных. Цель состоит в том, чтобы максимизировать значение целевой функции с учетом ограничений. Решение значений представляет собой вектор (список) из n , который достигает максимального значения целевой функции.

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

Связь между первичной проблемой и двойной проблемой

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

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

Эта интуиция формализована уравнениями в книге « Линейное программирование: двойственность» .

Нелинейный случай

В нелинейном программировании ограничения не обязательно линейны. Тем не менее, применяются многие из тех же принципов.

Чтобы гарантировать, что глобальный максимум нелинейной задачи можно легко определить, формулировка задачи часто требует, чтобы функции были выпуклыми и имели компактные множества нижнего уровня. В этом смысл условий Каруша-Куна-Таккера . Они обеспечивают необходимые условия для выявления локальных оптимумов задач нелинейного программирования. Существуют дополнительные условия (ограничения), необходимые для того, чтобы можно было определить направление к оптимальному решению. Оптимальное решение — это решение, которое является локальным оптимумом, но, возможно, не является глобальным оптимумом.

Двойственность Лагранжа

Мотивация . Предположим, мы хотим решить следующую задачу нелинейного программирования :

${\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}$

Проблема имеет ограничения; мы хотели бы преобразовать его в программу без ограничений. Теоретически это можно сделать, минимизировав функцию J ( x ), определяемую как

$J(x)=f_{0}(x)+\sum _{i}I[f_{i}(x)]$

где I — функция бесконечного шага : I[u]=0, если u≤0, и I[u]=∞ в противном случае. Но J ( x ) трудно решить, поскольку он не является непрерывным. Можно «приблизить» I[u] величиной λu , где λ — положительная константа. Это дает функцию, известную как лагранжиан:

$L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)$

Обратите внимание, что для x каждого

$\max _{\lambda \geq 0}L(x,\lambda )=J(x)$.

Доказательство :

• Если x удовлетворяет всем ограничениям f _i ( x )≤0, то L( x , λ ) максимизируется при принятии λ =0, и тогда его значение равно f(x);
• Если x нарушает какое-то ограничение, fi _λ ( x )>0 для некоторого i , то L(x, λ )→∞, когда i _→ ∞ .

Следовательно, исходная задача эквивалентна:

$\min _{x}\max _{\lambda \geq 0}L(x,\lambda )$.

Меняя порядок минимумов и максимумов, мы получаем:

$\max _{\lambda \geq 0}\min _{x}L(x,\lambda )$.

Двойная функция — это внутренняя проблема в приведенной выше формуле:

$g(\lambda ):=\min _{x}L(x,\lambda )$.

Лагранжева двойственная программа — это программа максимизации g:

$\max _{\lambda \geq 0}g(\lambda )$.

Оптимальное решение двойственной программы — это нижняя граница оптимального решения исходной (основной) программы; это слабый принцип двойственности . Если основная задача выпукла и ограничена снизу и существует точка, в которой строго выполняются все нелинейные ограничения ( условие Слейтера ), то оптимальное решение двойственной программы равно оптимальному решению основной программы; это сильный принцип двойственности . В этом случае мы можем решить основную программу, найдя оптимальное решение λ * двойственной программы, а затем решив:

$\min _{x}L(x,\lambda ^{*})$.

Обратите внимание: чтобы использовать слабый или сильный принцип двойственности, нам нужен способ вычисления g( λ ). В общем, это может быть сложно, так как нам нужно решить другую задачу минимизации для каждого λ . Но для некоторых классов функций можно получить явную формулу для g(). Решить первичную и двойственную программы вместе зачастую проще, чем решить только одну из них. Примерами являются линейное программирование и квадратичное программирование . Лучший и более общий подход к двойственности обеспечивает теорема двойственности Фенхеля .

Другое условие, при котором min-max и max-min равны, - это когда лагранжиан имеет седловую точку : (x∗, λ∗) является седловой точкой функции Лагранжа L тогда и только тогда, когда x∗ является оптимальным решением простое число λ∗ является оптимальным решением двойственного, а оптимальные значения в указанных задачах равны между собой.

Сильный принцип Лагранжа

Дана задача нелинейного программирования в стандартной форме.

${\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}$

с доменом ${\mathcal {D}}\subset \mathbb {R} ^{n}$ имея непустую внутренность, функция Лагранжа ${\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ определяется как

${\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).$

Векторы $\lambda$ и $\nu$ называются двойственными переменными или векторами множителей Лагранжа, связанными с задачей. Лагранжа Двойная функция $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ определяется как

$g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left\{f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right\}.$

Двойственная функция g является вогнутой, даже если исходная задача не является выпуклой, поскольку она представляет собой поточечный минимум аффинных функций. Двойственная функция дает нижнюю границу оптимального значения $p^{*}$ исходной проблемы; для любого $\lambda \geq 0$ и любой $\nu$ у нас есть $g(\lambda ,\nu )\leq p^{*}$.

Если выполняется условие ограничения, такое как условие Слейтера , и исходная задача выпукла, то мы имеем сильную двойственность , т. е. $d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$.

Выпуклые задачи

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

${\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}$

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

${\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}$

где целевая функция представляет собой двойственную функцию Лагранжа. При условии, что функции $f$ и $g_{1},\ldots ,g_{m}$ непрерывно дифференцируемы, нижняя грань возникает там, где градиент равен нулю. Проблема

${\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}$

называется двойной проблемой Вульфа . Эту проблему может быть сложно решить вычислительно, поскольку целевая функция не является вогнутой по совместным переменным. $(u,x)$. Кроме того, ограничение равенства $\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)$ в целом нелинейно, поэтому двойственная задача Вульфа обычно представляет собой задачу невыпуклой оптимизации. В любом случае слабая двойственность имеет место.

История

По словам Джорджа Данцига , теорема двойственности для линейной оптимизации была выдвинута Джоном фон Нейманом сразу после того, как Данциг представил задачу линейного программирования. Фон Нейман отметил, что он использовал информацию из своей теории игр , и предположил, что матричная игра для двух человек с нулевой суммой эквивалентна линейному программированию. Строгие доказательства были впервые опубликованы в 1948 году Альбертом Такером и его группой. (Предисловие Данцига к книге «Неринг и Такер», 1993 г.)

Приложения

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

См. также

• Выпуклая двойственность
• Двойственность
• Релаксация (приближение)

Ссылки

Книги

• Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл. ISBN  0-13-617549-Х .
• Берцекас, Дмитрий; Недич, Ангелия; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация . Афина Сайентифик. ISBN  1-886529-45-0 .
• Берцекас, Дмитрий П. (1999). Нелинейное программирование (2-е изд.). Афина Сайентифик. ISBN  1-886529-00-0 .
• Берцекас, Дмитрий П. (2009). Теория выпуклой оптимизации . Афина Сайентифик. ISBN  978-1-886529-31-1 .
• Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006). Численная оптимизация: Теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. дои : 10.1007/978-3-540-35447-5 . ISBN  3-540-35445-Х . МР   2265882 .
• Кук, Уильям Дж .; Каннингем, Уильям Х.; Пуллибланк, Уильям Р .; Шрийвер, Александр (12 ноября 1997 г.). Комбинаторная оптимизация (1-е изд.). Джон Уайли и сыновья. ISBN  0-471-55894-Х .
• Данциг, Джордж Б. (1963). Линейное программирование и расширения . Принстон, Нью-Джерси: Издательство Принстонского университета.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Фундаментальные основы математических наук. Том 305. Берлин: Springer-Verlag. стр. xviii+417. ISBN  3-540-56850-6 . МР   1261420 .
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «14 двойственностей для практикующих». Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы расслоения . Фундаментальные принципы математических наук. Том 306. Берлин: Springer-Verlag. стр. xviii+346. ISBN  3-540-56852-2 . МР   1295240 .
• Ласдон, Леон С. (2002) [Перепечатка Macmillan 1970 года]. Теория оптимизации больших систем . Минеола, Нью-Йорк: Dover Publications, Inc., стр. xiii+523. ISBN  978-0-486-41999-2 . МР   1888251 .
• Лоулер, Юджин (2001). «4.5. Комбинаторные следствия теоремы о минимальном разрезе о максимальном потоке, 4.6. Интерпретация линейного программирования теоремы о минимальном разрезе о максимальном потоке». Комбинаторная оптимизация: сети и матроиды . Дувр. стр. 117–120. ISBN  0-486-41453-1 .
• Лемарешаль, Клод (2001). «Лагранжева релаксация». В Юнгере, Майкл; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, проходившей в замке Дагштуль, 15–19 мая 2000 г. Конспекты лекций по информатике (LNCS). Том. 2241. Берлин: Springer-Verlag. стр. 112–156. дои : 10.1007/3-540-45586-8_4 . ISBN  3-540-42877-1 . МР   1900016 . S2CID   9048698 .
• Мину, Мишель (1986). Математическое программирование: Теория и алгоритмы . Эгон Балас (нападающий); Стивен Вайда (транс) из французского (1983 Париж: Dunod). Чичестер: межнаучная публикация Wiley. John Wiley & Sons, Ltd., стр. xxviii+489. ISBN  0-471-90170-9 . МР   0868279 . (Второе издание 2008 г., на французском языке: Математическое программирование: теория и алгоритмы , Éditions Tec & Doc, Париж, 2008. xxx+711 стр.)).
• Неринг, Эвар Д.; Такер, Альберт В. (1993). Линейное программирование и связанные с ним проблемы . Бостон, Массачусетс: Академическая пресса. ISBN  978-0-12-515440-6 .
• Пападимитриу, Христос Х.; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность (Полное издание). Дувр. ISBN  0-486-40258-4 .
• Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . стр. xii+454. ISBN  978-0-691-11915-1 . МР   2199043 .

Статьи

• Эверетт, Хью III (1963). «Обобщенный метод множителей Лагранжа для решения задач оптимального распределения ресурсов» . Исследование операций . 11 (3): 399–417. дои : 10.1287/опре.11.3.399 . JSTOR   168028 . МР   0152360 . Архивировано из оригинала 24 июля 2011 г.
• Кивиэль, Кшиштоф К.; Ларссон, Торбьёрн; Линдберг, ПО (август 2007 г.). «Лагранжева релаксация с помощью методов шарикового субградиента» . Математика исследования операций . 32 (3): 669–686. дои : 10.1287/moor.1070.0261 . МР   2348241 . Архивировано из оригинала 26 июля 2011 г. Проверено 12 мая 2011 г.
• Двойственность в линейном программировании Гэри Д. Нотт