数理最適化セミナーのご案内

B.1.3 信頼領域を利用する方法

　行列$G$が非負定値でないとき直線探索法を利用することは困難です．そこで，$G$が不定であるときも利用できる方法として主双対変数に対する信頼領域法を採用します．このとき，探索方向ベクトル$w$，サイズ$\delta > 0$，ステップ幅$\alpha$は次のような関係を満たします．

\begin{align*} & \| w \| \le \delta, \\ & \alpha \le \min \left\{ \frac{\delta}{\| w \|}, \gamma \alpha_{\max} \right\} \end{align*}

　$\alpha_{\max}$の導出方法は「直線探索を利用する方法」同様です．信頼領域のサイズ調整は通常の方法で行います．

　

　大域的収束性を得るために基準となる最急降下方向ベクトル$(\Delta x_{SD}, \Delta y_{SD}, \Delta z_{SD})$を

\begin{align*} \left[ \begin{array}{cc} D + X^{-1} Z & -A^t \\ -A & 0 \end{array} \right] \left[ \begin{array}{c} \Delta x_{SD} \\ \Delta y_{SD} \end{array} \right] &= \left[ \begin{array}{c} -r_L - X^{-1} r_C \\ r_E \end{array} \right], \\ \Delta z_{SD} &= -X^{-1} Z \Delta x_{SD} - X^{-1} r_C, \end{align*}

によって定義します．ここで$D \succ 0$は対角行列です．$\alpha^*$を方向$\Delta_{SD}$に沿って信頼領域で与えられる区間内で，メリット関数変化量の二次近似$\Delta F_q(x,z,\Delta x,\Delta z)$を最小化するステップ幅として定義します．

\begin{align*} & \alpha^* = \arg \min \{\Delta F_q(x, z, \alpha \Delta x_{SD}, \alpha \Delta z_{SD}) \mid \| \alpha(\Delta x_{SD} + \Delta z_{SD}) \| \le \delta, \alpha \in [0, \bar{\alpha} ] \} \\ & \bar{\alpha} = \min \{ 1, \gamma \alpha_{\max} \}, \gamma \in (0,1), \end{align*}

　信頼領域のステップ幅$\alpha$は以下の条件をみたすように設定します．

\begin{align*} & \Delta F_q(x, z, \alpha \Delta x, \alpha \Delta z) \le \frac{1}{2} \Delta F_q(x, z, \alpha^* \Delta x, \alpha^* \Delta z) < 0, \\ & \| \Delta x_{Nk} \| \le M \| \Delta x_{SDk} \|, \\ & \| \Delta z_{Nk} \| \le M \| \Delta z_{SDk} \|\end{align*}

　「信頼領域を利用する方法」では探索方向ベクトル$(\Delta x, \Delta z)$は

\[\left( \begin{array}{c} \Delta x \\ \Delta z \end{array} \right) = \nu \left( \begin{array}{c} \Delta x_{SD} \\ \Delta z_{SD} \end{array} \right) + (1 - \nu) \left( \begin{array}{c} \Delta x_N \\ \Delta z_N \end{array} \right),\]

として計算されます．ここで，パラメ－タ$\nu \in [0,1]$は$\nu = 0,0.1,0.2,\cdots,0.9,1.0$の中で条件：

\[\Delta F_q(x, z, \alpha \Delta x, \alpha \Delta z) \le \frac{1}{2} \Delta F_q(x, z, \alpha^* \Delta x, \alpha^* \Delta z) < 0\]

をみたす最小の数です．このように，「信頼領域を利用する方法」では探索方向ベクトルの設定に異なる二方向$(\Delta x_{SD},\Delta z_{SD})$，$(\Delta x_N,\Delta z_N)$を利用します．この結果，大域的収束性が保証されます．

B.1.2 直線探索を利用する方法
B.1.4 線形計画問題専用内点法

 

 

上に戻る