ChunPom’s diary

数学、物理、機械学習に関する話題。あと院試、資格、大学入試まで。

しっかり学ぶ数理最適化の演習解説ー2.8:弱双対定理からファルカスの補題を示す

 線形計画問題の弱双対定理から、ファルカスの補題を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.8である。解答は自己流なので間違っていたらご容赦ください。弱双対定理およびファルカスの補題については、下記を参照のこと。

su-butsu-kikaigakusyuu.hatenablog.com

 

以下、証明

ファルカスの補題の(1)が成り立つとき、(2)が成り立たないことを示す

 (1)の仮定の下では、主問題

{\displaystyle  max_{\boldsymbol{x}}\  \boldsymbol{c}^{T} \boldsymbol{x} \ \ s.t. \  A \boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}}

は実行可能解を持つ。ここで、特に{\displaystyle \boldsymbol{c} =\boldsymbol{0}}とすると、これの双対問題は

{\displaystyle  min_{\boldsymbol{y}}\  \boldsymbol{b}^{T} \boldsymbol{y} \ \ s.t. \  A^T \boldsymbol{y} \geq \boldsymbol{0}}

となる。

よって、{\displaystyle A^T \boldsymbol{y} \geq \boldsymbol{0}}を仮定すると、この{\displaystyle \boldsymbol{y}}は双対問題の実行可能解となる。よって、弱双対定理より、

{\displaystyle  \boldsymbol{b}^{T} \boldsymbol{y} \geq  \boldsymbol{c}^T \boldsymbol{x} = 0}

が成り立つ。従って、{\displaystyle A^T \boldsymbol{y} \geq \boldsymbol{0}}{\displaystyle \boldsymbol{b}^T \boldsymbol{y} \lt 0}を満たすような{\displaystyle \boldsymbol{y}}は存在せず、ファルカスの補題の(2)が成り立たないことが示された。

 

ファルカスの補題の(2)が成り立つとき、(1)が成り立たないことを示す

 (2)の仮定の下では、双対問題

{\displaystyle  min_{\boldsymbol{y}}\  \boldsymbol{b}^{T} \boldsymbol{y} \ \ s.t. \  A^T \boldsymbol{y} \geq \boldsymbol{0}}

は実行可能解を持つ。この解を{\displaystyle \boldsymbol{y}}とすると、これを正定数倍した{\displaystyle \boldsymbol{y}'=\lambda \boldsymbol{y}}もまた上記の制約を満たすため実行可能解となる。

 今、(2)の仮定により{\displaystyle \boldsymbol{b}^T \boldsymbol{y} \lt 0}であるため、{\displaystyle  \boldsymbol{b}^T \boldsymbol{y}'=\lambda \boldsymbol{b}^T \boldsymbol{y}}{\displaystyle \lambda \to \infty}とすれば{\displaystyle -\infty}に発散し、上記の双対問題は非有界となる。

弱双対定理の系により、「主問題と双対問題のいずれか一方が非有界なら、他方は実行不能となる」ため、

主問題

{\displaystyle  max_{\boldsymbol{x}}\  \boldsymbol{0}^{T} \boldsymbol{x} \ \ s.t. \  A \boldsymbol{x} = \boldsymbol{0}, \boldsymbol{x} \geq \boldsymbol{0}}

は実行不能となる。よって、ファルカスの補題の(1)が成り立たないことが示された。

 

以上により、ファルカスの補題が示された。