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

準備

長方形の面積最大化

たとえば2変数の問題として、長方形の周囲長Lを一定として、その面積が最大となる長方形の形状と面積はどのようになるかを考える。この場合、長方形の辺の長さをx, yとすると、問題は以下のように表せる。

(1)    \begin{equation*} \max S(x, y) = xy \quad {\rm s.t.} \: x+y = \frac{L}{2} \end{equation*}

これは以下のように代数的に簡単に解けて、答えは正方形とわかる。

(2)    \begin{gather*} S = x \left( \frac{L}{2} - x \right) = -x^2 + \frac{L}{2} x = - \left( x - \frac{L}{4} \right)^2 + \frac{L^2}{16} \\ \max S = \frac{L^2}{16} \quad {\rm for} \: x = y = \frac{L}{4} \end{gather*}

ただし変数の数が増えたり、目的関数や制約条件が複雑になると、解析的に解くのが面倒になる。

Lgrangeの未定乗数法による解

解法から先に示す。Lagrangeの未定乗数法では、目的関数L(x, y)に対して以下の問題となる。

(3)    \begin{gather*} \max \quad L(x, y, \lambda) = S(x, y) - \lambda f(x, y) = xy - \lambda \left( x + y - \frac{L}{2} \right) \\ {\rm where} \quad S(x, y) = xy, \quad f(x, y) = x + y - \frac{L}{2} \end{gather*}

L(x, y)を最大化するために、x, y, \lambdaで偏微分した以下の方程式を設定する。

(4)    \begin{gather*} \frac{\partial L}{\partial x} = 0, \quad \frac{\partial L}{\partial y} = 0, \quad \frac{\partial L}{\partial \lambda} = 0 \end{gather*}

これを計算すると

(5)    \begin{gather*} y - \lambda = 0, \quad x - \lambda = 0, \quad x + y - \frac{L}{2}= 0 \\ \therefore x = \frac{L}{4} \end{gather*}

Lagrangeの未定乗数法の一般形

一般には、変数\boldsymbol{x} = (x_1, \ldots, x_n)について、目的関数f(\boldsymbol{x})を制約条件g(\boldsymbol{x})=0の下で最大化/最小化する問題として与えられる。

(6)    \begin{align*} & \max \quad f(\boldsymbol{x}) \\ & {\rm s.t.} \quad g(\boldsymbol{x}) = 0 \end{align*}

この等式制約条件付き最大化/最小化問題は、以下のようにL(\boldsymbol{x}, \lambda)を導入して、連立方程式として表現される。

(7)    \begin{align*} & L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) - \lambda g(\boldsymbol{x}) \\ & \frac{L(\boldsymbol{x}, \lambda)}{\boldsymbol{x}} = \frac{L(\boldsymbol{x}, \lambda)}{\lambda} = 0 \end{align*}

例題

例題1:凸関数と直線

下に凸な関数f(x, y) = x^2 + y^2について、直線x + y = 1の制約条件下での最小値を求める。

(8)    \begin{align*} & \min \quad f(x, y) = x^2 + y^2 \\ & {\rm s.t.} \quad x + y - 1 = 0 \end{align*}

ここでlagrangeの未定乗数を導入して問題を定式化すると以下のようになる。

(9)    \begin{equation*} L(x, y, \lambda) = x^2 + y^2 - \lambda (x + y - 1) \end{equation*}

(10)    \begin{align*} &\dfrac{\partial L}{\partial x} = 2x - \lambda = 0 \\ &\dfrac{\partial L}{\partial y} = 2y - \lambda = 0 \\ &\dfrac{\partial L}{\partial \lambda} = - x - y + 1 = 0 \end{align*}

この連立方程式を解くと以下のようになり、解は最小値1つとなる。

(11)    \begin{gather*} x = y = \frac{\lambda}{2} \quad \Rightarrow \quad \frac{\lambda}{2} + \frac{\lambda}{2} = 1 \quad \Rightarrow \quad \lambda = 1\\ \therefore \; x = y = \frac{1}{2} \quad , \quad \min f(x, y) = \frac{1}{2} \end{gather*}

これを目的関数のコンターと制約条件の線で表すと以下の通り。

例題2:平面と円

平面x + y - 1について、制約条件f(x, y) = x^2 + y^2の下での極値を求める。

(12)    \begin{align*} & \min \quad f(x, y) = x + y - 1 \\ & {\rm s.t.} \quad x^2 + y^2 = 1 \end{align*}

lagrangeの未定乗数を導入して問題を定式化すると以下のようになる。

(13)    \begin{equation*} L(x, y, \lambda) = x + y - 1 - \lambda (x^2 + y^2 - 1) \end{equation*}

(14)    \begin{align*} &\dfrac{\partial L}{\partial x} = 1 - 2 \lambda x = 0 \\ &\dfrac{\partial L}{\partial y} = 1 - 2 \lambda y = 0 \\ &\dfrac{\partial L}{\partial \lambda} = - x^2 - y^2 + 1 = 0 \end{align*}

この連立方程式を解くと以下のようになり、解として2つの極値を得るが、それらは最大値と最小値に相当する。

(15)    \begin{gather*} x = y = \frac{1}{2 \lambda} \quad \Rightarrow \quad \frac{1}{4 \lambda ^2} + \frac{1}{4 \lambda ^2} = 1 \quad \Rightarrow \quad \lambda = \pm \frac{1}{\sqrt{2}}\\ \therefore \; x = y = \pm \frac{1}{\sqrt{2}} \approx \pm 0.7071\\ \max f(x, y) = \sqrt{2} - 1 \approx 0.414\\ \min f(x, y) = -\sqrt{2} - 1 \approx -2.414 \end{gather*}

これを目的関数のコンターと制約条件の線で表すと以下の通り。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です