拘束のある問題
提供: Internet Web School
目次 |
等式拘束のある問題
陰関数定理とラグランジュ乗数
以下の問題を考える.
\(L(x,y)=x+y\)とするとき，
半径１の円周
\(x^2+y^2=1 \qquad (1)\)
上の点\((x,y)\)で\(L(x,y)\)の最大にするものを求めよ。
関数の極値条件
実数値関数\(F(x)\)が\(x=x_0\)で極小値または極大値をとり，かつ，\(x=x_0\)で微分可能であれば，
\(F(x)\)の\(x=x_0\)での微分係数は\(0\)である。
\(\frac{dF}{dx}(x_0) = 0\)
陰関数
半径１の円の方程式
\(x_2+y_2=1\qquad (1)\)
に注目する。判りやすいように，
\(1\ge x \ge -1,1 \ge y \ge 0\) としておく．
\(g(x)=\sqrt{1-x^2}\) とすると， \(1\ge x \ge -1,1 \ge y \ge 0\)では\((1)\)の方程式を満たす\(x,y\)については \(y=g(x)\) という関係が成り立っている.
この\(g(x)\)という関数は，\((1)\)式の中には出てこない.\((1)\)からこのように間接的に導き出される関数を陰関数と呼ぶ.
一般化すれば特定の条件のもとに
\(f(x,y)=0\)という式から陰関数\(y=g(x)\)が定義される。
上の例では \(f(x,y)=x^2+y^2-1\)
しかし，何時でも上の例のように，\(f(x,y)=0\)から陰関数\(y=(x)\)が定義されるわけではない. 良く知られる定理では
陰関数定理
ある領域D\(\subseteq R\times R\)で関数\(f(x,y)\)が連続でかつ,\(x,y\)について偏微分可能で, その偏導関数
\(\frac{\partial f}{\partial x}(x,y) \qquad (1)\)
\(\frac{\partial f}{\partial y}(x,y) \qquad (2)\) も\((x,y)\)について連続とする。
D内の１点\((x_0,y_0)\)で
\(f(x_0,y_0)=0\)
であり,
\(\frac{\partial f}{\partial y}(x_0,y_0)\neq 0 \qquad (4)\)
とする。 このとき，\(x_0\)を含む\(]a,b[\)とその上の連続関数\(g(x)\)が存在し,
(1) 区間\(]a,b[\)上で\(f(x,g(x))=0\)
(2) \(y_0=g(x_0)\)
(3) 区間\(]a,b[\)上で，
\(\frac{dy}{dx}=-\frac{\partial f / \partial x}{\partial f / \partial y} \qquad (5)\)
ラグランジュ乗数法
関数\(L(x,y)\)が，制約条件 \(f(x,y)=0\) の元に\((x,y)=(x_0,y_0)\)で極値(極大値か極小値)をとるとする。
\(L(x,y)\)が\((x,y)\)について微分可能な関数で， 関数\(f(x,y)\)は\((x_0,y_0)\)が上の陰関数定理を適用できる条件を満たしているものとする。
すると，\(x_0\)の近傍で関数\(g(x)\)が存在して，\(x_0\)のその近傍では
\(f(x,g(x))=0\) が成り立ち，\(y_0=g(x_0)\),\(f(x_0,g(x_0))=0\)も成り立っている.
すると，関数\(L(x,y)\)は\((x_0,y_0)\)で極値(極大値か極小値)をとるから \(F(x)=L(x,g(x))\)も\(x=x_0\)で極値を取る.
極値条件により
\(\frac{dF}{dx}(x_0)=0 \qquad (6)\)
である．
この\(x\)についての微分を求めると\(F(x)\)は合成関数である
\( \frac{dF}{dx}(x_0)=\frac{\partial}{\partial x}L(x_0,g(x_0))+\frac{\partial}{\partial y}L(x_0,g(x_0))\frac{d}{dx}g(x_0) \qquad (7) \\ \frac{dy}{dx}=-\frac{\partial f / \partial x}{\partial f / \partial y} \qquad(8) \)
\(y=g(x)\)であるから\((8)\)式を上の\((7)\)式に代入し
\(\lambda=\frac{\partial}{\partial y}L(x_0,g(x_0))\{-\frac{\partial f}{\partial y}\}^{-1} \qquad (9)\)
という変数を使うと，
\(0=\frac{dF}{dx}(x_0)=\frac{\partial}{\partial x}L(x_0,g(x_0))+\lambda\frac{\partial}{\partial x}f(x_0,g(x_0)) \qquad (10)\) また
\(\lambda \frac{\partial}{\partial y}f(x_0,g(x_0)=-\frac{\partial}{\partial y}L(x_0,g(x)) \qquad (11)\)
から
\(0=\frac{\partial}{\partial y}L(x_0,g(x_0))+\lambda \frac{\partial}{\partial y}f(x_0,g(x_0)) \qquad (12) \)
すなわち\(\lambda\)という新しい変数を使って \(H(x,y,\lambda)=L(x,y)+\lambda f(x,y) \qquad (13)\) という関数を造ると\[\lceil\]関数\(L(x,y)<m/ath>が制約条件 <math>f(x,y)=0\) の元に \((x,y)=(x_0,y_0)\)で極値(極大値か極小値)をとる という条件からHについての制約のない場合の極値条件
\( \frac{\partial}{\partial x}H(x_0,y_0,\lambda)=0 \qquad (14) \\ \frac{\partial}{\partial y}H(x_0,y_0,\lambda)=0 \qquad (15) \\ <math>\frac{\partial}{\partial \lambda}H(x_0,y_0,\lambda)=f(x_0,y_0)=0 \qquad (16) \) が導かれる.。
要するに，制約条件付きの極値問題から，\(\lambda\)という人工的な変数を使って \(目的の関数+\lambda\times (制約条件を表す関数)\) の制約条件のない場合の極値条件が導かれる. ただしこの議論は\(\lceil\)その点が最大(小)値を与える\(\rfloor \Rightarrow \lceil\) その点が極値が与える\(\rfloor \Rightarrow \lceil\) その点での\(微分係数=0\)
という必要条件の連鎖でるので注意が必要である.
\(\lceil<math>微分係数＝0<math>\rfloor<math>は必要条件であるから， これが満たされても，極値かどうかチェックの必要があり，さらには<math>H\)の極値を与える\((x_0,y_0)\)が求められたとしても， それが最大(小)値を与えるのか確かめる必要がある。
また，少なくとも\(L\)と\(f\)が\(x,y\)について微分可能であることも必要である.
ここで使われた\(\lambda\)をラグランジュ乗数と呼ばれる.
これを一般化したものが以下である.
\( l :(x_1,x_2,\cdots,x_n) \in R^n \mapsto \in R \)
が\(\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\)で\(m\)個の制約条件
\( g_1(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)=0\\ g_2(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)=0\\ g_3(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)=0\\ \cdots \\ g_m(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)=0 \)
のもとでの極少(極大)値をとるものとする．さらに\(m\)個の\(n\)次元 ベクトル
\( \frac{\partial g_1 }{\partial {\bf x}}(\bar{\bf x})^T= \bigl{(}\frac{\partial g_1}{\partial x_1}(\bar{\bf x}),\frac{\partial g_1}{\partial x_2}(\bar{\bf x})\cdots,\frac{\partial g_1}{\partial x_n}(\bar{\bf x}) \bigr{)}\\ \frac{\partial g_2 }{\partial {\bf x}}(\bar{\bf x})^T=\bigl{(}\frac{\partial g_2}{\partial x_1}(\bar{\bf x}),\frac{\partial g_2}{\partial x_2}(\bar{\bf x})\cdots,\frac{\partial g_2}{\partial x_n}(\bar{\bf x}) \bigr{)} \\ \frac{\partial g_3 }{\partial {\bf x}}(\bar{\bf x})^T=\bigl{(}\frac{\partial g_3}{\partial x_1}(\bar{\bf x}),\frac{\partial g_3}{\partial x_2}(\bar{\bf x})\cdots,\frac{\partial g_3}{\partial x_n}(\bar{\bf x}) \bigr{)} \\ \cdots \\ \frac{\partial g_m }{\partial {\bf x}}(\bar{\bf x})^T=\bigl{(}\frac{\partial g_m}{\partial x_1}(\bar{\bf x}),\frac{\partial g_m}{\partial x_2}(\bar{\bf x})\cdots,\frac{\partial g_m}{\partial x_n}(\bar{\bf x}) \bigr{)} \\ \)
が一次独立とする．このとき,一変数関数の場合と同様,以下が成立つ．すなわち, \(m\)次元のラグランジュ乗数ベクトル
\( {\bf \lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_m) \) が存在し,
\( l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x}) + \cdots +\lambda_m g_m({\bf x}) \)
は\(\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\)で停留条件を充す．
すなわち
\( \frac{\partial}{\partial x_1}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{]} =0\\ \frac{\partial}{\partial x_2}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x}) \bigr{]} =0 \\ \cdots \\ \frac{\partial}{\partial x_n}\bigl{[}l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})+ \cdots +\lambda_m g_m({\bf x})\bigr{]}=0 \)
が成りたつ．
不等式拘束のある問題
前項では,等式拘束問題を扱った．この項では不等式拘束問題を扱う． 先ず,\(R^m\)の部分集合
\( P=\{ {\bf p} |{\bf p} =(p_1,p_2,\cdots,p_m)^T \in R^m, p_1 \ge 0,p_2 \ge 0,\cdots,p_m \ge 0 \} \)
を定義しておく．この(正錐)\(P\)を使って,\({\bf p},{\bf q} \in R^m\)の 順序(大小)を
\( {\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P \)
で定義する．
\(R^n\)から\(R^m\)への微分可能な写像
\( G: {\bf x} =(x_1,x_2,\cdots,x_n) \in R^n \mapsto G({\bf x}) = \left ( \begin{array}{c} g_1({\bf x})\\ g_2({\bf x})\\ g_3({\bf x})\\ \cdots \\ g_m({\bf x}) \end{array} \right ) \in R^m \) で定義されるものとする．
不等式制約
\(G({\bf x}) = \left ( \begin{array}{c} g_1({\bf x})\\ g_2({\bf x})\\ g_3({\bf x})\\ \cdots \\ g_m({\bf x}) \end{array} \right ) \le {\bf 0}= \left ( \begin{array}{c} 0\\ 0\\ 0\\ \vdots \\ 0 \end{array} \right ) \)
について,この項では以下のクーン・タッカーの条件が成立つものとする．
クーン・タッカーの条件
\( G({\bf x}) \le {\bf 0} \) を充たす任意の\({\bf x} \in R^n\)について
\(G({\bf x})+ \frac{d G}{d {\bf x}}^T({\bf x}) {\bf k} \leq 0 \)
となる \( {\bf k}=(k_1,k_2,\cdots,k_n)^T \in R^n\)が存在する．
ただし,
\(
\frac{d G}{d {\bf x}}^T({\bf x})=
\left(
\begin{array}{cccc}
\frac{\partial g_1}{\partial x_1}({\bf x}) &
\frac{\partial g_1}{\partial x_2}({\bf x}) &
\ldots&
\frac{\partial g_1}{\partial x_m}({\bf x})\\
\frac{\partial g_2}{\partial x_1}({\bf x}) &
\frac{\partial g_2}{\partial x_2}({\bf x}) &
\ldots&
\frac{\partial g_2}{\partial x_m}({\bf x})\\
\vdots & \vdots & \vdots & \vdots \\
\frac{\partial g_m}{\partial x_1}({\bf x}) &
\frac{\partial g_m}{\partial x_2}({\bf x}) &
\cdots&
\frac{\partial g_m}{\partial x_n}({\bf x})
\end{array}
\right)
\)
ここで, \(G({\bf x}) \le {\bf 0}\) は順序(大小関係)を
\( P=\{ {\bf p} |{\bf p} =(p_1,p_2,\cdots,p_m)^T \in R^m, p_1 \ge 0,p_2 \ge 0,\cdots,p_m \ge 0 \} \\ {\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P \)
定義する場合,
\( g_1({\bf x}) \le 0 ,g_2({\bf x}) \le 0, g_3({\bf x}) \le 0, \cdots, g_m({\bf x}) \le 0 \)
と同値になる．
停留条件
以上のクーン・タッカーの条件下で,
微分可能な写像
\(
l :(x_1,x_2,\cdots,x_n) \in R^n \mapsto \in R
\)
が不等式制約\(G({\bf x}) \le {\bf 0}\) のもとで
\(\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\) で極少(極大)値をとるものとすると,\(m\)次元のラグランジュ乗数ベクトル
\( {\bf \lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_m) \ge {\bf 0} \) が存在し,
\( l({\bf x})+ G({\bf x}) {\bf \lambda} = l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x}) + \cdots +\lambda_m g_m({\bf x}) \)
は,\(\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\)で停留条件を充たす．
すなわち
\( \frac{d l}{d {\bf x}}(\bar{\bf x})+ \frac{d G}{d {\bf x}}(\bar{\bf x}) {\bf \lambda} = \left( \begin{array}{c} \frac{\partial l}{\partial x_1}(\bar{\bf x})\\ \frac{\partial l}{\partial x_2}(\bar{\bf x})\\ \vdots\\ \frac{\partial l}{\partial x_n}(\bar{\bf x})\\ \end{array} \right) + \left( \begin{array}{cccc} \frac{\partial g_1}{\partial x_1}({\bf x}) & \frac{\partial g_2}{\partial x_1}({\bf x}) & \ldots& \frac{\partial g_m}{\partial x_1}({\bf x})\\ \frac{\partial g_1}{\partial x_2}({\bf x}) & \frac{\partial g_2}{\partial x_2}({\bf x}) & \ldots& \frac{\partial g_m}{\partial x_2}({\bf x})\\ \vdots & \vdots & \vdots & \vdots \\ \frac{\partial g_1}{\partial x_n}({\bf x}) & \frac{\partial g_2}{\partial x_n}({\bf x}) & \cdots& \frac{\partial g_m}{\partial x_n}({\bf x}) \end{array} \right) \left( \begin{array}{c} \lambda_1 \\ \lambda_2 \\ \vdots \\ \lambda_m \end{array} \right) = \left ( \begin{array}{c} 0\\ 0\\ \vdots \\ 0 \end{array} \right ) \)
が成りたつ．
さらに\(\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\)については,
\( G(\bar{\bf x}){\bf \lambda}=\lambda_1 g_1(\bar{\bf x})+\lambda_2 g_2(\bar{\bf x}) + \cdots +\lambda_m g_m(\bar{\bf x}) =0 \)
が成立つ．
\( {\bf \lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_m) \ge {\bf 0} \)
は
\( \lambda_1 \ge 0,\lambda_2\ge 0,\cdots,\lambda_m \ge 0 \)
と同値になる．
