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

ラグランジュの未定乗数法は、制約条件付きの最適化問題を解く一般的な方法です。SVMでも使われています。
今回は、制約条件を持つ関数の最小値を求めるラグランジュ未定乗数法を解く例を説明します。

問題の設定

以下のような最適化問題を考えます：
minimize $f(x, y)$
subject to $g(x, y) = 0$

ここで、$f(x, y)$ は目的関数で、$g(x, y)$ は制約条件を表す関数です。

ラグランジュ関数の定義

ラグランジュ関数 $\mathcal{L}$ は、目的関数と制約条件を組み合わせたものです：
$$
\mathcal{L}(x, y, \lambda) = f(x, y) + \lambda \cdot g(x, y)
$$
ここで、$\lambda$ はラグランジュ乗数です。

手順

ラグランジュ関数の偏微分:
ラグランジュ関数 $\mathcal{L}$ を $x$, $y$, および $\lambda$ について偏微分します。
$$
\frac{\partial \mathcal{L}}{\partial x} = \frac{\partial f}{\partial x} + \lambda \frac{\partial g}{\partial x} = 0
$$
$$
\frac{\partial \mathcal{L}}{\partial y} = \frac{\partial f}{\partial y} + \lambda \frac{\partial g}{\partial y} = 0
$$
$$
\frac{\partial \mathcal{L}}{\partial \lambda} = g(x, y) = 0
$$

方程式の解

上記の偏微分方程式を連立方程式として解きます。これにより、変数 $x$, $y$, $\lambda$ の値を求めます。

候補点の確認

解いた連立方程式の解から得られる $(x, y)$ が候補点です。この候補点が制約条件を満たし、目的関数の最小値となるかを確認します。

例題

minimize $ f(x,y) = x^2 + y^2 $
subject to $ x + y - 1 = 0 $

ラグランジュ関数の定義

ラグランジュ関数は以下のように定義されます：
$$
\mathcal{L}(x,y,\lambda) = x^2 + y^2 + \lambda (x + y - 1)
$$

偏微分方程式

ラグランジュ関数を $ x , y , $ および $ \lambda $について偏微分します。
$$
\frac{\partial \mathcal{L}}{\partial x} = 2x + \lambda = 0
$$
$$
\frac{\partial \mathcal{L}}{\partial y} = 2y + \lambda = 0
$$
$$
\frac{\partial \mathcal{L}}{\partial \lambda} = x + y - 1 = 0
$$

連立方程式の解

$$
2x + \lambda = 0 \implies \lambda = -2x
$$
$$
2y + \lambda = 0 \implies \lambda = -2y
$$

よって、
$$
-2x = -2y \implies x = y
$$
$$
x + y - 1 = 0 \implies 2x - 1 = 0 \implies x = \frac{1}{2}, y = \frac{1}{2}
$$

確認

候補点 $ (x, y) = \left(\frac{1}{2}, \frac{1}{2}\right) $ が制約条件を満たし、目的関数 ( f ) の値は
$$
f \left(\frac{1}{2}, \frac{1}{2}\right) = \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}
$$

したがって、目的関数 $ f(x,y) = x^2 + y^2 $ は制約条件 $ x + y - 1 = 0 $の下で最小値 $ \frac{1}{2} $をとります。