拘束のある問題
提供: Internet Web School
(ページの作成: ==等式拘束のある問題= <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</mat…)
次の差分→
2020年11月25日 (水) 10:58時点における版
=等式拘束のある問題
\( l :(x_1,x_2,\cdots,x_n) \in R^n \mapsto \in R \)
が\(\bar[[:Template:\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<math>個の<math>n<math>次元 ベクトル <math> \frac{\partial g_1 }{\partial {\bf x}}(\bar[[:Template:\bf x]])^T= \bigl{(}\frac{\partial g_1}{\partial x_1}(\bar[[:Template:\bf x]]),\frac{\partial g_1}{\partial x_2}(\bar[[:Template:\bf x]])\cdots,\frac{\partial g_1}{\partial x_n}(\bar[[:Template:\bf x]]) \bigr{)}\\ \frac{\partial g_2 }{\partial {\bf x}}(\bar[[:Template:\bf x]])^T=\bigl{(}\frac{\partial g_2}{\partial x_1}(\bar[[:Template:\bf x]]),\frac{\partial g_2}{\partial x_2}(\bar[[:Template:\bf x]])\cdots,\frac{\partial g_2}{\partial x_n}(\bar[[:Template:\bf x]]) \bigr{)} \\ \frac{\partial g_3 }{\partial {\bf x}}(\bar[[:Template:\bf x]])^T=\bigl{(}\frac{\partial g_3}{\partial x_1}(\bar[[:Template:\bf x]]),\frac{\partial g_3}{\partial x_2}(\bar[[:Template:\bf x]])\cdots,\frac{\partial g_3}{\partial x_n}(\bar[[:Template:\bf x]]) \bigr{)} \\ \cdots \\ \frac{\partial g_m }{\partial {\bf x}}(\bar[[:Template:\bf x]])^T=\bigl{(}\frac{\partial g_m}{\partial x_1}(\bar[[:Template:\bf x]]),\frac{\partial g_m}{\partial x_2}(\bar[[:Template:\bf x]])\cdots,\frac{\partial g_m}{\partial x_n}(\bar[[:Template:\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[[:Template:\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 \} \)
を定義しておく.この(正錐)</math>P</math>を使って,\({\bf p},{\bf q} \in R^m\)の 順序(大小)を
\( {\bf p} \ge {\bf q} \Leftrightarrow {\bf p} - {\bf q} \in P \) で定義する.
\(R^n<math>から<math>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}となる {\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}<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 \) 定義する場合,
\( 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[[:Template:\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[[:Template:\bf x]]=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\)で停留条件を充たす.
すなわち
\(
\frac{d l}{d {\bf x}}(\bar[[:Template:\bf x]])+ \frac{d G}{d {\bf x}}(\bar[[:Template:\bf x]])
{\bf \lambda}
=
\left(
\begin{array}{c}
\frac{\partial l}{\partial x_1}(\bar[[:Template:\bf x]])\\
\frac{\partial l}{\partial x_2}(\bar[[:Template:\bf x]])\\
\vdots\\
\frac{\partial l}{\partial x_n}(\bar[[:Template:\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[[:Template:\bf x]]=(\bar{x}_1,\bar{x}_2,\cdots,\bar{x}_n)\)については,
\( G(\bar[[:Template:\bf x]]){\bf \lambda}=\lambda_1 g_1(\bar[[:Template:\bf x]])+\lambda_2 g_2(\bar[[:Template:\bf x]]) + \cdots +\lambda_m g_m(\bar[[:Template:\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 \)
と同値になる.