機械学習-数学学習メモ「最適化問題の解き方（凸最適化編）」
例えば最小二乗法。データの背後に隠れている関数を求める際に、実データとの誤差が最小となるように係数を求めることをします。
このように、ある関数を最大にしたり最小にしたりする解を求めることを最適化問題といいます。
今回はそんな最適化について学習したことをざっくりとまとめようと思います。（※細かい定義や証明は省略しています。ガバガバ注意。）
最適化問題とは
最適化問題とは | データ分析基礎知識
によると
最適化問題（Optimization Problem）とは、「与えられた制約条件の下で、ある目的関数を最大または最小にする解を求めること」をいいます。
とのことです。
先ほど言ったことですね。制約条件がない場合もあります。
凸最適化問題を解く際の流れ（制約条件なしの場合）
1.目的関数を一階微分して=0と置き、解く。（停留点を求める）
これにより極値の候補（停留点）が分かります。
微分によってグラフの傾きが分かりますが、その傾きが=0ということは、そこが山の頂上（極大値）か一番下（極小値）かの可能性が大きいということです。
このようにして、徐々に最適解を絞っていきます。
この時点で出た解は、まだ最適解の「候補」であることしか分かりません。
2.ヘッセ行列を求め、その定値性を調べる。
つぎに、二階偏微分係数を成分にとるヘッセ行列（ヘッセ行列 - Wikipedia）を求めます。
このヘッセの定値性を調べることで、最適解の候補が最小解（もしくは最大解）であることが判別できます。
ヘッセ行列が正定値、もしくは半正定値である場合、その停留点が極小値（=最小値）であることが分かります。
一方ヘッセ行列が負定値、もしくは半負定値の場合、その停留点が極大値（=最大値）であることが分かります。
ヘッセ行列が不定の場合は最適解ではないです。
なぜ極小値=最小値といえるか
ヘッセ行列が正定値（半正定値）の場合、目的関数が凸関数であることが分かるからです。
凸関数の場合、下の画像からも分かるように極小点＝最小点が成立します。
http://www.i.u-tokyo.ac.jp/news/focus/080215_1z2.shtmlより引用。
つまり、ヘッセの定値性を調べていたのは、関数の凸性を確認するためでもあります。
極大値=最大値の場合も、これの逆ですが同じ理屈によって成り立ちます。
