二週間前に数理計画法に対する興味が再燃し，いまだにくすぶっている。
といっても，もっとも基本といえる線形計画法ですら，高校で習う図解法以上の知識はまだない。
手当たり次第に線形計画法や凸計画法の解説書を眺めているのだが，どうも双対定理というのが重要らしい。そしてそれを証明するのに Farkas（ファーカスやファルカスと読みがふられる）の定理ないしは補題と呼ばれるものが利用されるらしい。
何冊か邦書をあたったところ，Farkas の定理は三通りの述べ方があることが判明した。もっと調べれば種類は増えるかもしれない。
その手の表現の一つは，以前から一松信氏の『極値問題』という著書で見かけていたのだが，その本自体をきちんと勉強していないのもあって，Farkas の定理が何なのか気にはなるものの謎のままであった。原文ママではないが，次のような表現である。
以下では，A は n 行 m 列の実行列，x は m 行の縦ベクトル，y は n 列の横ベクトル，c は m 列の横ベクトル，b は n 行の縦ベクトルとする。縦と横がややこしいが，何度もグルグル考えているうちに慣れる。
正直，こう書いていてもいったい何を言っているのか全くピンと来ない。しかし，二つの条件を論理式で書き表し，形式的に式変形することで，今野浩氏の線形計画法のテキストにある次の表現と同じであることが判明した（やはり引用は原文ママではなく，勝手に脚色した）。
ことここに至ってようやく，2年半前に自分なりに理解した択一定理そのものであることが判明した。そして，他の数理計画法のテキストの中には，私の過去記事で述べたような幾何学的解釈や証明がそっくりそのまま書かれていることもすぐに判明した。
こうしてようやく Farkas の定理というものが得体のしれない不気味な定理ではなく，自分にとっては極めて意味の明白な親しみさえ感じる定理になったのでる。「Farkas の定理はトモダチ」という気分である。
それから二年半を経た今，関心はようやく少し先へと進んだ。思えば当時も gk 氏に線形計画法の「双対定理」なるものを教わった気がするのだが，それを再び思い出すきっかけが最近あったのであった（そしてその原因を作ったのはやはり gk 氏であった）。
線形計画問題の標準形とは次のようなものである。
主問題：
minimize cx,
subject to Ax=b and x≧0.
そしてこれに対する双対問題と呼ばれるものが
maximize yb,
subject to yA≦c
である。
そして双対定理というのは，他方の問題に解があれば，つまり，例えば主問題に最小値があれば，双対問題の最大値も存在し，しかも両者は一致するという，きれいだけれどもなんだか不思議な定理である。
この双対定理は Farkas の定理を用いて示せるという噂なので，その大ヒントを頼りに証明を試み，四日間ほど経ったが，あと一歩というところで躓いている。
ところで，例によって理論そのものに真面目に取り組むよりも歴史などに関心が移ってしまう私にとって，うってつけというか禁断の書というか，そちらの方面の大家である今野浩氏の『ヒラノ教授の線形計画法物語』（岩波書店）という，とても素敵な本が見つかってしまった。
その本の第4章に双対定理のことが書かれている。私自身，双対問題というもの自体がどう発見されたのか気になっていたのだが，単体法という，線形計画法に対する標準的な手法の一つとなっている方法を発見したばかりの，三十代前半の若かりし Dantzig（ダンツィク）が，自分の開発した単体法について von Neumann にお伺いを立てたのが発端だったそうである。ちょうどゲームの理論でミニマックス定理と呼ばれるものを考えていた von Neumann が双対定理の成立を予想したという。
そして，その次のくだりが肝心なのだが，von Neumann のお告げを聞いた Dantzig はその後間もなく双対定理の証明に成功した，とある。また，それとは独立に，数年後に Gale, Kuhn, Tucker の三人組も双対定理を証明して発表したという。
Wikipedia の英語版の Farkas' lemma の項目で参考文献に挙げられている
CFM13
所収の19番目の記事がそれに該当するのではないかと思うのだが，ちゃんと見てない。GKT 論文のすぐ次の20番目の Dantzig の論文の題目も非常に気になるところであるが。
ここまで長々と書いてきたが，この記事の真の目的は，実は，その貴重な文献のリンクを残しておくことであった。
ちなみに，Gale という人は2年半前の記事で言及した "The Theory of Linear Economic Models" の著者であることは言うまでもない。
といっても，もっとも基本といえる線形計画法ですら，高校で習う図解法以上の知識はまだない。
手当たり次第に線形計画法や凸計画法の解説書を眺めているのだが，どうも双対定理というのが重要らしい。そしてそれを証明するのに Farkas（ファーカスやファルカスと読みがふられる）の定理ないしは補題と呼ばれるものが利用されるらしい。
何冊か邦書をあたったところ，Farkas の定理は三通りの述べ方があることが判明した。もっと調べれば種類は増えるかもしれない。
その手の表現の一つは，以前から一松信氏の『極値問題』という著書で見かけていたのだが，その本自体をきちんと勉強していないのもあって，Farkas の定理が何なのか気にはなるものの謎のままであった。原文ママではないが，次のような表現である。
以下では，A は n 行 m 列の実行列，x は m 行の縦ベクトル，y は n 列の横ベクトル，c は m 列の横ベクトル，b は n 行の縦ベクトルとする。縦と横がややこしいが，何度もグルグル考えているうちに慣れる。
yA≦0 を満たす任意の y に対して必ず by≦0 となるための必要十分条件は，x≧0 かつ Ax=b を満たす x が存在することである。
正直，こう書いていてもいったい何を言っているのか全くピンと来ない。しかし，二つの条件を論理式で書き表し，形式的に式変形することで，今野浩氏の線形計画法のテキストにある次の表現と同じであることが判明した（やはり引用は原文ママではなく，勝手に脚色した）。
Ax=b かつ x≧0 である x が存在することと，yA≦0 かつ by＞0 を満たす y が「存在しないこと」とは同値である。
ことここに至ってようやく，2年半前に自分なりに理解した択一定理そのものであることが判明した。そして，他の数理計画法のテキストの中には，私の過去記事で述べたような幾何学的解釈や証明がそっくりそのまま書かれていることもすぐに判明した。
こうしてようやく Farkas の定理というものが得体のしれない不気味な定理ではなく，自分にとっては極めて意味の明白な親しみさえ感じる定理になったのでる。「Farkas の定理はトモダチ」という気分である。
それから二年半を経た今，関心はようやく少し先へと進んだ。思えば当時も gk 氏に線形計画法の「双対定理」なるものを教わった気がするのだが，それを再び思い出すきっかけが最近あったのであった（そしてその原因を作ったのはやはり gk 氏であった）。
線形計画問題の標準形とは次のようなものである。
主問題：
minimize cx,
subject to Ax=b and x≧0.
そしてこれに対する双対問題と呼ばれるものが
maximize yb,
subject to yA≦c
である。
そして双対定理というのは，他方の問題に解があれば，つまり，例えば主問題に最小値があれば，双対問題の最大値も存在し，しかも両者は一致するという，きれいだけれどもなんだか不思議な定理である。
この双対定理は Farkas の定理を用いて示せるという噂なので，その大ヒントを頼りに証明を試み，四日間ほど経ったが，あと一歩というところで躓いている。
ところで，例によって理論そのものに真面目に取り組むよりも歴史などに関心が移ってしまう私にとって，うってつけというか禁断の書というか，そちらの方面の大家である今野浩氏の『ヒラノ教授の線形計画法物語』（岩波書店）という，とても素敵な本が見つかってしまった。
その本の第4章に双対定理のことが書かれている。私自身，双対問題というもの自体がどう発見されたのか気になっていたのだが，単体法という，線形計画法に対する標準的な手法の一つとなっている方法を発見したばかりの，三十代前半の若かりし Dantzig（ダンツィク）が，自分の開発した単体法について von Neumann にお伺いを立てたのが発端だったそうである。ちょうどゲームの理論でミニマックス定理と呼ばれるものを考えていた von Neumann が双対定理の成立を予想したという。
そして，その次のくだりが肝心なのだが，von Neumann のお告げを聞いた Dantzig はその後間もなく双対定理の証明に成功した，とある。また，それとは独立に，数年後に Gale, Kuhn, Tucker の三人組も双対定理を証明して発表したという。
Wikipedia の英語版の Farkas' lemma の項目で参考文献に挙げられている
CFM13
所収の19番目の記事がそれに該当するのではないかと思うのだが，ちゃんと見てない。GKT 論文のすぐ次の20番目の Dantzig の論文の題目も非常に気になるところであるが。
ここまで長々と書いてきたが，この記事の真の目的は，実は，その貴重な文献のリンクを残しておくことであった。
ちなみに，Gale という人は2年半前の記事で言及した "The Theory of Linear Economic Models" の著者であることは言うまでもない。
※コメント投稿者のブログIDはブログ作成者のみに通知されます