В задачах оптимизации в прикладной математике , то разрыв двойственности разница между прямым и двойственными решениями . Если оптимальное двойное значение и оптимальное прямое значение, то разрыв дуальности равен . Это значение всегда больше или равно 0 (для задач минимизации). Разрыв дуальности равен нулю тогда и только тогда, когда имеет место сильная двойственность . В противном случае разрыв строго положительный и имеет место слабая двойственность . [1]
В общем случае даны две двойственные пары, разделенные локально выпуклыми пространствами а также . Тогда с учетом функции, мы можем определить основную задачу как
Если есть условия ограничения, их можно встроить в функцию позволяя где - индикаторная функция . Тогда пусть- возмущающая функция такая, что. Разрыв двойственности является разность задается
где является выпуклым сопряженным по обеим переменным. [2] [3] [4]
При вычислительной оптимизации часто сообщается о другом «пробеле двойственности», который представляет собой разницу в значении между любым двойным решением и значением допустимой, но неоптимальной итерации для основной задачи. Этот альтернативный «разрыв двойственности» количественно определяет несоответствие между значением текущей допустимой, но неоптимальной итерации для основной задачи и значением двойственной задачи; значение двойственной задачи при условиях регулярности равно значению выпуклой релаксации прямой задачи: выпуклая релаксация - это проблема, возникающая при замене невыпуклого допустимого множества его замкнутой выпуклой оболочкой и заменой невыпуклого допустимого множества его замкнутой выпуклой оболочкой. выпуклая функция с ее выпуклым замыканием , то есть функция, имеющая надграфик , являющийся замкнутой выпуклой оболочкой исходной прямой целевой функции. [5] [6] [7] [8] [9] [10] [11] [12] [13]
Рекомендации
- ^ Борвейн, Джонатан; Чжу, Цицзи (2005). Методы вариационного анализа . Springer. ISBN 978-1-4419-2026-3.
- ^ Раду Иоанн Бо; Герт Ванка; Сорин-Михай Град (2009). Двойственность в векторной оптимизации . Springer. ISBN 978-3-642-02885-4.
- ^ Эрнё Роберт Четнек (2010). Преодоление несоблюдения классических обобщенных условий регулярности внутренней точки при выпуклой оптимизации. Приложения теории двойственности к расширению максимальных монотонных операторов . Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
- ^ Зэлинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . River Edge, NJ: World Scientific Publishing Co. Inc. стр. 106 -113. ISBN 981-238-067-1. Руководство по ремонту 1921556 .
- ^ Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл. ISBN 0-13-617549-X.
- ^ Бертсекас, Дмитрий П. (1999). Нелинейное программирование (2-е изд.). Афина Сайентифик. ISBN 1-886529-00-0.
- ^ Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. С. xiv + 490. DOI : 10.1007 / 978-3-540-35447-5 . ISBN 3-540-35445-X. Руководство по ремонту 2265882 .
- ^ Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 305 . Берлин: Springer-Verlag. С. xviii + 417. ISBN 3-540-56850-6. Руководство по ремонту 1261420 .
- ^ Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «XII. Абстрактная двойственность для практиков». Выпуклый анализ и алгоритмы минимизации, Том II: Расширенная теория и методы связки . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306 . Берлин: Springer-Verlag. С. xviii + 346. DOI : 10.1007 / 978-3-662-06409-2_4 . ISBN 3-540-56852-2. Руководство по ремонту 1295240 .
- ^ Ласдон, Леон С. (2002) [Перепечатка Macmillan 1970 года]. Теория оптимизации для больших систем . Минеола, Нью-Йорк: Dover Publications, Inc., стр. Xiii + 523. ISBN 978-0-486-41999-2. Руководство по ремонту 1888251 .
- ^ Лемарешаль, Клод (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 стр.).
- ^ Шапиро, Джереми Ф. (1979). Математическое программирование: структуры и алгоритмы . Нью-Йорк: Wiley-Interscience [John Wiley & Sons]. С. xvi + 388 . ISBN 0-471-77886-9. Руководство по ремонту 0544669 .