Nelder-Mead method - yasuhisa's blog

去年の最適化理論の課題は、準ニュートン法あたりを実装してバナナ関数に適用して軌跡書いてね、というようなものだった(はず)だけど、今年は微妙に違う。今年はNelder-Mead methodというのを使ってバナナ関数で遊んでね、というものに変わった。

wikipedia:en:Nelder-Mead_method

Nelder-Mead methodというのはヘッセ行列どころか勾配も使わない非線形最適化手法の一つ。(まだちゃんと追ってないけど)探索してきた点を覚えておいて、その中で最悪の点、最良の点、重心などからシンプレックス(幾何学的な図形)の各頂点を構成していく。で、4つくらいの操作を繰り返しながら探索をしていく。こんなんで(局所)最適解に収束してくれるんかいなとかなり疑心暗鬼なのだが、案の定収束はかなり遅いらしい。。。この手法が理論的にどういうことが言えるのかはレポート出すときにでもちょっと調べてはみる予定(でもなんかGAっぽい)。

先生から渡された論文も1960年代に出された頃の論文で、上に書いたように何か特別いい性質があるような感じもしなかったのでなんで今この手法をやらせるのかよく分からなかったけど、どうやら解くべき問題の変数がでかくなってきていることが絡んできているようだ。何百万、何千万、もしくはそれ以上の変数での非線形最適化問題において、ヘッセ行列どころか勾配を計算するのも大変＞＜という事態らしく、勾配を使わない手法ということで近年また注目を集めてきているそうだ(もちろんもうちょっとsophisticateされた形でだけど)。最適化理論のほうを追っているわけではないから詳しくないけど、学習理論のほうでパーセプトロンが再び脚光を浴びているのと似たような印象。

ところで、Rの汎用的な最適化関数としてoptimという関数がある。最適化手法として準ニュートン法、共役勾配法などを選択することができるが、ディフォルトのmethodとしてこのNelder-Mead methodが指定されているのをhelp読んでて気がついた。勾配ベクトルを引数に渡さなくてよいので、確かに楽ではある。汎用という意味ではディフォルトになっているのもある意味納得。まあ、しかし収束のスピードとかその手法の持つ性質を(ある程度)ちゃんと理解して使わないとpracticalなところでも影響がありまくりなので、ちゃんと理論勉強しようと思います。