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

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

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

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

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

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

Максимізувати ${\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}$ — цільові функції для прямої і двоїстої задач відповідно.

Див. також

• Опукла оптимізація

Примітки

1. Boţ, Grad, Wanka, 2009, с. 1.
2. Прямодвоїстий алгоритм — це алгоритм одночасного розв'язування прямої і двоїстої задач.
3. Gonzalez, 2007, с. 2.

Література

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