ラグランジュ双対問題の歴史
ラグランジュ双対問題の歴史
SVM の導出を眺めていると双対問題の話になり、その後いきなり「ラグランジュ関数」なる謎の関数が出てきていつも「どっから出てきたのおまえ？」となる。計画問題、凸最適化に関する専門書や記事を読んでも毎回天下り的に導入されるし、誰がいつなんでどこからこいつを持ってきたのかがまったくわからない。
というわけで調べてみたところ、どうやら Euler や Lagrange が創始した解析力学の変分法の技術を von Neumann、Kuhn、Tucker あたりの誰かが計画問題に持ち込んだのが始まりではないかと思われるが、歴史が古すぎたり、肝心の最初の論文が機密扱いでネットに資料がないので詳しいことはわからなかった。
計画問題の歴史
記録に残っている範囲だけでも 1826 年には Fourier が線形不等式問題を解こうとしていたようなので、ちらほらと研究されていたようだが、現在の形に至ったのは第二次世界大戦中の軍事研究に端を発する。
その用途は「軍のコストを減らし、敵の損失を増やすために、支出とリターンを計画するため」とされており、1947年まで軍事機密とされた。その後、様々な分野に適用されて人々の暮らしに大きく貢献したので、計画問題の先駆けとなったソ連の Kantorovich とオランダ系アメリカ人の Koopsman は 1975 年にノーベル経済学賞を受賞している。
計画問題にもっとも大きな貢献を成したと言われているのは George B. Dantzig である。彼は 1946-1947 年頃、同様に米空軍で線形計画を用いた問題の解決に当たっていた。
Dantzig が線形計画法の解法であるシンプレックス法について von Neumann に説明すると、von Neumann はいま自分が研究しているゲーム理論の問題と等価であることに即座に気がついた。その後 Dantzig はシンプレックス法、von Neumann は双対問題に関する論文をそれぞれ発表している。
Dantzig は『Linear Programming and Extensions』で、この分野の数学的基礎を築いたのは誰よりも von Neumann の功績が大きいとしており、その後、理論的な整備を進めた Kuhn と Tucker も『JOHN VON NEUMANN'S WORK IN THE THEORY OF GAMES AND MATHEMATICAL ECONOMICS』でこれを認めている。von Neumann と Morgenstern の『ゲーム理論と経済行動』は線形不等式問題に関する数学的な基礎付けのヒントとなり、中でも二人ゼロ和ゲームのミニマックス定理は、非線形計画の双対定理に密接な関係があった。
Kuhn と Tucker は 1951 年の『Nonlinear Programming』で計画問題を現在の形にほぼ完成させた。実はその後 1931 年に Karush が修士論文で非線形計画の重要な必要条件を発見していたことがわかり、有名な Karush-Kuhn-Tucker 条件にまとまった。
参考
解法の歴史
Kuhn と Tucker の『Nonlinear Programming』では、計画問題をラグランジュの未定乗数法による停留点探索に変換する方法について Courant と Hilbert の論文を参照している。その論文がネット上では見つからなかった。また、von Neumann の 1947 年の双対問題に関する論文は非公開である。よってこれ以上は歴史を辿ることができない。結局、von Neumann、Kuhn、Tucker のうち、誰がラグランジュの未定乗数法を持ち出したのかはわからなかった（ご存知の方がいらっしゃいましたら教えてくださると幸いです）。
さて、このラグランジュ関数の歴史だが、調べたところ物理学の Euler-Lagrange 方程式あたり、つまり Euler と Lagrange が生きていた 1750 年あたりまで話が遡る。当然ネット上に文献は残っていないし、私が物理にあまり詳しくないため以下の説明が合っているかわからない。
ラグランジュ力学において力学系の作用を記述する関数がラグランジュ関数（ラグランジアン）である。また、このラグランジュ形式で変分原理（最小作用の原理）にしたがって、実際に力学系が取りうる軌道を求めるための手法のひとつがラグランジュの未定乗数法である。
ラグランジュの未定乗数法はおそらく制約条件付きのラグランジュ方程式を解く[1]ために考案されたものだが、数学的に有用でいろいろな場面に応用できるので、いまとなっては分野をまたいで広く知られている。
制約付き連続最適化問題の最小値（または最大値）を知りたい線形計画問題、非線形計画問題にもラグランジュの未定乗数法は応用されることになった。なぜならば最小値（最大値）は問題の停留点でもあるから、停留点をすべて求めることができるラグランジュの未定乗数法を使えば、最適解の候補が見つかるからである（凸最適化問題ならドンピシャで最適解が求まる）。
新たに生じた疑問としては、このラグランジュの未定乗数法、今でこそ有名だが計画問題に導入された 1950 年頃はどうだったのだろうかという点である。もとから有名だったから必然的に計画問題に持ち込まれたのか、計画問題でめちゃくちゃ役に立つことがわかったから広く知られるようになったのか、どっちなんだろう。主成分分析は 1901 年に発明された手法だが、それを解くためにも使われたわけだから、当時から有名だったのかもしれない。
ともあれ謎の「ラグランジュ関数」はどこから出てきた？ という問いはラグランジュ未定乗数法、果てはラグランジュの解析力学まで遡れるのだ、という結論が出たあたりでこの話はおしまいとしよう。
情報提供お待ちしております。この辺りの歴史に詳しい方がいらっしゃいましたら、ぜひ教えていただけると嬉しいです。
ちゃんと読めてないけど参考文献
「Euler-Lagrange 方程式あたりとの関係が書いてありそうで古い」を条件に探して辿り着いた文献。もっといい文献を見つけたらあとで差し替えます。
-
ここでいう制約条件とは、物理学では束縛条件や拘束条件とも呼ばれる。たとえばお碗の中を転がるビー玉がそのお碗の曲面に沿って運動せざるを得ないとか、滑車を介して二つの物体が紐で結ばれているから一緒に運動せざるを得ないといった、物体が運動できる範囲に制限がある場合にその制限を記述したものが束縛条件である。 ↩︎
Discussion