把握しておきたい最適化数学の基本 〜問題の定義、線形計画法、勾配法 etc〜

最適化の理解は統計学のメイントピックではないものの、「最適化」は概ね「最小値・最大値問題」となることから、統計学に関連する多くの導出で「最適化」の基本的な理解は必須であると思われます。
一方で、「最適化」の解説は各論を中心とするものが多く、特定の最適化の問題や手法を学ぶ目的以外では学習にかかるコストの面で適さない場合があるような印象を受けます。そのため当記事では、最適化に関しての概論をまとめることで、統計を理解するにあたって知っておくとよい前提知識が得られるように試みました。

なぜ「最適化」の基本を学んでおくべきか

そもそもそれほど難しくない

「最適化」と聞くと難しい印象を受けるかもしれませんが、基本的な内容については高校数学の「平方完成」や「微分」で取り扱っている「最大値・最小値問題」とさほど違いはありません。「最適化」を直感的に解釈するなら「一番良いと思われる条件を探す」と言い換えられると思いますが、「一番良い」を客観的に評価するにあたっては何らかの関数が必要で、その関数の「一番高い値=最適」と考えるなら、「最適化」は「関数の最大値問題または最小値問題」に置き換えられます。

「最適化」について把握していない方は「最適化=難しそうな手法」と考えるかもしれませんが、「手法自体」はむしろ単純で、「実際の事例をいかに最大値・最小値問題に変換するか」が最適化を理解する上で最も重要です。

具体的な例がある方がわかりやすいので、最適化の簡単な例をご紹介します。「コストを$x$費やした際の結果の期待値が$y = x(2-x) \quad (0 \leq x \leq 2)$となるとき、最適な期待値を得るにあたってのコストを求めよ」という例について以下考えます。
$$
\large
\begin{align}
\frac{\partial y}{\partial x} = -2x + 2
\end{align}
$$
上記において、$-2x+2=0$を解くと$x=1$であるため、この例においては最適なコストは$x=1$と考えることができます。

ここで取り扱った最適化の例は「微分を用いた最大値問題の解法」を用いて最適なコストを求めましたが、このように最適化問題の多くは「関数の最大値問題」に帰着することができます。そのため、そもそもそれほど難しくないことが多いことには注意しておくと良いです。

適用範囲が広い

最適化は単体で完結する分野というよりも、多くの他の分野の導出のベースに用いられることが多いです。「統計学」もその一つであり、具体的には尤度を最大にするパラメータを計算する最尤法も「最適なパラメータを求める問題」と考えることができます。

最尤法だけにとどまらず、フィッシャーの線形判別や主成分ベクトルの導出などにあたっても最適化が用いられます。1変数に関する最大化だけでなく、複数の変数やベクトルの向きに関する最大化・最適化も統計学では活用されます。

都度追うよりまとめて掴んだ方が簡単

統計学の理論の導出にあたって現れる「最適化」の手法は毎回同じパターンである一方で、理論の導出にあたっての問題設定は毎回異なります。よって、都度最適化に関してメイントピックの導出と同時に理解すると負担が大きくなります。

たとえばフィッシャーの線形判別では、「郡内分散と郡間分散の定義」、「共分散行列を用いた二次形式の表記」、「ベクトルの向きに関する最適化」によって主に構成されますが、最適化以外の導出も少々複雑なため、「最適化」を別枠で抑えておけば最大化する指標の定義の理解に注力することができます。

また、多くのトピックで「指標の定義」と「最大化」で理論的な導出がなされるため、「最適化」という概念を抑えておくことで、導出の流れのパターンについて予め把握した上で導出を追うことが可能になります。このことで導出の全体像を掴み、理解のスピードを早めることができます。

最適化の基本トピック

目的関数の定義

最適化を考えるにあたって特に重要なのが「目的関数(Objective)の定義」です。要するに「変数の値が良いかどうかについて評価するための関数」を定義する必要があるということです。
$$
\large
\begin{align}
Objective: \quad f(x) = x(2-x) \to Maximize
\end{align}
$$
冒頭の例だと上記のように目的関数の$f(x)$を記載することができます。

このような表記・レイアウトを用いることで、最適化問題について考える際に説明を省略することができるため、非常に有用です。数式を見ると難しいと考える人も多いかもしれませんが、単に説明を省略することで本来の問題以外をなるべく考えなくて良くなると理解すれば良いと思います。

制約条件

「目的関数」に対して同じく重要なのが「制約条件(Constraint)」です。「制約条件」は数学の最大値問題において「定義域を定める」ということに対応しています。「制約条件」を考えるとたとえば下記のような問題が設定されます。
$$
\large
\begin{align}
Objective &: \quad f(x) = -x^2 + 3 \to Maximize \\
Constraint &: \quad 1 \leq x \leq 5
\end{align}
$$
二次関数$f(x)=-x^2$の形状から関数の最大値は$f(1)=-1+3=2$となります。よって、$x=-1$が目的関数を最大化する変数の値となります。

ラグランジュの未定乗数法

制約条件の取り扱いにあたって、関数や制約条件が複雑な場合などがあります。この際はラグランジュの未定乗数法を用いることが多いです。

概要は下記で取り扱いました。ラグランジュの未定乗数法自体の理解は少々難しいですが、複雑な導出ではよく出てくるので、原理の理解は後回しにしても手法だけは必ず抑えておくと良いと思います。
https://www.hello-statisticians.com/explain-terms-cat/pca1.html#i-4

ラグランジュの未定乗数法は下記にまとめましたので、詳しく知りたい方は下記も確認してみてください。
https://www.hello-statisticians.com/explain-terms-cat/lagrange1.html

基本的には使い方だけは抑えてはおくべきだと思いますので、原理の理解が難しい場合は使い方だけを抑えるようにしましょう。