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

Принцип математической оптимизации

В математической теории оптимизации двойственность или принцип двойственности — это принцип, согласно которому задачи оптимизации можно рассматривать с двух точек зрения: с точки зрения основной задачи или с точки зрения двойственной задачи . Если основная задача является задачей минимизации, то двойственная задача является задачей максимизации (и наоборот). Любое допустимое решение основной задачи (задачи минимизации) по крайней мере столь же велико, как и любое допустимое решение двойственной задачи (задачи максимизации). Следовательно, решение основной задачи является верхней границей решения двойственной задачи, а решение двойственной задачи является нижней границей решения основной задачи. ^[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}$

Если есть условия ограничений, их можно встроить в функцию, разрешив где — подходящая функция на , которая имеет минимум 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 переменных. Цель состоит в том, чтобы максимизировать значение целевой функции с учетом ограничений. Решение — это вектор (список) из n значений, который достигает максимального значения для целевой функции.

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

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

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

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

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

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

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

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

Двойственность Лагранжа

Мотивация . ^[17] Предположим, мы хотим решить следующую задачу нелинейного программирования :

${\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}}$

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

${\displaystyle J(x)=f_{0}(x)+\sum _{i}I[f_{i}(x)]}$

где I — бесконечная ступенчатая функция : I[u]=0, если u≤0, и I[u]=∞ в противном случае. Но J ( x ) трудно решить, поскольку она не является непрерывной. Можно «аппроксимировать» I[u] с помощью λu , где λ — положительная константа. Это дает функцию, известную как лагранжиан:

${\displaystyle L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)}$

Обратите внимание, что для каждого x ,

${\displaystyle \max _{\lambda \geq 0}L(x,\lambda )=J(x)}$.

Доказательство :

• Если x удовлетворяет всем ограничениям f _i ( x )≤0, то L( x , λ ) максимизируется при λ =0, и тогда ее значение равно f(x);
• Если x нарушает некоторое ограничение, f _i ( x )>0 для некоторого i , то L(x, λ )→∞ при λ _i →∞ .

Таким образом, исходная задача эквивалентна:

${\displaystyle \min _{x}\max _{\lambda \geq 0}L(x,\lambda )}$.

Поменяв местами минимум и максимум, получим:

${\displaystyle \max _{\lambda \geq 0}\min _{x}L(x,\lambda )}$.

Двойственная функция — это внутренняя задача в приведенной выше формуле:

${\displaystyle g(\lambda ):=\min _{x}L(x,\lambda )}$.

Двойственная программа Лагранжа — это программа максимизации g:

${\displaystyle \max _{\lambda \geq 0}g(\lambda )}$.

Оптимальное решение двойственной программы — это нижняя граница оптимального решения исходной (первичной) программы; это слабый принцип двойственности . Если первичная задача выпукла и ограничена снизу, и существует точка, в которой все нелинейные ограничения строго выполняются ( условие Слейтера ), то оптимальное решение двойственной программы равно оптимальному решению первичной программы; это сильный принцип двойственности . В этом случае мы можем решить первичную программу, найдя оптимальное решение λ * для двойственной программы, а затем решив:

${\displaystyle \min _{x}L(x,\lambda ^{*})}$.

Обратите внимание, что для использования слабого или сильного принципа двойственности нам нужен способ вычисления g( λ ). В общем случае это может быть сложно, так как нам нужно решить отдельную задачу минимизации для каждого λ . Но для некоторых классов функций можно получить явную формулу для g() . Решение прямой и двойственной программ вместе часто проще, чем решение только одной из них. Примерами являются линейное программирование и квадратичное программирование . Лучший и более общий подход к двойственности обеспечивается теоремой двойственности Фенхеля . ^{[18] : Sub.3.3.1}

Другое условие, при котором min-max и max-min равны, — это когда лагранжиан имеет седловую точку : (x∗, λ∗) является седловой точкой функции Лагранжа L тогда и только тогда, когда x∗ является оптимальным решением прямой задачи, λ∗ является оптимальным решением двойственной задачи, а оптимальные значения в указанных задачах равны друг другу. ^{[18] : Предложение 3.2.2}

Сильный принцип Лагранжа

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

${\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 {\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$

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

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

История

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

Приложения

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

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

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

Примечания

1. Бойд, Стивен П.; Ванденберг, Ливен (2004). Выпуклая оптимизация (pdf) . Cambridge University Press. стр. 216. ISBN 978-0-521-83378-3. Получено 15 октября 2011 г. .
2. Бот, Раду Иоан; Ванка, Герт; Град, Сорин-Михай (2009). Двойственность в векторной оптимизации . Спрингер. ISBN 978-3-642-02885-4.
3. Csetnek, Ernö Robert (2010). Преодоление неудачи классических обобщенных условий регулярности внутренней точки в выпуклой оптимизации. Приложения теории двойственности к расширениям максимальных монотонных операторов . Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3.
4. Zălinescu, Constantin (2002). Выпуклый анализ в общих векторных пространствах . River Edge, NJ: World Scientific Publishing Co., Inc. стр. 106–113. ISBN 981-238-067-1. МР  1921556.
5. Борвейн, Джонатан; Чжу, Цицзи (2005). Методы вариационного анализа . Springer. ISBN 978-1-4419-2026-3.
6. Ахуджа, Равиндра К .; Магнанти, Томас Л .; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Prentice Hall. 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. Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе пересмотренное издание перевода французского издания 1997 года). Берлин: Springer-Verlag. С. xiv+490. doi :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. Lasdon, Leon S. (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. MR  1900016. S2CID  9048698.
15. Minoux, Michel (1986). Математическое программирование: Теория и алгоритмы . Эгон Балас (перевод); Стивен Вайда (перевод) из (1983 Париж: Dunod) французский. Чичестер: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. стр. xxviii+489. ISBN 0-471-90170-9. MR  0868279. (Второе издание 2008 г., на французском языке: Programmation Mathématique: Théorie et алгоритмы , Éditions Tec & Doc, Париж, 2008. xxx+711 стр.).
16. Шапиро, Джереми Ф. (1979). Математическое программирование: Структуры и алгоритмы. Нью-Йорк: Wiley-Interscience [John Wiley & Sons]. С. xvi+388. ISBN 0-471-77886-9. МР  0544669.
17. Дэвид Ноулз (2010). «Лагранжева дуальность для чайников» (PDF) .
18. Немировски и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
19. Джеффрион, Артур М. (1971). «Двойственность в нелинейном программировании: упрощенная разработка, ориентированная на приложения». Обзор SIAM . 13 (1): 1–37. doi :10.1137/1013001. JSTOR  2028848.

Ссылки

Книги

• Ахуджа, Равиндра К.; Магнанти , Томас Л .; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Prentice Hall. 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.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе пересмотренное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. стр. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. МР  2265882.
• Кук, Уильям Дж .; Каннингем, Уильям Х.; Пуллибланк, Уильям Р .; Шрайвер, Александр (12 ноября 1997 г.). Комбинаторная оптимизация (1-е изд.). John Wiley & Sons. ISBN 0-471-55894-X.
• Данциг, Джордж Б. (1963). Линейное программирование и расширения . Принстон, Нью-Джерси: Princeton University Press.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (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.
• Lasdon, Leon S. (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. MR  1900016. S2CID  9048698.
• Minoux, Michel (1986). Математическое программирование: Теория и алгоритмы . Эгон Балас (перевод); Стивен Вайда (перевод) из (1983 Париж: Dunod) французский. Чичестер: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. стр. xxviii+489. ISBN 0-471-90170-9. MR  0868279. (Второе издание 2008 г., на французском языке: Programmation Mathématique: Théorie et алгоритмы , Éditions Tec & Doc, Париж, 2008. xxx+711 стр.)).
• Неринг, Эвар Д.; Такер, Альберт В. (1993). Линейное программирование и смежные проблемы . Бостон, Массачусетс: Academic Press. ISBN 978-0-12-515440-6.
• Пападимитриу, Христос Х.; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность (несокращенное издание). Дувр. ISBN 0-486-40258-4.
• Ruszczyński, Andrzej (2006). Нелинейная оптимизация . Princeton, NJ: Princeton University Press . стр. xii+454. ISBN 978-0-691-11915-1. МР  2199043.

Статьи

• Эверетт, Хью III (1963). «Обобщенный метод множителей Лагранжа для решения задач оптимального распределения ресурсов». Исследование операций . 11 (3): 399–417. doi :10.1287/opre.11.3.399. JSTOR  168028. MR  0152360. Архивировано из оригинала 24.07.2011.
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (август 2007 г.). «Лагранжева релаксация с помощью методов субградиента ballstep». Mathematics of Operations Research . 32 (3): 669–686. doi :10.1287/moor.1070.0261. MR  2348241. Архивировано из оригинала 26.07.2011 . Получено 12.05.2011 .
• Двойственность в линейном программировании Гэри Д. Нотт