Слабка двоїстість

Слабка двоїстість — це концепція в оптимізації, яка стверджує, що розрив двоїстості завжди більший або дорівнює нулю. Це означає, що розв'язок прямої задачі (задачі мінімізації) завжди більший або дорівнює розв'язку пов'язаної двоїстої задачі. Цей термін протиставляється сильній двоїстості, яка виконується лише за певних умов.

Використання

Багато прямодвоїстих апроксимаційних алгоритмів засновані на принципі слабкої двоїстості.

Теорема про слабку двоїстість

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

Максимізувати $\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.