Nelder-Mead methodの軌跡

教習所にも通うことになったので、さっさと課題片づけておくかーと思って、Nelder-Mead methodの実装を開始。すぐ終わった。どんな方法かは下に書いた。

• Nelder-Mead method - yasuhisa's blog

すぐ終わった、だけどこれ多変数最適化の手法であることを考えるとかなり実装がしやすい手法ですね。ヘッセ行列どころか勾配すらいらないし。まあ、そういう情報すら使わないので、ちゃんと収束するんかいな、、、というのが不安だったので、色々実験してみました。コードはレポート提出期限が過ぎてからうpする予定でおります、はい。

Nelder-Mead methodでは初期点というのが一つではなく、N次元の最適化問題だったら、N+1個以上の初期点を選んでずんどこ動いていきます。それらの点を

• 反射
• 拡大
• 縮小
• 収縮

と呼ばれる操作を繰り替えしながら、ずんどこずんどこ。2変数の無制約最小化問題で、3つの初期点(単体、というらしい)がどう動いていくかをplotしたのがこんな感じの図。


(1, 1)が最適化で、収束するまではplotしてませんが、単体の初期値や、さっき書いた4つの操作をするときのパラメータにはそれほど依存せず、大域的最適解に収束しているような感じでした。

まあ、もちろんパラメータや初期値によっては収束のスピードは違いますが、ちゃんとそれっぽい方向に動いてくれているというのが分かってちょっと関心しました。まあ、早くはないです。はい。

あと収束の判定条件が結構微妙。ニュートン法とかのように前回の関数値や点の差のノルムを取ると、初期の場合でもその条件を突破してしまうことがあるので、わりと特殊な感じになりそうな。iterationの最大回数決めといて、そこで強制打ち切りというのもわりと普通かもしれない。

コードはこちら。
www.yasuhisay.info

これなら分かる最適化数学―基礎原理から計算手法まで