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


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

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

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

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

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

Максимизировать c T x {displaystyle mathbf {c} ^{T}mathbf {x} } при условии A x ⩽ b , x ⩾ 0 {displaystyle Amathbf {x} leqslant mathbf {b} ,mathbf {x} geqslant 0} ;

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

Минимизировать b T y {displaystyle mathbf {b} ^{T}mathbf {y} } при условии A T y ⩾ c , y ⩾ 0 {displaystyle A^{T}mathbf {y} geqslant mathbf {c} ,mathbf {y} geqslant 0} .

Теорема о слабой двойственности утверждает, что c T x ⩽ b T y {displaystyle mathbf {c} ^{T}mathbf {x} leqslant mathbf {b} ^{T}mathbf {y} } .

А именно, что если ( x 1 , x 2 , . . . . , x n ) {displaystyle (x_{1},x_{2},....,x_{n})} является допустимым решением прямой задачи максимизации линейного программирования, а ( y 1 , y 2 , . . . . , y m ) {displaystyle (y_{1},y_{2},....,y_{m})} является допустимым решением двойственной задачи минимизации линейного программирования, то теорему слабой двойственности можно сформулировать следующим образом: ∑ j = 1 n c j x j ⩽ ∑ i = 1 m b i y i {displaystyle sum _{j=1}^{n}c_{j}x_{j}leqslant sum _{i=1}^{m}b_{i}y_{i}} , где c j {displaystyle c_{j}} и b i {displaystyle b_{i}} являются коэффициентами соответствующих целевых функций.

Доказательство: c T x = x T c ⩽ x T A T y ⩽ b T y {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} }

Обобщения

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


  • Минимизирующая последовательность
  • Полуопределённое программирование
  • Нелинейная задача собственных значений
  • Смешанное произведение
  • Уравнение переноса

  •  

    • Яндекс.Метрика
    • Индекс цитирования