最適化問題の解法について１

同期の留学生の子に最適化問題を解く手法を教えることとなった。

といっても自分も大して知っているわけではないので

今からつらつらと勉強していこうかと思う。

とりあえずは弊研究室御用達の「黄金分割法」から。

wikiの引用で許されるのがブログの気楽なとこね。

ぶっちゃけwiki読んでしまえばそのままなのだが、

３点における値を見比べてより最少（最大）になりそうな区間を選び、

そこに新たな点を置いて、同様の作業を繰り返していくとやがて極値に至るというやつ。

これ、見るからにフクザツで非線形な関数を相手にする場合は

超時間がかかったり、ローカルオプティマムに嵌る気しかしないのだが…

と思って調べたら

岡山大の「微分を使わない最適化法」とかいうPDFがあった。

『凸関数でない場合、黄金分割法はうまく最適解を導けない可能性がある』

そう！それだよそれ！　それが言いたかったのだよ！

さらに言うなら初期探索区間βに対して区間がε以下になった時に終了するとすると

$k \geq \log{\frac{\sqrt{5}+1}{2}} \log{\frac{\beta}{\epsilon}}$

を満たすkが最低試行回数になるとか…（「＞」って\geqってうつんだね）

つまりまぁある程度以上早くならないということでもある。

同じところにあった「直接探索法」（単体法・シンプレックス法）の説明も端的にまとまっていて見やすい。

こちらは関数値のみを用いて探索できる簡単なアルゴリズムってのが利点だがそもそも極値に収束しない場合がある。

そんでもって微分とかもっとバンバン使うような手法はというと

この辺りとか結構詳しい。いつかMailsのESMとかもきちんと文にしてこっちに残しておきたいなぁと思いつつ。

そしたらHTMLより純粋にTex文で書いた方が楽だよなぁなんてことも。

とりあえずいろいろ遊べたのでまぁ今回はこの辺で。

粗大メモ置き場