最適化の勉強 その1
なんで書こうと思ったの
- 目的
- 構成
- 注意
- 一応ブログとして書いてるけと個人の学習用なので悪しからず。
- 文頭全部に「たぶん」が付く
1. 非線形最適化
降下法
- ある点から見て、目的関数が減少するような方向を探す(部分問題)
- その方向に一定量進み、その点をとして1.に戻る
を繰り返す
各種アルゴリズムはこの考えに基づいている。 問題は、1.の目的関数が減少する方向をどう探すか。
最急降下法
探査方向ベクトルを
とする方法。勾配の方向ってことは目的関数が減少する方向だよね。
目的関数の勾配ベクトルを求める必要がある。
Newton法
目的関数をの周りでテイラー展開して二次に近似する。 するとその近似関数の最小値は探査方向として有用である。
最小値自体は目的関数の勾配ベクトルとヘシアンの逆行列で表せる。 つまり探査方向を求めるためにヘシアンの計算が必要。その計算が大変なのがデメリット。
共役方向
共役方向と呼ばれる方向がめっちゃいいらしい。 なんでかっていうと、この方向は変数変換したときに目的関数の等高線に対して直交で、まっすぐ解に進むから。 ちなみにここで言う「共役」は「複素共役」とかとは意味が違う。
Powell法
共役方向がめっちゃいいのは分かった。じゃあこの方向どうやって見つけるの?っていうのがこの方法。
共役勾配法
Powellで共役方向を求めながら最小化していく方法
まとめ
よく聞くNewton法とかCG法についてなんとなくわかった気になった。 次回は制約付きについて理解する
参考文献
今野 浩, 山下 浩 ,"非線形計画法", pp146-147,pp169-188