next up previous
Next: 実験 Up: 原理 Previous: 最適化アルゴリズムの一般形


制約付き最適化問題とLagrange関数

前の項では変数に制約条件がないときの関数の最適化問題を取り扱った。 本節では, 変数に等式制約条件が課されているときの最適化問題の解法を 取り扱う。 このような問題の代表的な解法がLagrange関数を用いる方法である。

等式制約条件

$\displaystyle g(\vec{x})=0$ (21)

のもとで関数 $ f(\vec{x})$の最小値を求める問題を考える。 ただし, $ g(\vec{x})$は必要な回数だけ微分可能であるとする。

ここで, 点 $ \overline{\vec{x}}$が上記の問題の最適解だったと仮定しよう。 すると, $ g(\vec{x})=0$なる曲面に沿って $ \overline{\vec{x}}$を少しだけ動かして も, $ f(\vec{x})$の値は変わらないはずである。 すなわち, 超曲面 $ f(\vec{x})=f(\overline{\vec{x}})$ と超曲面 $ g(\vec{x})=0$は点 $ \overline{\vec{x}}$において接(超)平面を共有するから, これらの 超曲面の法線ベクトル$ \nabla f$$ \nabla g$は点 $ \overline{\vec{x}}$において平行になる。 このような場合には, 適当な定数$ \lambda$が取れて,

$\displaystyle \nabla f(\overline{\vec{x}}) + \lambda \nabla g(\overline{\vec{x}})=0$ (22)

となる。

式(22)の左辺は

$\displaystyle L(\lambda,\vec{x})=f(\vec{x})+\lambda g(\vec{x})$ (23)

なる関数の$ \vec{x}$に関する偏微分になっている。 だから, 点 $ \overline{\vec{x}}$が最適であるための必要条件(22)は,

$\displaystyle \frac{\partial L}{\partial \vec{x}}=\vec{0}^T$ (24)

と書き直される。 一方, 式(23)を$ \lambda$について偏微分すると

$\displaystyle \frac{\partial L}{\partial \lambda}=g$ (25)

となる。最適解 $ \overline{\vec{x}}$には $ g(\overline{\vec{x}})=0$ という制約条件が課されていたのだが, この制約条件は, 式(23)の関数$ L$を用いることで,

$\displaystyle \frac{\partial L}{\partial \lambda}=0$ (26)

と書き直されることになる。

式(24)と式(26)をまとめると, 点 $ \overline{\vec{x}}$が最適解であるための必要条件は,

$\displaystyle \frac{\partial L}{\partial \vec{x}}=\vec{0}^T, \quad \frac{\partial L}{\partial \lambda}=0$ (27)

であることがわかる。 よって, この制約付き最小化問題は, 非線形連立方程式(27)を解く問題に帰着されることになる。

ただし, 式(27)は最小解のための必要条件であって十分条件ではない。 実際には, 式(27)を解いて得られる解には 関数の極小点, 極大点および鞍点がすべて含まれる。

例 3   関数

$\displaystyle f(x_1,x_2)=x_1+x_2, \quad g(x_1,x_2)=x_1^2+x_2^2$ (28)

に対し, 制約条件 $ g(x_1,x_2)=1$ のもとで $ f(x_1,x_2)$を 最小化する問題を考えよう。制約条件を満たす領域は単位円である。 一方, 関数$ f$の等高線は傾き$ -1$の直線である。

さて, 単位円上にある点が円周上のある点を起点として 微小に移動するという状況を考える。

$ (x_1,x_2)$が動き始める点の座標が $ (1/\sqrt{2},1/\sqrt{2})$である場合と $ (-1/\sqrt{2},-1/\sqrt{2})$である場合には, この点から点$ (x_1,x_2)$が 少しだけ動いたとき, その軌跡は $ f(x_1,x_2)$の等高線を横切らないから, $ f(x_1,x_2)$の値は変わらない。そして, 点 $ (1/\sqrt{2},1/\sqrt{2})$における $ g(x_1,x_2)=1$を満たす曲線(円)の法線ベクトルは $ [\sqrt{2},\sqrt{2}]^T$, 点 $ (-1/\sqrt{2},-1/\sqrt{2})$における の法線ベクトルは $ [-\sqrt{2},-\sqrt{2}]^T$となり, これらはいずれも $ f(x_1,x_2)$の等高線に直交している (例1, 例2参照)。

これに対し, 点$ (x_1,x_2)$が動き始める点の座標が上記以外であった場合には, 点が微小に移動したときに, その軌跡は必ず $ f(x_1,x_2)$の等高線を横切るので, 関数の値は変動する。また, このとき, $ g(x_1,x_2)=1$を満たす曲線の法線ベクトルは $ f(x_1,x_2)$の等高線と直交しない。

以上のように考えると, Lagrange乗数法によって関数 $ f(x_1,x_2)$が極値を取る点 $ (1/\sqrt{2},1/\sqrt{2})$および $ (-1/\sqrt{2},-1/\sqrt{2})$ が発見されることがわかる。なお, 前者は関数が極大となる点, 後者は関数が極小となる点である。

単位円上の各点( $ g(x_1,x_2)=0$をみたす点)における法線ベクトルと 関数 $ f(x_1,x_2)$の勾配ベクトルとの関係を 図3に示す。 図3では, 点Aおよび点Bにおいて単位円の法線ベクトルと 関数 $ f(x_1,x_2)$の勾配ベクトルが平行になっている。 点Aが関数 $ f(x_1,x_2)$が最小となる点であり, 点Bが関数 $ f(x_1,x_2)$が最大となる点である。 点Cおよび点Dでは, 単位円の法線ベクトルと 関数 $ f(x_1,x_2)$の勾配ベクトルは斜めに交わっている。 このとき, 点Cおよび点Dから出発した点の軌跡は 関数 $ f(x_1,x_2)$の等高線を必ず横切るから, 点Cおよび点Dでは関数 $ f(x_1,x_2)$は極値を取らない ことがわかる.

図 3: Lagrange乗数法の意味
\includegraphics[width=.8\textwidth]{laglange.eps}

制約条件が $ g_1(\vec{x})=0$から $ g_m(\vec{x})=0$まで$ m$個あるときにも,

$\displaystyle L(\lambda,\vec{x})=f(\vec{x})+\sum_{i=1}^m \lambda_i g_i(\vec{x})$ (29)

とおき,

$\displaystyle \frac{\partial L}{\partial \vec{x}}=\vec{0}^T, \frac{\partial L}{\partial \lambda_1}=0, \ldots\frac{\partial L}{\partial \lambda_m}=0$ (30)

なる非線形連立方程式を解くことにより, もとの最適化問題を解くことができる。

式(23), 式(29)で定義される$ L$をLagrange関数, 式(27), 式(30)を解くことによりもとの関数の最小値 を得る解法をLagrange乗数法と呼ぶ。

続いて, 式(30)の解を求める方法を導くために, 非線形方程式

$\displaystyle \vec{r}(\vec{x})=\vec{0}$ (31)

を解く問題を考える。 ここに, $ \vec{r}$$ n$次のベクトル値関数とする。

$ k$回の繰り返し時における解の候補 $ \vec{x}_{k}$が与えられているとしよう。 式(31)を $ \vec{x}_{k}$のまわりでTaylor展開して1次の項まで取ると,

$\displaystyle \vec{r}(\vec{x})\simeq \vec{r}(\vec{x}_{k})+ \nabla \vec{r} (\vec{x}_{k}) (\vec{x}-\vec{x}_{k})$ (32)

となるから1, $ \vec{r}(\vec{x})$$ \vec{0}$に近くするためには,

$\displaystyle \vec{x}_{k+1}= \vec{x}_{k} -(\nabla \vec{r} (\vec{x}_{k}))^{-1} \vec{r}(\vec{x}_{k})$ (33)

とすればよいことがわかる。 ただし, 数値的には逆行列を求めることは好ましくないので, $ \vec{x}_{k+1}$を式(33)から直接計算するかわりに 線形方程式

$\displaystyle (\nabla \vec{r} (\vec{x}_{k}))\vec{x}_{k+1}= (\nabla \vec{r} (\vec{x}_{k}))\vec{x}_{k} -\vec{r}(\vec{x}_{k})$ (34)

を解く。 上記の手順を繰り返すことで, 式(31)の解が求められると 考えられる。

式(33)の手順を繰り返すことによって 関数の零点を求めるアルゴリズムもNewton法と呼ばれる。

式(27)あるいは式(30)を解く問題に上述のアルゴリズムを適用 するためには, 変数$ \vec{x}$に関する非線形連立方程式 $ \vec{r}(\vec{x})=0$を 変数 $ (\vec{x},\lambda)$に関する非線形連立方程式(27) あるいは 変数 $ (\vec{x},\lambda_1,\ldots,\lambda_m)$に関する非線形連立方程式(30) で置き換えればよい。


next up previous
Next: 実験 Up: 原理 Previous: 最適化アルゴリズムの一般形
Shigeru HANBA
平成15年11月16日