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

В математической теории оптимизации двойственность или принцип двойственности - это принцип, согласно которому проблемы оптимизации могут рассматриваться с одной из двух точек зрения: с основной проблемы или с двойственной проблемы . Решение двойственной задачи дает нижнюю оценку решения прямой (минимизационной) задачи. ^[1] Однако в целом оптимальные значения прямой и двойственной задач не обязательно должны быть равны. Их различие называется разрывом дуальности . Для задач выпуклой оптимизации разрыв двойственности равен нулю при условии квалификационного ограничения .

Двойная проблема [ править ]

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

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

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

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

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

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

Разрыв дуальности [ править ]

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

При вычислительной оптимизации часто сообщается о другом «пробеле двойственности», который представляет собой разницу в значении между любым двойным решением и значением допустимой, но неоптимальной итерации для основной задачи. Этот альтернативный «разрыв двойственности» количественно определяет несоответствие между значением текущей допустимой, но неоптимальной итерации для основной задачи и значением двойственной задачи; значение двойственной задачи при условиях регулярности равно значению выпуклой релаксации прямой задачи: выпуклая релаксация - это проблема, возникающая при замене невыпуклого допустимого множества его замкнутой выпуклой оболочкой и заменой невыпуклого допустимого множества его замкнутой выпуклой оболочкой. выпуклая функция с ее выпуклым замыканием , то есть функция, имеющая надграфикэто замкнутая выпуклая оболочка исходной прямой целевой функции. ^{[6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] »}

Линейный регистр [ править ]

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

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

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

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

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

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

Нелинейный случай [ править ]

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

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

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

Сильный принцип Лагранжа: двойственность Лагранжа [ редактировать ]

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\Lambda (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 является вогнутой, даже если исходная задача не является выпуклой, потому что это точная нижняя грань аффинных функций. Двойственная функция дает нижние оценки оптимального значения исходной задачи; для любого и любого, что у нас есть .${\displaystyle p^{*}}$${\displaystyle \lambda \geq 0}$${\displaystyle \nu }$${\displaystyle g(\lambda ,\nu )\leq p^{*}}$

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

Выпуклые задачи [ править ]

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

История [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

Книги [ править ]

• Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл. ISBN 0-13-617549-X.
• Бертсекас, Дмитрий; Недич, Анджелиа; Оздаглар, Асуман (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. DOI : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. Руководство по ремонту  2265882 .
• Кук, Уильям Дж .; Каннингем, Уильям Х .; Pulleyblank, Уильям Р .; Шрайвер, Александр (12 ноября 1997 г.). Комбинаторная оптимизация (1-е изд.). Джон Вили и сыновья. ISBN 0-471-55894-X.
• Данциг, Джордж Б. (1963). Линейное программирование и расширения . Принстон, Нью-Джерси: Издательство Принстонского университета.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 305 . Берлин: Springer-Verlag. С. xviii + 417. ISBN 3-540-56850-6. Руководство по ремонту  1261420 .
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «14 двойственности для практикующих». Выпуклый анализ и алгоритмы минимизации, Том II: Расширенная теория и методы связки . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 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). «Лагранжева релаксация». В Юнгере, Михаэль; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: документы из Весенней школы состоялись в Шлоссе Dagstuhl, 15-19 мая 2000 года . Конспект лекций по информатике (LNCS). 2241 . Берлин: Springer-Verlag. С. 112–156. DOI : 10.1007 / 3-540-45586-8_4 . ISBN 3-540-42877-1. MR  1900016 .
• Мину, Мишель (1986). Математическое программирование: теория и алгоритмы . Эгон Балас (нападающий); Стивен Вайда (транс) из французского (1983 Paris: Dunod). Чичестер: публикация Wiley-Interscience. John Wiley & Sons, Ltd., стр. Xxviii + 489. ISBN 0-471-90170-9. Руководство по ремонту  0868279 . (Второе изд., 2008 г., на французском языке: Математическое программирование: Теория и алгоритмы , Éditions Tec & Doc, Париж, 2008. xxx + 711 стр.)).
• Nering, Evar D .; Такер, Альберт В. (1993). Линейное программирование и связанные с ним проблемы . Бостон, Массачусетс: Academic Press. ISBN 978-0-12-515440-6.
• Papadimitriou, Christos H .; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность (Несокращенная ред.). Дувр. ISBN 0-486-40258-4.
• Рущинский, Анджей (2006). Нелинейная оптимизация . Принстон, Нью-Джерси: Издательство Принстонского университета . С. xii + 454. ISBN 978-0691119151. Руководство по ремонту  2199043 .

Статьи [ править ]

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