線形探索問題とは
ある一変数の関数の最小値や最大値を求めたい時には，
微分して極値を求めるのが基本ですが，
微分できないほど式が複雑な時は，
力ずくで探索するのも一つの手です．
このような一次元の探索を線形探索を言いますが、
線形探索アルゴリズムの中で有名なものに
黄金分割法があります．
これは探索空間をいわゆる黄金比という割合で狭めていって，
最小値 or 最大値を計算するロジックです．
詳しいロジックは下記のリンクを見ればわかると思います．
今回，この黄金分割法による線形探索アルゴリズムの
MATLABサンプルコードを作成してみました．
実行すると，冒頭のグラフのように
ある単峰性関数(赤線)の中の
最小値(青)を解析(微分情報)無しで探索できます．
ただ，単峰性を仮定しているので，
ある程度最適値の範囲がわかっていなければなりませんので，
そこは注意しましょう．
一般的に、このような線形探索を行うことは少ないですが、
この黄金分割法はニュートン法や最急降下法などの、
多次元の勾配法のステップパラメータ(学習率)
の最適化などに良く使用されているようです。
(下記の最急降下法のwikiにおいては、
αの値を逐次的に黄金分割法で最適化しながら
最適化を実施する)
MATLABサンプルコード
MATLABのサンプルプログラムは下記のGitHubリポジトリで公開されています。
MATLABRobotics/GoldenSectionMethod.m at master · AtsushiSakai/MATLABRobotics
