2021.07.15
数学

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

はじめに

　今回は、最適化問題を解く際に使われるラグランジュの未定乗数法について説明する。ラグランジュの未定乗数法とは、最適化したい関数とそれに付随する束縛条件から1つの式を作り、その式の極値を求める操作である。最初に、ラグランジュの未定乗数法で簡単な例題を解き、確かに極値が得られることを確認する。そのあとラグランジュの未定乗数法の仕組みを解説する。

ラグランジュの未定乗数法で極値を求める

　以下の例題を考える（例題1）。

束縛条件が

(1) $\begin{equation*} (x-1)^2+(y-1)^2=1 \end{equation*}$

で与えられるとき

(2) $\begin{equation*} f(x,y)=x^2+y^2 \end{equation*}$

の極値を求めよ。

3次元空間に図示すると以下のようになる。束縛条件は円柱の側面（赤色）であり、関数 $f(x,y)$ は放物曲面（緑色）である。

放物曲面と円柱の交線（楕円）上に存在する点のうち高さ $z$ が一番大きい点（ $\alpha$ ）と一番小さい点（ $\beta$ ）が求めたい点である。前者は極大値、後者は極小値に相当する。

ラグランジュの未定乗数法ではまず最初に実数 $u$ を導入し、次の関数を考える。

(3) $\begin{equation*} L(x,y,u)=x^2+y^2+u\left[(x-1)^2+(y-1)^2-1\right] \end{equation*}$

右辺最初の2つの項は式(2)に対応し、第3項の括弧の中は、束縛条件(1)の右辺にある1を左辺に移行したものである。次に、 $L$ を $x,y,u$ の関数とみなし極値を求める。

(4) $\begin{eqnarray*} \frac{\partial L}{\partial x}&=&2x+2u(x-1)=0 \\ \frac{\partial L}{\partial y}&=&2y+2u(y-1)=0 \\ \frac{\partial L}{\partial u}&=&(x-1)^2+(y-1)^2-1=0 \end{eqnarray*}$

最初の2つの式から

(5) $\begin{eqnarray*} x(1+u)&=&u \\ y(1+u)&=&u \end{eqnarray*}$

を得る。 $u=-1$ のとき上式を満たさないので $u\neq-1$ として良い。従って

(6) $\begin{eqnarray*} x&=&\frac{u}{1+u} \\ y&=&\frac{u}{1+u} \end{eqnarray*}$

を得る。この2つの式を式(4)の3つ目の式に代入すると $u$ についての2次方程式が得られる。これを解くと $u=-1\pm\sqrt{2}$ を得る。式(6)の右辺に代入すると2組の $(x,y)$ を得る。

(7) $\begin{eqnarray*} x_\alpha&=&1+\frac{1}{\sqrt{2}} \\ y_\alpha&=&1+\frac{1}{\sqrt{2}} \end{eqnarray*}$

(8) $\begin{eqnarray*} x_\beta&=&1-\frac{1}{\sqrt{2}} \\ y_\beta&=&1-\frac{1}{\sqrt{2}} \end{eqnarray*}$

これら2つが極値を与える点の座標である。どちらが極大値であるかは実際に代入して確認する。今の場合 $x_\alpha^2+y_\alpha^2=3+2\sqrt{2}$ 、 $x_\beta^2+y_\beta^2=3-2\sqrt{2}$ となるので、 $(x_\alpha,y_\alpha)$ が点 $\alpha$ （極大値）に、 $(x_\beta,y_\beta)$ が点 $\beta$ （極小値）に対応する。

　実は、関数 $L$ から作られる次のヘッセ行列 $H$

(9) $\begin{equation*} H =\left( \begin{array}{cc} \frac{\partial^2 L}{\partial x\partial x} & \frac{\partial^2 L}{\partial x\partial y} \\ \frac{\partial^2 L}{\partial y\partial x} & \frac{\partial^2 L}{\partial y\partial y} \end{array} \right) =\left( \begin{array}{cc} 1+u & 0} \\ 0 & 1+u} \end{array} \right) \end{equation*}$

が正定値行列であれば極小値、負定値行列であれば極大値になると判定できるが、今回はこの理屈には深入りしない。興味ある方はこれやこれを見てほしい。

ラグランジュの未定乗数法のからくり

　2次元ベクトルを $x=(x_1,x_2)$ と書くことにすると、上の問題を以下のように一般化することができる（例題2）。

束縛条件が

(10) $\begin{equation*} g(x)=0 \end{equation*}$

で与えられるとき

(11) $\begin{equation*} f(x) \end{equation*}$

の極値を求めよ。

求めたい極値を $x^*$ と書くことにする。式(10)より

(12) $\begin{equation*} g(x^*)=0 \end{equation*}$

が成り立つ。 $x^*$ から微小量 $d$ だけ動くと（ $d$ も2次元ベクトル）

(13) $\begin{equation*} g(x^*+d)\simeq g(x^*)+\nabla g(x^*)^T d \end{equation*}$

と近似できる（ここで、 $T$ は転置を表す）。 $d$ の向きを $\nabla g(x^*)$ と直交する向きに取ると（下図参照）

$\nabla g(x^*)^T d=0$ なので

(14) $\begin{equation*} g(x^*+d)\simeq g(x^*)=0 \end{equation*}$

となる。つまり、 $\nabla g(x^*)$ と直交する方向に少し動いた点 $x=x^*+d$ でも束縛条件は成り立つ。次に、この点における $f(x^*+d)$ の値を考える。同じように展開すると

(15) $\begin{equation*} f(x^*+d)\simeq f(x^*)+\nabla f(x^*)^T d \end{equation*}$

を得る。いま、 $\nabla f(x^*)$ と $d$ の向きが直交していないとすると、 $\nabla f(x^*)^T d$ は有限値を持つことになり $f(x^*)$ が極値であるという仮定に反する。なぜなら、極値とはその近傍における最大値あるいは最小値のことだからである。従って、 $\nabla f(x^*)$ と $d$ は直交しなければならない。つまり、 $x^*$ が極値のとき、 $\nabla f(x^*)$ と $\nabla g(x^*)$ の向きは平行でなければならない。つまり