制約条件付き最適化問題におけるラグランジュの未定乗数法の導出と図形的解釈について

制約付き最適化問題の解法としてよく用いられる「ラグランジュの未定乗数法」だが、本論で議論されるというよりはAppendixなどで解説されることが多い。
当記事では「パターン認識と機械学習(PRML)」の上巻のAppendixを参考に、ラグランジュの未定乗数法の導出と図形的解釈について確認するものとする。

前提知識

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

https://www.hello-statisticians.com/explain-terms-cat/pca1.html#i-4
概要は上記にまとめた。

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

https://www.hello-statisticians.com/explain-terms-cat/pca1.html#i-6
ラグランジュの未定乗数法は上記のように主成分分析の導出などでも用いられる。多くの問題は制約付き最適化問題に帰着されることが多いので、ラグランジュの未定乗数法の応用例は非常に多い。

1変数関数のテイラー展開（復習）

まずは1変数関数のテイラー展開について復習する。関数$f$の$n$次の導関数を$f^{(n)}$とすると、$x=a$の周辺におけるテイラー展開は下記のようになる。
$$
\large
\begin{align}
f(x) &= \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n
\end{align}
$$

ここで$f^{(n)}(a)$は$x=a$における$f$の$n$次微分係数である。また、$a=0$においてはマクローリン展開と呼び、下記のように表す。
$$
\large
\begin{align}
f(x) &= \sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!}x^n
\end{align}
$$

具体的な関数のマクローリン展開については下記で取り扱った。

https://www.hello-statisticians.com/explain-terms-cat/maclaurin-seriese.html

2変数関数のテイラー展開

2変数のスカラー関数$f(x,y)$のテイラー展開について考える。点$(x,y)=(a,b)$の周辺におけるテイラー展開は下記のようになる。

2変数のスカラー関数$f(x,y)$のテイラー展開について考える。点$(x,y)=(a,b)$の周辺におけるテイラー展開は下記のようになる。
$$
\large
\begin{align}
f(x,y) &= \sum_{n=0}^{\infty} \frac{1}{n!} \left( (x-a)\frac{\partial}{\partial x} + (y-b)\frac{\partial}{\partial y} \right)^{n} f(x,y)|_{x=a,y=b}
\end{align}
$$

上記において、「$|_{x=a,y=b}$」は$f(x,y)$の偏微分の計算を先に行ってから$(x,y)=(a,b)$を代入するという意味合いで用いた。

またここで、$x$を$a+x$、$y$を$b+y$で置き換えて、下記のように表記することもできる。
$$
\large
\begin{align}
f(a+x,b+y) &= \sum_{n=0}^{\infty} \frac{1}{n!} \left( x\frac{\partial}{\partial x} + y\frac{\partial}{\partial y} \right)^{n} f(x,y)|_{x=a,y=b}
\end{align}
$$

当稿の作成にあたり参考にした「パターン認識と機械学習(PRML)」ではこの表記を主に用いているため、以下ではこちらの表記を用いる。

多変数関数のテイラー展開

$$
\large
\begin{align}
\mathbf{x} &= \left(\begin{array}{c} x_1 \\ \vdots \\ x_p \end{array} \right) \\
\mathbf{\epsilon} &= \left(\begin{array}{c} \epsilon_1 \\ \vdots \\ \epsilon_p \end{array} \right)
\end{align}
$$

上記で定義した$\mathbf{x}$、$\mathbf{\epsilon}$を用いて多変数のスカラー関数$f(\mathbf{\epsilon})$の$\mathbf{\epsilon}=\mathbf{x}$の周囲での一次のテイラー展開について考える。ここで2変数までと異なり$x$や$y$ではなく$\mathbf{\epsilon}$を変数としたのには注意が必要で、これも参考にした「パターン認識と機械学習(PRML)」の表記に合わせるにあたって変更した。
$$
\begin{align}
f(x_1+\epsilon_1, \cdots , x_p+\epsilon_p) &= \frac{f(\mathbf{x})}{0!} + \frac{1}{1!}\left( \epsilon_1\frac{\partial}{\partial \epsilon_1} + \cdots + \epsilon_p\frac{\partial}{\partial \epsilon_p} \right) f(\epsilon_1, \cdots , \epsilon_p)|_{\epsilon_1=x_1, \cdots , \epsilon_p=x_p} \\
&= \frac{f(\mathbf{x})}{0!} + \frac{1}{1!}\left( \epsilon_1\frac{\partial}{\partial \epsilon_1} + \cdots + \epsilon_p\frac{\partial}{\partial \epsilon_p} \right) f(x_1, \cdots , x_p) \\
&= \frac{f(\mathbf{x})}{0!} + \frac{1}{1!}\left( \epsilon_1\frac{\partial f(x_1, \cdots , x_p)}{\partial \epsilon_1} + \cdots + \epsilon_p\frac{\partial f(x_1, \cdots , x_p)}{\partial \epsilon_p} \right) \\
&= \frac{f(\mathbf{x})}{0!} + \frac{1}{1!}\left(\begin{array}{r} \epsilon_1 & \cdots & \epsilon_p \end{array} \right) \left(\begin{array}{c} \frac{\partial f(x_1, \cdots , x_p)}{\partial \epsilon_1} \\ \vdots \\ \frac{\partial f(x_1, \cdots , x_p)}{\partial \epsilon_p} \end{array} \right) \\
&= f(\mathbf{x}) + \mathbf{\epsilon}^{T} \nabla f(\mathbf{x})
\end{align}
$$

上記の導出にあたって$\nabla$は下記のように定義した。
$$
\large
\begin{align}
\nabla &= \left(\begin{array}{c} \frac{\partial}{\partial \epsilon_1} \\ \vdots \\ \frac{\partial}{\partial \epsilon_p} \end{array} \right)
\end{align}
$$
ここで導出した一次の多変数関数のテイラー展開を用いて、以下ではラグランジュの未定乗数法の導出と図形的解釈を行う。

ラグランジュの未定乗数法の導出と図形的解釈

制約条件が等号で与えられる場合

$$
\large
\begin{align}
\mathbf{x} &= \left(\begin{array}{c} x_1 \\ \vdots \\ x_p \end{array} \right) \\
\mathbf{\epsilon} &= \left(\begin{array}{c} \epsilon_1 \\ \vdots \\ \epsilon_p \end{array} \right)
\end{align}
$$

上記のように$\mathbf{x}$、$\mathbf{\epsilon}$を定義した際に、下記の最適化問題を考える。
$$
\large
\begin{align}
&\mathrm{maximize}: f(\mathbf{x}) \\
&\mathrm{constraint}: g(\mathbf{x})=0
\end{align}
$$

ここで$f(\mathbf{x})$が最適化問題の目的関数、$g(\mathbf{x})=0$が最適化問題の制約条件である。このとき、前述の多変量関数のテイラー展開の考え方を元に、$g(\mathbf{x}+\mathbf{\epsilon})$の一次のテイラー展開を考える。
$$
\large
\begin{align}
g(\mathbf{x}+\mathbf{\epsilon}) \simeq g(\mathbf{x}) + \mathbf{\epsilon}^{T} \nabla g(\mathbf{x})
\end{align}
$$

上記において、$g(\mathbf{x}+\mathbf{\epsilon}) = g(\mathbf{x})$より$\mathbf{\epsilon}^{T} \nabla g(\mathbf{x})=0$が導出できる。ここで$\mathbf{\epsilon}$は$g(\mathbf{x})$の接線方向のベクトルであるため、$\nabla g(\mathbf{x})$は$g(\mathbf{x})$によって定義される領域に垂直なベクトルとなる。

また、$\nabla f(\mathbf{x})$も$g(\mathbf{x})=0$によって定義される領域に垂直なベクトルとなる。これにより$\nabla g(\mathbf{x})$と$\nabla f(\mathbf{x})$が平行で、$\nabla f(\mathbf{x}) + \lambda \nabla g(\mathbf{x})=0$が成立することがわかる。
$$
\large
\begin{align}
L(\mathbf{x}, \lambda) \equiv f(\mathbf{x}) + \lambda g(\mathbf{x})
\end{align}
$$

したがって、上記のように$L(\mathbf{x}, \lambda)$を定義すると、下記が成立する。
$$
\large
\begin{align}
\nabla L(\mathbf{x}, \lambda) &= \nabla f(\mathbf{x}) + \lambda \nabla g(\mathbf{x}) \\
&= 0
\end{align}
$$

よって、$L(\mathbf{x}, \lambda)$の最大化を考えることで、制約付きの最適化問題を解くことができる。

制約条件が不等号で与えられる場合

まとめ

「ラグランジュの未定乗数法」は「制約つき最適化問題」を解くにあたって用いられるので、多くの問題において用いられる非常に役に立つ解法です。
導出にあたっては「制約条件の関数」と「目的関数」の二つの勾配ベクトルが「制約条件」が作る線や平面などと直交し、二つの勾配ベクトルが平行であることを用いることで図形的な解釈を行いつつ示すことが可能です。

https://www.maruzen-publishing.co.jp/item/b294524.html