ラグランジュの未定常数法（the method of Lagrange mulitipliers) - 巨人の肩に乗ってニヤニヤするブログ

概要

多変数実数値関数の停留点を変数間の制約条件下で求めるための方法。

束縛問題を極値問題として扱うことができる。

そのため、束縛されたいと強く望むあなたには、おすすめできない。

等式制約条件下での最適化問題

目的関数 $\hspace{3} f( \bf{ x }) \hspace{3}$ が最大となる点を

$m$ 個の等式制約

$h_i(\bf{x})=0,\hspace{10} i=1,2,\cdots,m$

の下で求める。

この問題はラグランジュの未定常数法により解くことができる。

※等式制約条件下での最適化問題をラグランジュの未定常数法で解く場合、目的関数や制約条件式に対して微分可能性や凸関数である等の条件が必要であるが、それらがすべて満たされていると仮定する。

この問題に対してラグランジュ関数と呼ばれる次の実数値関数を定義する。

$L(\bf{x},\bf{\lambda}) = f(\bf{x}) + \displaystyle\sum_{i=1}^m \lambda_ih_i(\bf{x})$

このとき、以下の連立方程式を解くことによって最適点 $\hspace{3}\bf{x}_*\hspace{3}$ を求めることができる。

$\frac{\partial L(\bf{x},\bf{\lambda})}{\partial \bf{x}} = \frac{\partial f(\bf{x})}{\partial \bf{x}} + \displaystyle\sum_{i=1}^m \lambda_i\frac{\partial h_i(\bf{x})}{\partial \bf{x}} = \bf{\0}$

$\frac{\partial L(\bf{x},\bf{\lambda})}{\partial \lambda_i} = h_i(\bf{x}) = 0, \hspace{5} i=1,2,\cdots,m$

このようにして最適点を求める魔法が昨今、世間を賑わせているラグランジュの未定常数法である。

幾何学的な説明

例題を通して、幾何学的な説明をしていく。

例：

$max.\hspace{10} f(x_1,x_2) = -x_1^2-x_2^2+8$

$s.t.\hspace{10} h(x_1,x_2)=x_1+x_2-8=0$

このとき、目的関数 $\hspace{3}f\hspace{3}$ のグラフは以下のようになる。

何かに似ているが偶然である。

f:id:dr_melos:20130804180546p:plain

これを上から見た図が以下。

※黒い線は等高線を、青い線は制約によって $\hspace{3}(x_1,x_2)\hspace{3}$ がとりうる範囲（制約面）をそれぞれ表している。

f:id:dr_melos:20130804190552p:plain

まず、最適点 $\hspace{3}\bf{x}_*\hspace{3}$ においては制約面と等高線は接していなければならない。

もしそうでないとすると、制約面に沿って $\hspace{3}f(\bf{x})\hspace{3}$ の値がさらに大きくなるように移動できてしまい、矛盾。

よって以下のことがいえる。

$\exists\lambda \neq 0,\hspace{10}\nabla_{\bf{x}}f(\bf{x}) + \lambda\nabla_{\bf{x}}h(\bf{x})=0$

また、制約面と等高線が一致していたとしても、制約面上に解があるとは限らないので、

$\begin{equation} h(\bf{x})=0\end{equation}$

という条件も必要になる。

以上をまとめると次の連立方程式が導かれる。

$\begin{eqnarray} \left\{ \begin{array}{l} -2x_1 + \lambda=0\\ -2x_2 + \lambda=0\\ x_1+x_2-8=0 \end{array} \right. \end{eqnarray}$

これより、最適解 $\hspace{3} $x_1,x_2$ = $2,2$ \hspace{3}$ が得られた。

不等式制約条件下での最適化問題

ラグランジュの未定常数法は不等式制約条件下での最適化問題にも適用できる。

ただ、僕はもう疲れ（手記はここで途絶えている）

参考

パターン認識と機械学習上

言語処理のための機械学習入門