最適化問題

最適化問題とは？

定められた条件下で目的関数を最大化あるいは最小化する解を求める問題のこと。

例えば、連続関数の最大化問題であれば、一般的に次のように書ける。

$ \hat{\theta}=argmax{\tinyθ}f(θ)

例

この問題の困難さは関数fの形状やパラメータθの数による。

$ f(θ)=-θ^2+2θ-1

あれば、一階微分を取り、0と置くことで、

$ -2θ+2=0

θ＝１が全体最適解であることは高校数学でも分かる。

しかし、現実の問題はここまで簡単に解ける問題では無いので、問題に合わせてさまざまな最適化のテクニックが存在する。

関数の形状に注目

凸問題

全体に１つ大きな峰があり、関数のどの位置にいようが全体最適解の方向が局所的な情報（微分情報）からわか　るという特性を持つ。

全体最適解を計算するのが楽。

非凸問題

現実の問題は局所最適解を持つことが多い。

全体最適解ではないものの、局所的に最適解になっているものを局所最適解と呼ぶ。

https://gyazo.com/ae990dae72f1abe0dba00bb2d9046e0f

引用

大学4年間のデータサイエンスが10時間でざっと学べる , 久野 遼平 (著), 木脇 太一 (著), KADOKAWA (2018/3/29)