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

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

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

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

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

Двоїста задача:

Мінімізувати ${\displaystyle \mathbf {b} ^{T}\mathbf {y} }$ за умови ${\displaystyle A^{T}\mathbf {y} \geqslant \mathbf {c} ,\mathbf {y} \geqslant 0}$.

Теорема про слабку двоїстість стверджує, що ${\displaystyle \mathbf {c} ^{T}\mathbf {x} \leqslant \mathbf {b} ^{T}\mathbf {y} }$.

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

Доведення: ${\displaystyle \mathbf {c} ^{T}\mathbf {x} =\mathbf {x} ^{T}\mathbf {c} \leqslant \mathbf {x} ^{T}A^{T}\mathbf {y} \leqslant \mathbf {b} ^{T}\mathbf {y} }$

У загальнішому випадку, якщо ${\displaystyle x}$ — допустимий розв'язок прямої задачі максимізації, а ${\displaystyle y}$ — допустимий розв'язок двоїстої задачі мінімізації, зі слабкої двоїстості випливає, що ${\displaystyle f(x)\leqslant g(y)}$, де ${\displaystyle f}$ і ${\displaystyle 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.