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

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

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

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

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

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

Максимизировать

\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$ являются целевыми функциями для прямой и двойственной задач соответственно.

См. также

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

Примечания

Boţ, Grad, Wanka, 2009, с. 1.
Прямодвойственный алгоритм — это алгоритм одновременного решения прямой и двойственной задач.
Gonzalez, 2007, с. 2.

Литература

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_e13b95a7e2330dac-1] Boţ, Grad, Wanka, 2009, с. 1.

[2] Прямодвойственный алгоритм — это алгоритм одновременного решения прямой и двойственной задач.

[_0b54189f5a9f1196-3] Gonzalez, 2007, с. 2.