Слабая двойственность

В прикладной математике слабая двойственность — это концепция оптимизации , которая утверждает, что разрыв двойственности всегда больше или равен 0. Это означает, что для любой задачи минимизации, называемой основной проблемой , решение основной проблемы всегда больше или равно решению двойной задачи максимизации . ^[1]^: 225 Альтернативно, решение задачи первичной максимизации всегда меньше или равно решению задачи двойной минимизации.

Слабая двойственность контрастирует с сильной двойственностью , которая утверждает, что первичная оптимальная цель и двойственная оптимальная цель равны . Сильная двойственность имеет место только в определенных случаях. ^[2]

Использует [ править ]

Многие алгоритмы первично-двойственной аппроксимации основаны на принципе слабой двойственности. ^[3]

Теорема слабой о двойственности

Рассмотрим задачу линейного программирования :

{\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b,\\&x\geq 0,\end{aligned}}

( 1 )

где $A$ является $m\times n$ и $b$ является $m\times 1$ . Двойственная : задача ( 1 ) такова

${\begin{aligned}{\underset {y\in \mathbb {R} ^{m}}{\text{minimize}}}\quad &b^{\top }y\\{\text{subject to}}\quad &A^{\top }y\geq c,\\&y\geq 0.\end{aligned}}$

( 2 )

Теорема слабой двойственности утверждает, что $c^{\top }x^{*}\leq b^{\top }y^{*}$ для каждого решения $x^{*}$ к основной проблеме ( 1 ) и каждому решению $y^{*}$ к двойственной задаче ( 2 ).

А именно, если $(x_{1},x_{2},....,x_{n})$ является возможным решением для линейной программы первичной максимизации и $(y_{1},y_{2},....,y_{m})$ является допустимым решением для линейной программы двойной минимизации, то теорему слабой двойственности можно сформулировать как $\sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}$ , где $c_{j}$ и $b_{i}$ – коэффициенты соответствующих целевых функций.

Доказательство: $с Т х = х Т с \leq х Т А Т й \leq б Т и$

Обобщения [ править ]

В более общем смысле, если $x$ является возможным решением задачи первичной максимизации и $y$ является допустимым решением двойственной задачи минимизации, то из слабой двойственности следует $f(x)\leq g(y)$ где $f$ и $g$ являются целевыми функциями для основной и двойственной задач соответственно.

См. также [ править ]

Ссылки [ править ]

^ Бойд, С.П., Ванденберге, Л. (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 .
^ Бот, Раду Йоан; Град, Сорин-Михай; Ванка, Герт (2009), Двойственность в векторной оптимизации , Берлин: Springer-Verlag, стр. 1, doi : 10.1007/978-3-642-02886-1 , ISBN. 978-3-642-02885-4 , МР 2542013 .
^ Гонсалес, Теофило Ф. (2007), Справочник по алгоритмам аппроксимации и метаэвристике , CRC Press, стр. 2–12, ISBN 9781420010749 .

[1] Бойд, С.П., Ванденберге, Л. (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 .

[2] Бот, Раду Йоан; Град, Сорин-Михай; Ванка, Герт (2009), Двойственность в векторной оптимизации , Берлин: Springer-Verlag, стр. 1, doi : 10.1007/978-3-642-02886-1 , ISBN. 978-3-642-02885-4 , МР 2542013 .

[3] Гонсалес, Теофило Ф. (2007), Справочник по алгоритмам аппроксимации и метаэвристике , CRC Press, стр. 2–12, ISBN 9781420010749 .

[1]

[2]

[3]