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

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

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

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

В общем даны два двойные пары из отделенный локально выпуклые пространства ${\displaystyle \left(X,X^{*}\right)}$ и ${\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}$ и инфимум (точная нижняя граница) функции достигается.

Если есть условия ограничения, их можно встроить в функцию ${\displaystyle f}$ позволяя ${\displaystyle {\tilde {f}}=f+I_{\mathrm {constraints} }}$ куда ${\displaystyle I_{\mathrm {constraints} }}$ является подходящей функцией на ${\displaystyle X}$ который имеет минимум 0 на ограничениях, и для которого можно доказать, что ${\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)}$.^[2]

В разрыв дуальности - разность правой и левой частей неравенства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Учитывая нелинейное программирование проблема в стандартной форме

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

Двойная функция грамм является вогнутым, даже если исходная задача не является выпуклой, поскольку это точная нижняя грань аффинных функций. Двойственная функция дает нижние оценки оптимального значения ${\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}}}$

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

История

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

Смотрите также

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

Примечания

1. Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация (pdf). Издательство Кембриджского университета. п. 216. ISBN  978-0-521-83378-3. Получено 15 октября, 2011.
2. Бо, Раду Иоан; Ванка, Герт; Град, Сорин-Михай (2009). Двойственность в векторной оптимизации. Springer. ISBN  978-3-642-02885-4.
3. Четнек, Эрне Роберт (2010). Преодоление несоблюдения классических обобщенных условий регулярности внутренней точки при выпуклой оптимизации. Приложения теории двойственности к расширению максимальных монотонных операторов. Logos Verlag Berlin GmbH. ISBN  978-3-8325-2503-3.
4. Зэлинеску, Константин (2002). Выпуклый анализ в общих векторных пространствах. Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., стр.106 –113. ISBN  981-238-067-1. Г-Н  1921556.
5. Борвейн, Джонатан; Чжу, Цицзи (2005). Методы вариационного анализа. Springer. ISBN  978-1-4419-2026-3.
6. Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения. Прентис Холл. ISBN  0-13-617549-X.
7. Бертсекас, Дмитрий; Недич, Анжелиа; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация. Athena Scientific. ISBN  1-886529-45-0.
8. Бертсекас, Дмитрий П. (1999). Нелинейное программирование (2-е изд.). Athena Scientific. ISBN  1-886529-00-0.
9. Бертсекас, Дмитрий П. (2009). Теория выпуклой оптимизации. Athena Scientific. ISBN  978-1-886529-31-1.
10. Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. С. xiv + 490. Дои:10.1007/978-3-540-35447-5. ISBN  3-540-35445-X. Г-Н  2265882.
11. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 305. Берлин: Springer-Verlag. С. xviii + 417. ISBN  3-540-56850-6. Г-Н  1261420.
12. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «14 двойственности для практикующих». Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы связки. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306. Берлин: Springer-Verlag. С. xviii + 346. ISBN  3-540-56852-2. Г-Н  1295240.
13. Ласдон, Леон С. (2002) [Перепечатка Macmillan 1970 года]. Теория оптимизации для больших систем. Минеола, Нью-Йорк: Dover Publications, Inc., стр. Xiii + 523. ISBN  978-0-486-41999-2. Г-Н  1888251.
14. Лемарешаль, Клод (2001). «Лагранжева релаксация». В Юнгере, Михаэль; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г.. Конспект лекций по информатике (LNCS). 2241. Берлин: Springer-Verlag. С. 112–156. Дои:10.1007/3-540-45586-8_4. ISBN  3-540-42877-1. Г-Н  1900016.
15. Мину, Мишель (1986). Математическое программирование: теория и алгоритмы. Эгон Балас (нападающий); Стивен Вайда (транс) из французского (1983 Paris: Dunod). Чичестер: публикация Wiley-Interscience. John Wiley & Sons, Ltd., стр. Xxviii + 489. ISBN  0-471-90170-9. Г-Н  0868279. (Второе изд., 2008 г., на французском: Математическое программирование: теория и алгоритмы, Éditions Tec & Doc, Paris, 2008. xxx + 711 стр.).
16. Шапиро, Джереми Ф. (1979). Математическое программирование: структуры и алгоритмы. Нью-Йорк: Wiley-Interscience [John Wiley & Sons]. стр.xvi + 388. ISBN  0-471-77886-9. Г-Н  0544669.
17. Джеффрион, Артур М. (1971). «Двойственность в нелинейном программировании: упрощенная разработка, ориентированная на приложения». SIAM Обзор. 13 (1): 1–37. Дои:10.1137/1013001. JSTOR  2028848.

Рекомендации

Книги

• Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения. Прентис Холл. ISBN  0-13-617549-X.
• Бертсекас, Дмитрий; Недич, Анжелиа; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация. Athena Scientific. ISBN  1-886529-45-0.
• Бертсекас, Дмитрий П. (1999). Нелинейное программирование (2-е изд.). Athena Scientific. ISBN  1-886529-00-0.
• Бертсекас, Дмитрий П. (2009). Теория выпуклой оптимизации. Athena Scientific. ISBN  978-1-886529-31-1.
• Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. С. xiv + 490. Дои: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). «Лагранжева релаксация». В Юнгере, Михаэль; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г.. Конспект лекций по информатике (LNCS). 2241. Берлин: Springer-Verlag. С. 112–156. Дои:10.1007/3-540-45586-8_4. ISBN  3-540-42877-1. Г-Н  1900016.
• Мину, Мишель (1986). Математическое программирование: теория и алгоритмы. Эгон Балас (нападающий); Стивен Вайда (транс) из французского (1983 Paris: Dunod). Чичестер: публикация Wiley-Interscience. John Wiley & Sons, Ltd., стр. Xxviii + 489. ISBN  0-471-90170-9. Г-Н  0868279. (Второе изд., 2008 г., на французском языке: Математическое программирование: теория и алгоритмы, Éditions Tec & Doc, Paris, 2008. xxx + 711 pp.)).
• Nering, Evar D .; Такер, Альберт В. (1993). Линейное программирование и связанные с ним проблемы. Бостон, Массачусетс: Academic Press. ISBN  978-0-12-515440-6.
• Papadimitriou, Christos H .; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность (Несокращенное ред.). Дувр. ISBN  0-486-40258-4.
• Рущинский, Анджей (2006). Нелинейная оптимизация. Принстон, штат Нью-Джерси: Princeton University Press. С. xii + 454. ISBN  978-0691119151. Г-Н  2199043.

Статьи

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