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

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

Использование

Многие прямодвойственные аппроксимационные алгоритмы основаны на принципе слабой двойственности.

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

Прямая задача:

Максимизировать $\mathbf {c} ^{T}\mathbf {x}$ при условии $A\mathbf {x} \leqslant \mathbf {b} ,\mathbf {x} \geqslant 0$;

Двойственная задача:

Минимизировать $\mathbf {b} ^{T}\mathbf {y}$ при условии $A^{T}\mathbf {y} \geqslant \mathbf {c} ,\mathbf {y} \geqslant 0$.

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

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

Доказательство: $\mathbf {c} ^{T}\mathbf {x} =\mathbf {x} ^{T}\mathbf {c} \leqslant \mathbf {x} ^{T}A^{T}\mathbf {y} \leqslant \mathbf {b} ^{T}\mathbf {y}$

Обобщения

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

См. также

• Выпуклое программирование

Литература

• Radu Ioan Boţ, Sorin-Mihai Grad, Gert Wanka. Duality in Vector Optimization. — Berlin: Springer-Verlag, 2009. — С. 1. — ISBN 978-3-642-02885-4. — doi:10.1007/978-3-642-02886-1.
• Teofilo F. Gonzalez. Handbook of Approximation Algorithms and Metaheuristics. — CRC Press, 2007. — С. 2-12. — ISBN 9781420010749.