線形計画法における双対定理を,Farkas の定理から導く証明にようやく成功した。ちょうど丸一週間費やしたことになる。
そもそも双対定理を Farkas の定理から導けるという話自体は知っていた。これは大ヒントであって,そういう意味では証明は九割がた済んでいたわけである。
初め,Farkas の定理を素朴に使ってみたところ,弱双対定理と呼ばれる,もっとずっと簡単に導ける不等式しか得られなかった。
考え始めてから四日目の朝,Farkas の定理の択一性がちゃんと利用できそうな定式化が思いついた。しかし,その時点ではまだ完全な証明に至らなかった。
それからさらに三日経った今日,ようやく最後のピースが埋まった。その最後のピースは結局のところ弱双対定理であった。
久々に新しいことを学んだ気がする。できればこのまま非線形計画法における基礎理論である KKT 条件と呼ばれるものや,凸汎関数の劣微分作用素へと進んでいきたいものである。その折には Minty の連立不等式の定理の別証明を考案するか,もしくは Grünbaum による証明の,4年前に理解できなかったところを理解したいものである。
なお,双対定理に話を戻せば,双対定理から Farkas の定理を導けることも知られており,それは実際,かなり容易である。この方針に立つ場合,Farkas の定理の実質的な内容である,凸集合の分離定理を用いずに双対定理を証明するわけで,おそらく Dantzig は自身が開発した単体法をうまく用いたのではないかと推測される。数多ある線形計画法のテキストの中にはその方針で先に双対定理を導いているものも多いように思われる。Farkas の定理の証明自体も,凸集合の分離という幾何学的な捉え方ではなく,掃き出し法のような純代数的な式変形と数学的帰納法によるものがある。そうした手法もやはり学ぶべきであろうから,きちんと取り組んだ際にはその手法を用いて双対定理が示せないか考えてみたいものである。
あとは von Neumann と Morgenstern のゲーム理論の古典的テキストの関連個所もついでに調査しようと思っている。特に Min-Max 定理との関連も見ておきたい。
私自身は数学の実務への応用にはほとんど関心がないが,例えばある問題に対する解をどう見出すかといった手続きを具体的に追及するという方向性には興味がある。それは構成的,もしくは操作論的な立場というものが気になっているからである。定理などの実際の内容に興味があるというより,その定理の内容をどう理解するかといったものの見方に強い関心があるのである。したがって,新しい定理を見出すよりも,よく知られている定理の別証明を考えたり,他の定理との関連を見出そうとすることばかりに気が向いてしまう。そういう意味ではプロの研究者には向いていないのであろう。最先端でバリバリ結果を出すよりも,古い文献に埋もれてあれこれ妄想している方が幸せなのである。
そもそも双対定理を Farkas の定理から導けるという話自体は知っていた。これは大ヒントであって,そういう意味では証明は九割がた済んでいたわけである。
初め,Farkas の定理を素朴に使ってみたところ,弱双対定理と呼ばれる,もっとずっと簡単に導ける不等式しか得られなかった。
考え始めてから四日目の朝,Farkas の定理の択一性がちゃんと利用できそうな定式化が思いついた。しかし,その時点ではまだ完全な証明に至らなかった。
それからさらに三日経った今日,ようやく最後のピースが埋まった。その最後のピースは結局のところ弱双対定理であった。
久々に新しいことを学んだ気がする。できればこのまま非線形計画法における基礎理論である KKT 条件と呼ばれるものや,凸汎関数の劣微分作用素へと進んでいきたいものである。その折には Minty の連立不等式の定理の別証明を考案するか,もしくは Grünbaum による証明の,4年前に理解できなかったところを理解したいものである。
なお,双対定理に話を戻せば,双対定理から Farkas の定理を導けることも知られており,それは実際,かなり容易である。この方針に立つ場合,Farkas の定理の実質的な内容である,凸集合の分離定理を用いずに双対定理を証明するわけで,おそらく Dantzig は自身が開発した単体法をうまく用いたのではないかと推測される。数多ある線形計画法のテキストの中にはその方針で先に双対定理を導いているものも多いように思われる。Farkas の定理の証明自体も,凸集合の分離という幾何学的な捉え方ではなく,掃き出し法のような純代数的な式変形と数学的帰納法によるものがある。そうした手法もやはり学ぶべきであろうから,きちんと取り組んだ際にはその手法を用いて双対定理が示せないか考えてみたいものである。
あとは von Neumann と Morgenstern のゲーム理論の古典的テキストの関連個所もついでに調査しようと思っている。特に Min-Max 定理との関連も見ておきたい。
私自身は数学の実務への応用にはほとんど関心がないが,例えばある問題に対する解をどう見出すかといった手続きを具体的に追及するという方向性には興味がある。それは構成的,もしくは操作論的な立場というものが気になっているからである。定理などの実際の内容に興味があるというより,その定理の内容をどう理解するかといったものの見方に強い関心があるのである。したがって,新しい定理を見出すよりも,よく知られている定理の別証明を考えたり,他の定理との関連を見出そうとすることばかりに気が向いてしまう。そういう意味ではプロの研究者には向いていないのであろう。最先端でバリバリ結果を出すよりも,古い文献に埋もれてあれこれ妄想している方が幸せなのである。
※コメント投稿者のブログIDはブログ作成者のみに通知されます