ゼロからはじめる連続最適化

はじめまして。

本記事では、機械学習や制御、通信といった幅広い分野でよく用いられる連続最適化の基礎から応用までを綴ります。最適化問題はいつもライブラリを使って解いているけど、中で何が起こっているかわからない...などと感じている人向けのブログとなります。
ブログを書くきっかけとしては、自分自身の復習という意味合いが強いですが、誰かの参考になれば幸いです。

さて、早速ですが本記事で扱う最適化問題(optimization problem)の定義を以下に与えます。 

{min:f(x)}

{s.t.:g_i(x) \leq 0 (i=1,...,m),h_j(x) = 0 (j=1,...,l)}

 ここでminは最小化、s.t.は制約条件をあらわし、xはn次元決定変数、{f, g_i, h_j}はn変数の実数値関数をあらわします。すなわち、制約条件を満たす中で目的関数{f(x)}の値をもっとも小さくするようなxを求める問題となります。(最大化問題は、最小化問題の目的関数に-1をかけたものを解けば良いです)

 
上の式だけだとイメージがわきづらいと思います。そこで、分類や回帰でよく用いられるサポートベクターマシン(Support Vector Machine; SVM)を例に挙げます。例えば、ニクラス分類であれば、二つのクラス間の距離(マージン)が最大となるような境界を求めます。それは、以下の最小化問題としてあらわされます。

{min:\displaystyle \frac{1}{2} \|w\|^2}

{s.t.:y_i(w^T x_i + b) - 1 \geq 0}

(各変数の定義、問題の導出などは、そのうち書くSVMの記事で...) 
しかし、実際この問題をそのまま解くことよりも、以下の双対問題を解くことが多いですね。

{max:\sum_{i} \alpha_i -\frac{1}{2} \sum_{i, j} \alpha_i \alpha_j y_i y_j x_i x_j}

 なぜ、もとの問題(主問題)を解かずに双対問題を解くのか、そもそも主問題と双対問題の解の関係はどうなっているのか、など意外と知らずに解いている人もいるかもしれません。

本記事では、上述のような問題に答えるために特別な性質を持つ最適化問題、それを解くためのアルゴリズムを紹介したいと思います。また、先の予定としてはオンライン最適化、収束解析や機械学習の文脈でよく耳にする確率的降下勾配法(SGD)やAdam、Eveなどについても触れていければと考えています。

不定期更新ですがよろしくお願いします。
何かあればコメントやツイッターでお気軽にお声がけください。