最適化の勉強 その1

なんで書こうと思ったの

  • 目的
    • 最適化を使って学会発表するのに理解できてなくない?ということでアウトプットの意味で書く
    • ゴールは非線形最適化の概要を把握するのと、実際に研究で使ってるPythonライブラリのTNC法を理解すること
  • 構成
    1. 非線形最適化の概要
    2. 制約付きの場合
    3. Python.scipy.optimize()ライブラリの各アルゴリズムに関する説明(主にTNC)
  • 注意
    • 一応ブログとして書いてるけと個人の学習用なので悪しからず。
    • 文頭全部に「たぶん」が付く

1. 非線形最適化

降下法

非線形最適化問題の解法の概念として、降下法がある。

  1. ある点x^{k}から見て、目的関数が減少するような方向d^{k}を探す(部分問題)
  2. その方向に一定量進み、その点をx^{k+1}として1.に戻る

を繰り返す

各種アルゴリズムはこの考えに基づいている。 問題は、1.の目的関数が減少する方向をどう探すか。

最急降下法

探査方向ベクトルを

d^{k} = -\nabla f(x^{k})

とする方法。勾配の方向ってことは目的関数が減少する方向だよね。

目的関数の勾配ベクトルを求める必要がある。

Newton法

目的関数をx^{k}の周りでテイラー展開して二次に近似する。 するとその近似関数の最小値は探査方向として有用である。

最小値自体は目的関数の勾配ベクトルとヘシアンの逆行列で表せる。 つまり探査方向を求めるためにヘシアンの計算が必要。その計算が大変なのがデメリット。

共役方向

共役方向と呼ばれる方向がめっちゃいいらしい。 なんでかっていうと、この方向は変数変換したときに目的関数の等高線に対して直交で、まっすぐ解に進むから。 ちなみにここで言う「共役」は「複素共役」とかとは意味が違う。

Powell法

共役方向がめっちゃいいのは分かった。じゃあこの方向どうやって見つけるの?っていうのがこの方法。

共役勾配法

Powellで共役方向を求めながら最小化していく方法

まとめ

よく聞くNewton法とかCG法についてなんとなくわかった気になった。 次回は制約付きについて理解する

参考文献

今野 浩, 山下 浩 ,"非線形計画法", pp146-147,pp169-188