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

Duality (optimization)

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

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

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

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

Если есть условия ограничения, их можно встроить в функцию позволяя куда является подходящей функцией на который имеет минимум 0 на ограничениях, и для которого можно доказать, что . Последнее условие тривиально, но не всегда удобно, выполняется для характеристическая функция (т.е. за удовлетворяющие ограничениям и иначе). Затем продлите к функция возмущения такой, что .[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

с доменом имея непустой интерьер, Функция Лагранжа определяется как

Векторы и называются двойные переменные или же Векторы множителей Лагранжа связано с проблемой. В Двойственная функция Лагранжа определяется как

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

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

Выпуклые проблемы

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

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

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

называется двойственной проблемой Вульфа. С этой проблемой может быть трудно справиться с помощью вычислений, потому что целевая функция не является вогнутой в совместных переменных. . Кроме того, ограничение равенства в общем случае нелинейна, поэтому двойственная задача Вульфа обычно является невыпуклой задачей оптимизации. В любом слючае, слабая двойственность держит.[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.CS1 maint: ref = harv (ссылка на сайт)
  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.CS1 maint: ref = harv (ссылка на сайт)
  14. ^ Лемарешаль, Клод (2001). «Лагранжева релаксация». В Юнгере, Михаэль; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г.. Конспект лекций по информатике (LNCS). 2241. Берлин: Springer-Verlag. С. 112–156. Дои:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. Г-Н 1900016.CS1 maint: ref = harv (ссылка на сайт)
  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 стр.).CS1 maint: ref = harv (ссылка на сайт)
  16. ^ Шапиро, Джереми Ф. (1979). Математическое программирование: структуры и алгоритмы. Нью-Йорк: Wiley-Interscience [John Wiley & Sons]. стр.xvi + 388. ISBN 0-471-77886-9. Г-Н 0544669.CS1 maint: ref = harv (ссылка на сайт)
  17. ^ Джеффрион, Артур М. (1971). «Двойственность в нелинейном программировании: упрощенная разработка, ориентированная на приложения». SIAM Обзор. 13 (1): 1–37. Дои:10.1137/1013001. JSTOR 2028848.

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

Книги

Статьи