ソースを表示

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

<math>
\frac{\partial}{\partial x_1}\bigl{[} l({\bf x}) + \lambda_1 g_1({\bf x}) \bigr{]}  =0
</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\\
</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>
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>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}を充たす任意の{\bf x} \in R^nについて \\
G({\bf x})+ \frac{d G}{d {\bf x}}^T({\bf x}) {\bf k}となる
{\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>

と同値になる．