Сильна двоїстість

Сильна двоїстість — випадок у математичній оптимізації, коли пряма і двоїсті цільові значення рівні. Існує подібний випадок, слабка двоїстість, коли пряма задача має оптимальне значення не менше за двоїсту, тобто, розрив двоїстості більший або рівний нулю.

Лінійне програмування

Пряма задача		Двоїста задача
максимізувати	$c^{T}x$	мінімізувати	$b^{T}y$
за умов	${\begin{matrix}Ax\leq b\\\end{matrix}}$	за умов	${\begin{matrix}A^{T}y=c\\y\geq 0\end{matrix}}$

Теорема про сильну двоїстість: Якщо пряма і двоїсті задачі розв'язні, тоді оптимальні точки $x,y$ задовольняють $c^{T}x=y^{T}b$.

Доведення: Розглянемо таке рівняння

${\begin{bmatrix}A&0\\-c^{T}&b^{T}\\0&A^{T}\\0&-A^{T}\\0&-I\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}\leq {\begin{bmatrix}b\\0\\c\\-c\\0\end{bmatrix}}$

Якщо існують $x,y$, що задовольняють цьому рівнянню, тоді $Ax\leq b$, отже $x$ допустимий розв'язок, $y\geq 0$ і $A^{T}y=c$, отже $y$ також допустимий розв'язок. Тоді оскільки $-c^{T}x+b^{T}y\leq 0$ та за принцип слабкої двоїстості маємо, що $c^{T}x=y^{T}b$ і на цьому доведення закінчено. Інакше, згідно з наслідком леми Фаркаша, існує вектор $[y^{T}\lambda x_{p}^{T}x_{m}^{T}w^{T}]\geq 0$, що задовольняє

${\begin{bmatrix}y^{T}&\lambda &x_{p}^{T}&x_{m}^{T}&w^{T}\end{bmatrix}}{\begin{bmatrix}A&0\\-c^{T}&b^{T}\\0&A^{T}\\0&-A^{T}\\0&-I\end{bmatrix}}=0$ і ${\begin{bmatrix}y^{T}&\lambda &x_{p}^{T}&x_{m}^{T}&w^{T}\end{bmatrix}}{\begin{bmatrix}b\\0\\c\\-c\\0\end{bmatrix}}<0$

З цього маємо таке

1. $y^{T}A=\lambda c^{T}$ і $y\geq 0$
2. $\lambda b+A(x_{m}-x_{p})-w=0$, тобто $A(x_{p}-x_{m})\leq \lambda b$
3. $y^{T}b<c^{T}(x_{p}-x_{m})$

Якщо $\lambda >0$, тоді можна помножити вектор ${\begin{bmatrix}y^{T}&\lambda &x_{p}^{T}&x_{m}^{T}&w^{T}\end{bmatrix}}$ на $1/\lambda$ і вважати, що $\lambda =1$. Однак, тоді пункти 1 і 2 показують, що $x_{p}-x_{m}$ і $y$ допустимі для прямої і двоїстої задач відповідно, а пункт 3 суперечить слабкій двоїстості.

Інакше, якщо $\lambda =0$, то з пункту 3 випливає, що або $y^{T}<0$, або $c^{T}(x_{p}-x_{m})>0$. У першому випадку двоїста програма необмежена, що суперечить розв'язності прямої. Це можна побачити так: припустимо, що $y_{f}$ — допустимий розв'язок двоїстої програми, оберемо довільне $\mu >0$ і розглянемо $y_{f}+\mu y$. Ця сума також є допустимим розв'язком двоїстої програми, оскільки $y_{f}+\mu y\geq 0$ і $(y_{f}+\mu y)^{T}A=y_{f}^{T}A+\mu y^{T}A=b^{T}$ і можна зробити $(y_{f}+\mu y)^{T}$ як завгодно великим вибравши відповідне $\mu$. Якщо $c^{T}(x_{p}-x_{m})>0$, то аналогічні доводи показують, що пряма задача необмежена, що також дає суперечність. $\square$

Див. також

• Умова Слейтера