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

はじめに

 今回は、最適化問題を解く際に使われるラグランジュの未定乗数法について説明する。ラグランジュの未定乗数法とは、最適化したい関数とそれに付随する束縛条件から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を左辺に移行したものである。次に、Lx,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^*)の向きは平行でなければならない。つまり

(16)    \begin{equation*} \nabla f(x^*)+u\nabla g(x^*)=0 \end{equation*}

を満たす実数uが存在するということである。いま、次の関数を定義する。

(17)    \begin{equation*} L(x,u)=f(x)+ug(x) \end{equation*}

関数Lラグランジュ関数と呼ぶ。これを空間座標で微分しそれを0と置いたものが式(16)である。また、uで微分し0と置くと束縛条件g(x)=0を得る。つまり、例題2を解くことと、ラグランジュ関数の極値を求めることとは等価である。

 今考えてきたxは2次元であるが、一般のN次元に拡張することができる。さらに、複数の束縛条件に拡張することもできる。

(18)    \begin{equation*} L(x,u)=f(x)+\sum_{m=1}^{M}u_m g_m(x) \end{equation*}

ここで、x=(x_1,\cdots,x_N)^Tu=(u_1,\cdots,u_M)^Tである。これらN+M個の変数について微分することにより極値を求めれば良い。以上が、ラグランジュの未定乗数法の理屈である。

まとめ

 今回はラグランジュの未定乗数法について説明した。この手法で求まる複数の極値のうちどれが最適であるか(考える領域の中でどれが一番大きいか、あるいは一番小さいか)は別途確認する必要があることに注意しなければならない。

参考文献

しっかり学ぶ数理最適化

補足

 上の例題1は高校数学で解くことができる。束縛条件を円の極座標表示で表しf(x,y)に代入すればよい。できますか?

Kumada Seiya

Kumada Seiya

仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

コメント

この記事へのコメントはありません。

アーカイブ

カテゴリー

PAGE TOP