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

B.1.2 直線探索を利用する方法

　修正KKT条件に対するニュ－トン法は次のようになります．

\begin{align*} & \left[ \begin{array}{cc} G + X^{-1} Z & -A^t \\ -A & 0 \end{array} \right] \left[ \begin{array}{c} \Delta x_N \\ \Delta y_N \end{array} \right] = \left[ \begin{array}{c} -r_L - X^{-1} r_C \\ r_E \end{array} \right], \\ & \Delta z_N = -X^{-1} Z \Delta x_N - X^{-1} r_C.\end{align*}

　ここで，$(\Delta x_N, \Delta y_N, \Delta z_N)$は各変数に対する探索方向ベクトルで，$G$はラグランジュ関数のヘッセ行列あるいはその近似行列です．このとき，「$\rho$が十分大きく，$G$が半正定値行列である場合$\Delta F_l(x,z,\Delta x_N,\Delta z_N) < 0$である」という性質が成り立ちます．

　この性質を利用して，直線探索を利用して大域的に収束するアルゴリズムを構築することができます．主双対変数に対するステップ幅$\alpha$は以下のように計算されます．まず，次の三式から$\alpha$の上限値$\alpha _{\max}$を求めます．

\begin{align*} & {\alpha^x}_{\max } = \min_i \left\{ \frac{-x_i}{(\Delta x_N)_i} \mid (\Delta x_N)_i < 0 \right\}, \\ & {\alpha^z}_{\max} = \min_i \left\{ \frac{-z_i}{(\Delta z_N)_i} \mid (\Delta z_N)_i < 0 \right\}, \\ & \alpha_{\max} = \min \{ {\alpha^x}_{\max}, {\alpha^z}_{\max} \} \end{align*}

　次に，

\[\alpha = \bar{\alpha} \beta^l,\quad \bar{\alpha} = \min \{ \gamma \alpha_{\max}, 1 \}\]

と定義します．ここで，$\gamma \in (0,1)$, $\beta \in (0,1)$です．そして，$l$は

\[F(x + \bar{\alpha} \beta^l \Delta x_N, z + \bar{\alpha} \beta^l \Delta z_N) - F(x,z) \le \varepsilon_0 \bar{\alpha} \beta^l \Delta F_l(x, z, \bar{\alpha} \beta^l \Delta x_N, \bar{\alpha} \beta^l \Delta z_N)\]

をみたす最小の正整数として定義されます注1．$\varepsilon_0 \in (0,1)$です．

　このように，各種パラメータを適切に設定すれば，メリット関数$F(x,z)$が確実に減少するような探索方向ベクトル$(\Delta x_N, \Delta y_N, \Delta z_N)$及びステップ幅$\alpha$を定める事ができます．ここからアルゴリズムの大域的収束性が保証されます．

　

　ラグランジュ関数のヘッセ行列が非負定値となるのは

  • 線形計画問題（ヘッセ行列は0）
  • 一般の凸計画問題

です．また，一般の非線形計画問題ではヘッセ行列を準ニュートン法で近似することによって行列$G$を常に正定値に保つことができます．従って，このような場合に直線探索を利用した手法を使用することができます．

注1）この一連のステップ幅の設定ルールをArmijo's Ruleと呼びます．

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

 

 

上に戻る