しっかり学ぶ数理最適化の演習解説ー2.8:弱双対定理からファルカスの補題を示す
線形計画問題の弱双対定理から、ファルカスの補題を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.8である。解答は自己流なので間違っていたらご容赦ください。弱双対定理およびファルカスの補題については、下記を参照のこと。
su-butsu-kikaigakusyuu.hatenablog.com
以下、証明
ファルカスの補題の(1)が成り立つとき、(2)が成り立たないことを示す
(1)の仮定の下では、主問題
は実行可能解を持つ。ここで、特にとすると、これの双対問題は
となる。
よって、を仮定すると、このは双対問題の実行可能解となる。よって、弱双対定理より、
が成り立つ。従って、とを満たすようなは存在せず、ファルカスの補題の(2)が成り立たないことが示された。
ファルカスの補題の(2)が成り立つとき、(1)が成り立たないことを示す
(2)の仮定の下では、双対問題
は実行可能解を持つ。この解をとすると、これを正定数倍したもまた上記の制約を満たすため実行可能解となる。
今、(2)の仮定によりであるため、はとすればに発散し、上記の双対問題は非有界となる。
弱双対定理の系により、「主問題と双対問題のいずれか一方が非有界なら、他方は実行不能となる」ため、
主問題
は実行不能となる。よって、ファルカスの補題の(1)が成り立たないことが示された。
以上により、ファルカスの補題が示された。