Просмотр кода страницы Слабая двойственность

'''Слабая двойственность''' — это концепция в [[Оптимизация (математика)|оптимизации]], которая утверждает, что [[разрыв двойственности]] всегда больше или равен нулю. Это означает, что решение прямой задачи (задачи минимизации) ''всегда'' больше или равно решению связанной [[Двойственность (оптимизация)|двойственной задачи]]. Данный термин противопоставляется [[Сильная двойственность|сильной двойственности]], которая выполняется лишь в определённых условиях{{sfn|Boţ, Grad, Wanka|2009|с=1}}.

== Использование ==
Многие прямодвойственные<ref>Прямодвойственный алгоритм — это алгоритм одновременного решения прямой и двойственной задач.</ref> [[Аппроксимационный алгоритм|аппроксимационные алгоритмы]] основаны на принципе слабой двойственности{{sfn|Gonzalez|2007|с=2}}.

== Теорема о слабой двойственности ==
''Прямая'' задача:
: Максимизировать <math>\mathbf{c}^T\mathbf{x}</math> при условии <math>A\mathbf{x} \leqslant \mathbf{b}, \mathbf{x} \geqslant 0</math>;
''Двойственная'' задача:
: Минимизировать <math>\mathbf{b}^T\mathbf{y}</math> при условии <math>A^T\mathbf{y} \geqslant \mathbf{c}, \mathbf{y} \geqslant 0</math>.

Теорема о слабой двойственности утверждает, что <math>\mathbf{c}^T\mathbf{x}\leqslant\mathbf{b}^T\mathbf{y}</math>.

А именно, что если <math>(x_1,x_2,....,x_n)</math> является допустимым решением прямой задачи максимизации [[Линейное программирование|линейного программирования]], а <math>(y_1,y_2,....,y_m)</math> является допустимым решением двойственной задачи минимизации линейного программирования, то теорему слабой двойственности можно сформулировать следующим образом:
<math>\sum_{j=1}^n c_j x_j \leqslant \sum_{i=1}^m b_i y_i </math>, где <math> c_j </math> и <math> b_i </math> являются коэффициентами соответствующих целевых функций.

Доказательство:
<math>\mathbf{c}^T\mathbf{x}=\mathbf{x}^T\mathbf{c} \leqslant \mathbf{x}^TA^T\mathbf{y}\leqslant\mathbf{b}^T\mathbf{y}</math>

=== Обобщения ===
В более общем случае, если <math>x</math> является допустимым решением для прямой задачи максимизации, а <math>y</math> является допустимым решением для двойственной задачи минимизации, из слабой двойственности вытекает, что <math>f(x) \leqslant g(y)</math>, где <math>f</math> и <math>g</math> являются целевыми функциями для прямой и двойственной задач соответственно.

== См. также ==
* [[Выпуклое программирование]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|автор=Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka
|ref=Boţ, Grad, Wanka
|doi = 10.1007/978-3-642-02886-1
|isbn= 978-3-642-02885-4
|место= Berlin
|mr= 2542013
|страницы= 1
|издательство= Springer-Verlag
|заглавие=Duality in Vector Optimization
|ссылка= https://books.google.com/books?id=nwB0qExrF00C&pg=PA1
|год= 2009
}}
* {{книга
|заглавие=Handbook of Approximation Algorithms and Metaheuristics
|ref=Gonzalez
|автор= Teofilo F. Gonzalez 
|издательство= CRC Press
|год=2007
|isbn=9781420010749
|страницы=2-12<!-- это не несколько страниц, не заменяйте дефис на тире -->
|ссылка=https://books.google.com/books?id=QK3_VU8ngK8C&pg=SA2-PA12
}}

[[Категория:Линейное программирование]]
[[Категория:Выпуклая оптимизация]]
{{rq|checktranslate|style}}