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

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

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

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

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

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

Максимизировать ${𝐜}^T𝐱$ при условии $A𝐱⩽𝐛,𝐱⩾0$;

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

Минимизировать ${𝐛}^T𝐲$ при условии $A^T𝐲⩾𝐜,𝐲⩾0$.

Теорема о слабой двойственности утверждает, что ${𝐜}^T𝐱⩽{𝐛}^T𝐲$.

А именно, что если $(x_1,x_2,....,x_n)$ является допустимым решением прямой задачи максимизации линейного программирования, а $(y_1,y_2,....,y_m)$ является допустимым решением двойственной задачи минимизации линейного программирования, то теорему слабой двойственности можно сформулировать следующим образом: $\sum _{j=1}^n{c}_j{x}_j⩽\sum _{i=1}^m{b}_i{y}_i$, где $c_j$ и $b_i$ являются коэффициентами соответствующих целевых функций.

Доказательство: ${𝐜}^T𝐱={𝐱}^T𝐜⩽{𝐱}^T{A}^T𝐲⩽{𝐛}^T𝐲$

Обобщения

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга