しっかり学ぶ数理最適化・第２章３.１節 - 双対問題
双対問題
線形計画問題において、最適値を求めるのが困難な際に重要となるのが、最適値の上界と下界を求めることです。最大化問題において、ある実行可能解が得られた時、それは必ず最適値以下であるはずです。つまり得られた実行可能解を下界として捉えることができます。では上界を求めるにはどうすれば良いのでしょうか？上界を求める一つの手段として2.3.1節で述べられる双対問題による手法があります。双対問題を考えることで最大化問題を最小化問題に置き換えることができ、最適値の上界を求めることができるというなんとも不思議な求め方です。賢いですね。まあただ実行可能解を１つ得ることが容易でない問題もあるということで、世の中そんな甘くはなさそうですが...
本節では、やや天下り的な具体例から手法の流れを把握し、その後に一般化を行うことで双対問題を用いた最適値の上界・下界を求める手法に関してみていきます。
数式が非常に多くアレルギーが出そうになりましたがよくよく見てみると別に大した式じゃありません。数式ばかりに目がいきがちですが、著者の梅谷先生はこの節で行っていることを簡潔にまとめてくださってます。まとめると以下です。
制約条件の１次結合を用いて線形計画問題の最適値の良い上界を求めた
理解する前にこの文言を見ても「？」だったでしょうが、理解した後に聞くとなんとも簡潔な表現に聞こえます。後の2.3.2節では緩和問題に触れており、双対問題の導出にはこちらを利用することの方が多いようです。気が向いたらまとめます（多分向かない）
