担当授業のこととか,なんかそういった話題。

主に自分の身の回りのことと担当講義に関する話題。時々,寒いギャグ。

線形計画法の双対定理と Farkas の定理。

2016-10-19 22:58:51 | mathematics
線形計画法における双対定理を,Farkas の定理から導く証明にようやく成功した。ちょうど丸一週間費やしたことになる。

そもそも双対定理を Farkas の定理から導けるという話自体は知っていた。これは大ヒントであって,そういう意味では証明は九割がた済んでいたわけである。

初め,Farkas の定理を素朴に使ってみたところ,弱双対定理と呼ばれる,もっとずっと簡単に導ける不等式しか得られなかった。

考え始めてから四日目の朝,Farkas の定理の択一性がちゃんと利用できそうな定式化が思いついた。しかし,その時点ではまだ完全な証明に至らなかった。

それからさらに三日経った今日,ようやく最後のピースが埋まった。その最後のピースは結局のところ弱双対定理であった。

久々に新しいことを学んだ気がする。できればこのまま非線形計画法における基礎理論である KKT 条件と呼ばれるものや,凸汎関数の劣微分作用素へと進んでいきたいものである。その折には Minty の連立不等式の定理の別証明を考案するか,もしくは Grünbaum による証明の,4年前に理解できなかったところを理解したいものである。

なお,双対定理に話を戻せば,双対定理から Farkas の定理を導けることも知られており,それは実際,かなり容易である。この方針に立つ場合,Farkas の定理の実質的な内容である,凸集合の分離定理を用いずに双対定理を証明するわけで,おそらく Dantzig は自身が開発した単体法をうまく用いたのではないかと推測される。数多ある線形計画法のテキストの中にはその方針で先に双対定理を導いているものも多いように思われる。Farkas の定理の証明自体も,凸集合の分離という幾何学的な捉え方ではなく,掃き出し法のような純代数的な式変形と数学的帰納法によるものがある。そうした手法もやはり学ぶべきであろうから,きちんと取り組んだ際にはその手法を用いて双対定理が示せないか考えてみたいものである。

あとは von Neumann と Morgenstern のゲーム理論の古典的テキストの関連個所もついでに調査しようと思っている。特に Min-Max 定理との関連も見ておきたい。

私自身は数学の実務への応用にはほとんど関心がないが,例えばある問題に対する解をどう見出すかといった手続きを具体的に追及するという方向性には興味がある。それは構成的,もしくは操作論的な立場というものが気になっているからである。定理などの実際の内容に興味があるというより,その定理の内容をどう理解するかといったものの見方に強い関心があるのである。したがって,新しい定理を見出すよりも,よく知られている定理の別証明を考えたり,他の定理との関連を見出そうとすることばかりに気が向いてしまう。そういう意味ではプロの研究者には向いていないのであろう。最先端でバリバリ結果を出すよりも,古い文献に埋もれてあれこれ妄想している方が幸せなのである。
ジャンル:
ウェブログ
コメント   この記事についてブログを書く
この記事をはてなブックマークに追加
« 線形計画法の双対定理。 | トップ | <読書感想文1601> ヒラノ教... »
最近の画像もっと見る

コメントを投稿


コメント利用規約に同意の上コメント投稿を行ってください。

数字4桁を入力し、投稿ボタンを押してください。

あわせて読む

トラックバック

この記事のトラックバック  Ping-URL
  • このブログへのリンクがない記事からのトラックバックは受け取らないよう設定されております。
  • ※ブログ管理者のみ、編集画面で設定の変更が可能です。