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

Слабка двоїстість — це концепція в оптимізації, яка стверджує, що розрив двоїстості завжди більший або дорівнює нулю. Це означає, що розв'язок прямої задачі (задачі мінімізації) завжди більший або дорівнює розв'язку пов'язаної двоїстої задачі. Цей термін протиставляється сильній двоїстості, яка виконується лише за певних умовШаблон: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$ — цільові функції для прямої і двоїстої задач відповідно.

Див. також

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

Література

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