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

редактировать

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

Содержание

1 Двойная задача
- 1.1 Разрыв двойственности
2 Линейный случай
- 2.1 Связь между прямой задачей и двойственной задачей
3 Нелинейный случай
- 3.1 Сильный лагранжев принцип: Двойственность Лагранжа
- 3.2 Выпуклые задачи
4 История
5 См. Также
6 Примечания
7 Ссылки
- 7.1 Книги
- 7.2 Статьи

Двойная задача

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

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

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

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

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

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

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

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

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

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

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

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

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

Связь между основной задачей и двойной задачей

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

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

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

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

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

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

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

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

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

минимизировать f 0 (x) при условии fi (x) ≤ 0, я ∈ {1,…, m} привет (x) = 0, i ∈ {1,…, p} {\ displaystyle {\ begin {align} {\ text {minim}} 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 {align}}}

{ \ Displaystyle {\ begin {align} {\ text {minim}} 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 {align}}}

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

Λ (x, λ, ν) = f 0 (x) + ∑ i = 1 m λ ifi (x) + ∑ i = 1 p ν ihi (x). {\ 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).}

\ 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}$ $\ lambda$ и $ν {\ displaystyle \ nu}$ $\ nu$ называются двойственными переменными или векторами множителей Лагранжа, связанными с проблемой. Двойственная функция Лагранжа $g: R m × R p → R {\ displaystyle g: \ mathbb {R} ^ {m} \ times \ mathbb {R} ^ {p} \ to \ mathbb {R}}$ $g: \ mathbb {R} ^ {m} \ times \ mathbb {R} ^ {p} \ to \ mathbb {R}$ определяется как

g (λ, ν) = inf x ∈ D Λ (x, λ, ν) = inf x ∈ D (f 0 (x) + ∑ i = 1 m λ ifi ( х) + ∑ i = 1 p ν ihi (x)). {\ 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 (\ 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 является вогнутой, даже если исходная задача не является выпуклой, поскольку это точная нижняя грань аффинной функции. Двойственная функция дает нижние границы оптимального значения $p ∗ {\ displaystyle p ^ {*}}$ $p ^ {*}$ исходной задачи; для любого $λ ≥ 0 {\ displaystyle \ lambda \ geq 0}$ $\ lambda \ geq 0$ и любого $ν {\ displaystyle \ nu}$ $\ nu$ мы имеем $g (λ, ν) ≤ p ∗ {\ displaystyle g (\ lambda, \ nu) \ leq p ^ {*}}$ $g (\ lambda, \ nu) \ leq p ^ {*}$ .

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

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

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

минимизировать xf (x) subjecttogi (x) ≤ 0, i = 1,…, m {\ displaystyle {\ begin {align} {\ underset {x} {\ operatorname {minim }}} f (x) \\ \ operatorname {subject \; to} g_ {i} (x) \ leq 0, \ quad i = 1, \ ldots, m \ end {align}}}

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

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

максимизировать u inf x (f (x) + ∑ j = 1 mujgj (x)) subjecttoui ≥ 0, i = 1,…, m {\ displaystyle {\ begin {align} {\ underset {u} {\ operatornam e {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 {align}}}

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

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

максимизировать x, uf (x) + ∑ j = 1 mujgj (x) при условии ∇ f (x) + ∑ j = 1 muj ∇ gj (x) = 0 ui ≥ 0, i = 1,…, m {\ displaystyle {\ begin {align} {\ 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 {align}}}

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

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

История

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

См. Также

Примечания

Ссылки

Книги

Ахуджа, Равиндра К. ; Магнанти, Томас Л. ; Орлин, Джеймс Б. (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. DOI : 10.1007 / 978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882. CS1 maint: ref = harv (ссылка )
Кук, Уильям Дж. ; Cunningham, William H.; Pulleyblank, William R. ; Schrijver, Alexander (12 ноября 1997 г.). Комбинаторная оптимизация (1-е изд.). John Wiley Sons. ISBN 0-471-55894-X.
Данциг, Джордж Б. (1963). Linear Programming and Extensions. Princeton, NJ: Princeton University Press.
Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Выпуклый анализ и алгоритмы минимизации, Том I: Основы. Grundlehren der Mathematischen Wissenschaften [Фундаментальные принципы математических наук]. 305 . Berlin: Springer-Verlag. Pp. Xviii + 417. ISBN 3-540-56850-6. MR 1261420.
Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). "14 двойственности для практиков". Выпуклый анализ и алгоритмы минимизации, Том II: Расширенная теория и методы расслоения. Grundlehren der Mathematischen Wissenschaften [Fundamen Основы математических наук. 306 . Берлин: Springer-Verlag. С. xviii + 346. ISBN 3-540-56852-2. MR 1295240.
Ласдон, Леон С. (2002) [Перепечатка Macmillan 1970 года]. Теория оптимизации для больших систем. Минеола, Нью-Йорк: Dover Publications, Inc., стр. Xiii + 523. ISBN 978-0-486-41999-2. MR 1888251. CS1 maint: ref = harv (ссылка )
Лоулер, Юджин (2001). "4.5. Комбинаторные последствия теоремы о максимальном потоке и минимальном разрезе, 4.6. Интерпретация линейным программированием теоремы о минимальном разрезе максимального потока". Комбинаторная оптимизация: сети и матроиды. Довер. Стр. 117–120. ISBN 0-486-41453-1.
Lemaréchal, Claude (2001). «Лагранжева релаксация». In Jünger, Michael; Naddef, Denis (eds.). Вычислительная комбинаторная оптимизация: Доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г. Лекционные заметки по информатике (LNCS). 2241 . Berlin: Springer-Verlag. Pp. 112–156. doi : 10.1007 / 3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016. Обслуживание CS1 : ref = harv (ссылка )
(1986). Математическое программирование: теория и алгоритмы. Эгон Балас (вперед); Стивен Вайда (перевод) с французского (1983 Paris: Dunod). Чичестер: A Wiley-Interscience Публикация. John Wiley Sons, Ltd. С. xxviii + 489. ISBN 0-471-90170-9. MR 0868279. (Второе изд., 2008 г., на французском языке: Programmation mathématique: Théorie et algorithmes, Éditions Tec Doc, Paris, 2008. xxx + 711 pp.)). CS1 maint: ref = harv (ссылка )
Неринг, Эвар Д.; Такер, Альберт В. (1993). Линейное программирование и связанные с ним проблемы. Бостон, Массачусетс: Academic Press. ISBN 978-0-12- 515440-6.
Пападимитриу, Христос Х.; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность (несокращенное издание). Dover. ISBN 0-486-40258- 4.
Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. Pp. Xii + 454. ISBN 978-0691119151. MR 2199043.

Статьи

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