ソースを表示

==等式拘束のある問題==



==陰関数定理とラグランジュ乗数==

以下の問題を考える.


<math>L(x,y)=x+y</math>とするとき，
半径１の円周

<math>x^2+y^2=1   \qquad (1)</math>

上の点<math>(x,y)</math>で<math>L(x,y)=x+y</math>の最大にするものを求めよDC


===関数の極値条件===

実数値関数<math>F(x)</math>が<math>x=x_0</math>で極小値または極大値をとり，かつ，<math>x=x_0</math>で微分可能であれば，

<math>F(x)</math>の<math>x=x_0</math>での微分係数は<math>0</math>である。

<math>\frac{dF}{dx}(x_0) = 0</math>


半径１の円の方程式

<math>x_2+y_2=1\qquad (1)</math>

に注目する。判りやすいように，

<math>1\ge x \ge -1,1 \ge y \ge 0</math>
としておく．

<math>g(x)=\sqrt{1-x^2}</math>
とすると，
<math>1\ge x \ge -1,1 \ge y \ge 0</math>では<math>(1)</math>の方程式を満たす<math>x,y</math>については
<math>y=g(x)</math>
という関係が成り立っている.

この<math>g(x)</math>という関数は，<math>(1)</math>式の中には出てこない.<math>(1)</math>からこのように間接的に導き出される関数を陰関数と呼ぶ.


一般化すれば特定の条件のもとに
<math>f(x,y)=0</math>という式から陰関数<math>y=g(x)</math>が定義される。

上の例では　<math>f(x,y)=x^2+y^2-1</math>

しかし，何時でも上の例のように，<math>f(x,y)=0</math>から陰関数<math>y=g(x)</math>が定義されるわけではない.


===陰関数定理===

ある領域D<math>\subseteq R\times R</math>で関数<math>f(x,y)</math>が連続でかつ,<math>x,y</math>について偏微分可能で,
その偏導関数

<math>\frac{\partial f}{\partial x}(x,y) \qquad (1)</math>

<math>\frac{\partial f}{\partial y}(x,y) \qquad (2)</math>
も<math>(x,y)</math>について連続とする。

D内の１点<math>(x_0,y_0)</math>で

<math>f(x_0,y_0)=0</math>

であり,

<math>\frac{\partial f}{\partial y}(x_0,y_0)\neq 0 \qquad (4)</math>

とする.
このとき，<math>x_0</math>を含む開区間<math>(a,b)</math>とその上の連続関数<math>g(x)</math>が存在し,

1) 開区間<math>(a,b)</math>上で<math>f(x,g(x))=0</math>

2) <math>y_0=g(x_0)</math>

3) 開区間<math>(a,b)</math>上で，

<math>\frac{dy}{dx}=-\frac{\partial f / \partial x}{\partial f / \partial y} \qquad (5)</math>



上の定理で<math>x,y</math>の役目を反対にすれば,<math>x_0=g(y_0)</math> となる陰関数の存在が示される.


===ラグランジュ乗数法===


関数<math>L(x,y)</math>が，制約条件
<math>f(x,y)=0</math>
の元に<math>(x,y)=(x_0,y_0)</math>で極値(極大値か極小値)をとるとする。

<math>L(x,y)</math>が<math>(x,y)</math>について微分可能な関数で，
関数<math>f(x,y)</math>は<math>(x_0,y_0)</math>が上の陰関数定理を適用できる条件を満たしているものとする。
<math>x_0</math>の近傍で関数<math>g(x)</math>が存在して，<math>x_0</math>のその近傍では
<math>f(x,g(x))=0</math>　が成り立ち，<math>y_0=g(x_0)</math>,<math>f(x_0,g(x_0))=0</math>も成り立っている.
<math>x,y</math>の役目を反対にすれば,<math>x_0=g(y_0)</math> となる陰関数を用いることになるが議論は全く同様に
できる.


関数<math>L(x,y)</math>は<math>(x_0,y_0)</math>で極値(極大値か極小値)をとるから
<math>F(x)=L(x,g(x))</math>も<math>x=x_0</math>で極値を取る.



極値条件により

<math>\frac{dF}{dx}(x_0)=0 \qquad  (6)</math>

である．

この<math>x</math>についての微分を求めると<math>F(x)</math>は合成関数であるから

<math>
\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) 
</math>

<math>y=g(x)</math>であるから<math>(8)</math>式を上の<math>(7)</math>式に代入し



<math>\lambda=\frac{\partial}{\partial y}L(x_0,g(x_0))\{-\frac{\partial f}{\partial y}\}^{-1} \qquad (9)</math>

という変数を使うと，

<math>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)</math>

また

<math>\lambda \frac{\partial}{\partial y}f(x_0,g(x_0)=-\frac{\partial}{\partial y}L(x_0,g(x)) \qquad (11)</math>

から

<math>0=\frac{\partial}{\partial y}L(x_0,g(x_0))+\lambda \frac{\partial}{\partial y}f(x_0,g(x_0)) \qquad (12) </math>

すなわち<math>\lambda</math>という新しい変数を使って

<math>H(x,y,\lambda)=L(x,y)+\lambda f(x,y) \qquad (13)</math>

という関数を造ると:

関数<math>L(x,y)</math>が制約条件<math>f(x,y)=0</math>
を充たすという条件の下に
<math>(x,y)=(x_0,y_0)</math>で極値(極大値か極小値)をとる
という条件から<math>H</math>についての制約のない場合の極値条件

<math>
\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) \\
\frac{\partial}{\partial \lambda}H(x_0,y_0,\lambda)=f(x_0,y_0)=0 \qquad (16)
</math>


が導かれる.制約条件付きの極値問題から，<math>\lambda</math>という人工的な変数を使って

<math>目的の関数+\lambda\times (制約条件を表す関数)</math>
の制約条件のない場合の極値条件が導かれる.

ただしこの議論は「その点が最大(小)値を与える」<math>\Rightarrow</math>
「その点が極値を与える」<math>\Rightarrow </math> 「その点での<math>微分係数=0</math>」


という必要条件の連鎖であるので注意が必要である.

「<math>微分係数＝0</math>」は必要条件であるから，
これが満たされても，極値かどうかチェックの必要があり，さらには<math>H</math>の極値を与える<math>(x_0,y_0)</math>が求められたとしても，
それが最大(小)値を与えるのか確かめる必要がある。

また，少なくとも<math>L</math>と<math>f</math>が<math>x,y</math>について微分可能であることも必要である.

ここで使われた<math>\lambda</math>はラグランジュ乗数と呼ばれる.
上の問題に適用すると


<math>f(x,y)=x^2+y^2 -1,L(x,y)=x+y</math>

拘束条件<math>f(x,y)=x^2+y^2 -1=0</math>　を充たし,<math>L(x,y)=x+y</math>の極値を与える
<math>x_0,y_0</math>が存在すると仮定すれば,

<math>x_0 \neq 0</math>　または　<math>y_0 \neq 0</math>　であり,

陰関数の存在条件
<math>\frac{\partial f}{\partial x}(x_0,y_0) = 2x_0 \neq 0 </math>
または
<math>\frac{\partial f}{\partial y}(x_0,y_0) = 2y_0 \neq 0 </math>
が成り立っている.

そこで,

<math>H(x,y,\lambda)=x+y+\lambda (x^2+y^2 -1)</math>

とおけば

<math>
1+ 2\lambda  x_0 = \frac{\partial}{\partial x}H(x_0,y_0,\lambda)=0  \qquad (17) \\
1+ 2\lambda  y_0 = \frac{\partial}{\partial y}H(x_0,y_0,\lambda)=0  \qquad (18) \\
x_0^2+y_0^2 -1 = \frac{\partial}{\partial \lambda}H(x_0,y_0,\lambda)=0 \qquad (19)
</math>


<math>(17) </math>式から <math>\lambda \neq 0 </math> であり,


<math>(18),(19) </math>式から

<math>x_0 = -\frac{1}{2\lambda} ,y_0 = -\frac{1}{2\lambda}</math>

これを<math>(19)</math> 式に代入して

<math>\frac{1}{2\lambda^2} -1 = 0</math>

よって

<math>\lambda=\frac{\sqrt{2}}{2} </math> または　<math>\lambda=-\frac{\sqrt{2}}{2} </math>

<math>\lambda=\frac{\sqrt{2}}{2} </math> のとき<math>x_0 = y_0= -\frac{\sqrt{2}}{2}</math> であり,<math>L(x_0,y_0)=x_0+y_0= -\sqrt{2} </math>

<math>\lambda=-\frac{\sqrt{2}}{2} </math> のとき<math>x_0 = y_0= \frac{\sqrt{2}}{2}</math> であり,<math>L(x_0,y_0)=x_0+y_0= \sqrt{2} </math>


従って
等式拘束条件
<math>x^2+y^2=1 </math>
の下で<math>L(x,y)=x+y </math>　の
最大値は<math>x = y= \frac{\sqrt{2}}{2}</math>のときで<math>\sqrt{2} </math> 

Microsoft Excel のソルバーで解くこともできる.

データの入力とソルバーのパラメータは以下の通りである.解析には非線形問題を選択する.
[[ファイル:LP-Fig50.1.jpg|800px]]

ソルバーの出力は以下の通りであり前期の解析解と同じである.

[[ファイル:LP-Fig50.2.jpg|800px]]

上記の議論を一般化したものが以下である.



<math>
l :(x_1,x_2,\cdots,x_n) \in R^n \mapsto \in R
</math>

が<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>で<math>m</math>個の制約条件

<math>
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
</math>

のもとでの極少(極大)値をとるものとする．さらに<math>m</math>個の<math>n</math>次元
ベクトル

<math>
\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{)} \\
</math>

が一次独立とする．これは前項の<math>(4)</math>式の陰関数の存在条件
<math>\frac{\partial f}{\partial y}(x_0,y_0)\neq 0 \qquad (4)</math>
に相当する.

<math>m</math>個の<math>n</math>次元
ベクトルからなる<math> n\times m </math>行列
<math>
\Bigl{[} \frac{\partial g_1 }{\partial {\bf x}}(\bar{\bf x}),
\frac{\partial g_2 }{\partial {\bf x}}(\bar{\bf x}),
\cdots,\frac{\partial g_m }{\partial {\bf x}}(\bar{\bf x})
\Bigr{]}
</math>
の階数が<math> m </math> であることと同値である.



このとき,一変数関数の場合と同様,以下が成立つ．すなわち,
<math>m</math>次元のラグランジュ乗数ベクトル

<math>
{\bf \lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_m)
</math>
が存在し,

<math>
l({\bf x})+\lambda_1 g_1({\bf x})+\lambda_2 g_2({\bf x})
+ \cdots +\lambda_m g_m({\bf x})
</math>

は<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>で停留条件を充す．

すなわち

<math>
\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 
</math>


が成りたつ．

==不等式拘束のある問題==

前項では,等式拘束問題を扱った．この項では不等式拘束問題を扱う．
先ず,<math>R^m</math>の部分集合

<math>
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 \} 
</math>

を定義しておく．この(正錐)<math>P</math>を使って,<math>{\bf p},{\bf q} \in R^m</math>の
順序(大小)を

<math>
{\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P
</math>

で定義する．

<math>R^n</math>から<math>R^m</math>への微分可能な写像

<math>
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
</math>
で定義されるものとする．

不等式制約

<math>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 )
</math>

について,この項では以下のクーン・タッカーの条件が成立つものとする．


===クーン・タッカーの条件===
<math>
G({\bf x}) \le {\bf 0}
</math>
を充たす任意の<math>{\bf x} \in R^n</math>について 

<math>G({\bf x})+ \frac{d G}{d {\bf x}}^T({\bf x}) {\bf k} \lt 0 </math>

となる
<math> {\bf k}=(k_1,k_2,\cdots,k_n)^T \in R^n</math>が存在する．

ただし,


<math>
\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)
</math>

ここで,
<math>G({\bf x}) \le {\bf 0}</math>
は順序(大小関係)を

<math>
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
</math>

定義する場合,

<math>
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
</math>

と同値になる．

===停留条件===

以上のクーン・タッカーの条件下で,


微分可能な写像
<math>
l :(x_1,x_2,\cdots,x_n) \in R^n \mapsto \in R
</math>

が不等式制約<math>G({\bf x}) \le {\bf 0}</math>
のもとで

<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>
で極小(極大)値をとるものとすると,<math>m</math>次元のラグランジュ乗数ベクトル

<math>
{\bf \lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_m) \ge {\bf 0}
</math>
が存在し,

<math>
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})
</math>

は,<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>で極値条件(停留条件)を充たす．


すなわち

<math>
\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 )
</math>

が成りたつ．

さらに<math>\bar{\bf x}=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)</math>については,

<math>
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
</math>

が成立つ．

<math>
{\bf \lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_m) \ge {\bf 0}
</math>

は

<math>
\lambda_1 \ge 0,\lambda_2\ge 0,\cdots,\lambda_m \ge  0
</math>

と同値になる．