拘束のある問題

提供: Internet Web School

目次 1 等式拘束のある問題 2 不等式拘束のある問題 2.1 クーン・タッカーの条件 2.2 停留条件

等式拘束のある問題

\( 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 \)

と同値になる．