機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

ラグランジュの未定乗数法 - 等式制約

線形代数

1つの等式制約

変数{\bf x}の関数f({\bf x})の最大値、最小値は、{\bf x}に制約がなければ、

\begin{eqnarray} \nabla_{\bf x}f={\bf 0}\tag{1} \end{eqnarray}

を解いて得られます。{\bf x}に制約

\begin{eqnarray} g({\bf x})=0\tag{2} \end{eqnarray}

がある場合は、ラグランジュ乗数\lambdaを導入した

\begin{eqnarray} F=f({\bf x})-\lambda g({\bf x})\tag{3} \end{eqnarray}

を考え、これを{\bf x}で微分して={\bf 0}とおきます。

\begin{eqnarray} \nabla_{\bf x}f-\lambda\nabla_{\bf x}g={\bf 0}\tag{4} \end{eqnarray}

式(4)と式(2)を連立させて解けば、{\bf x}と\lambdaを定めることができます。
この解法をラグランジュ未定乗数法といいます。

ただし、この方法で求まるのは、一般に極値であり、それが最大値か、最小値か、
あるいはそれ以外の極大値、極小値(あるいは変曲点)であるかは、別に判定しなければならない。
しかし、問題の性質から最大値あるいは最小値がただ一つ分かっている場合には、非常に便利な方法です。

極値でfの等値面と曲面g=0が接する理由 - 1つの等式制約

式(4)はfの等値面と曲面g=0が接することを示していますが、これについては次のように考えるとよいです。

もし等値面と交差していれば、その曲面上でfの値が小さいほうから大きいほうへ、またはその逆に変化するので、
その点で極値を取らない。
ゆえに接していなければならない。

イメージを下図に示します。

f:id:olj611:20210829092655p:plain:w500

複数の等式制約

複数の制約

\begin{eqnarray} g_1({\bf x})=0,\ldots,g_m({\bf x})=0\tag{5} \end{eqnarray}

があるときf({\bf x})の最大、最小値(一般には極値)を求めるには、
各制約式それぞれにラグランジュ乗数\lambda_1,\ldots\lambda_mを導入して、

\begin{eqnarray} F&=&f({\bf x})-\lambda_1g_1({\bf x})-\cdots-\lambda_mg_m({\bf x})\\ &=&f({\bf x})-\langle{\boldsymbol \lambda},{\bf g}({\bf x})\rangle\tag{6} \end{eqnarray}

を考えます。
ただし、{\boldsymbol \lambda},{\bf g}({\bf x})は次のようにおきました。

\begin{eqnarray} {\boldsymbol \lambda}=\begin{pmatrix}\lambda_1\\ \vdots\\ \lambda_m\end{pmatrix},\ {\bf g}({\bf x})=\begin{pmatrix}g_1({\bf x})\\ \vdots\\ g_m({\bf x})\end{pmatrix}\tag{7} \end{eqnarray}

式(7)を{\bf x}で微分して={\bf 0}と置いた

\begin{eqnarray} \nabla_{\bf x}f-\langle{\boldsymbol\lambda},\nabla_{\bf x}{\bf g}({\bf x})\rangle={\bf 0}\tag{8} \end{eqnarray}

と式(5)を連立させて解けば、{\bf x}と\lambda_1,\ldots,\lambda_mを定めることができます。

ちなみに式(8)を変形させると次のようにも書けます。

\begin{eqnarray} &&\nabla_{\bf x}f-\sum_{j=1}^m\lambda_j\nabla_{\bf x}g_j={\bf 0}\\ &&\Leftrightarrow\nabla_{\bf x}\left(f-\sum_{j=1}^m\lambda_jg_j\right)={\bf 0}\tag{9} \end{eqnarray}

式(8)が成り立つ理由 - 複数の等式制約

制約条件g_1=0,\ldots,g_m=0のもとで、関数fが極値をとる時、式(8)が成り立つ理由は、次のように考えればよいです。
もし\nabla_{\bf x}fが\nabla_{\bf x}g_1,\ldots,\nabla_{\bf x}g_mの張る部分空間に含まれていなければ、
\nabla_{\bf x}がその部分空間に直交する成分を持つので、その方向は\nabla_{\bf x}g_1,\ldots,\nabla_{\bf x}g_mの全てに直交します。
すなわち、その方向はすべての制約曲面に接して、しかもその方向にfの勾配が0ではない。
したがって、その方向に移動すればfの値が増え、反対方向に移動すればfの値が減るので、fは極値をとらない。
ゆえに、fが極値をとるならそのようなことは起きない。

偉人の名言

f:id:olj611:20210829094024p:plain:w300
学問なんて、覚えると同時に忘れてしまってもいいものなんだ。
けれども、全部忘れてしまっても、その勉強の訓練の底に一つかみの砂金が残っているものだ。
これだ。
これが貴いのだ。
勉強しなければいかん。
太宰治

参考文献

線形代数セミナー p112-113
これなら分かる最適化数学 p63-77

動画

なし

目次へ戻る