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

B.3.2 信頼領域法を用いる方法

　本手法では，二つの二次計画問題を解くことで点列を生成していきます．まず，一つ目の二次計画問題は次の通りです．

\[\begin{array}{@{}ll@{}} \mbox{目的関数} & \displaystyle \frac{1}{2} (\Delta x_k^{SD})^T D_k \Delta x_k^{SD} + \nabla f(x_k)^T \Delta x_k^{SD} \quad \rightarrow \quad \mbox{最小化} \\ \mbox{制約条件} & \displaystyle \begin{array}{@{}l@{}} g_j(x_k) + \nabla g_j(x_k)^T \Delta x_k^{SD} = 0, j \in J_E \\ g_j(x_k) + \nabla g_j(x_k)^T \Delta x_k^{SD} \ge 0, j \in J_I \end{array} \end{array}\]

　ここで$D_k$とは，要素が正の値であるような対角行列とします．この問題の解$\Delta x_k^{SD}$は，本手法に大域的収束性を与える上で大きな役割を果たします．

　

　この問題の解を求めたとき，効いている制約の集合を$J_A^k$とします．すなわち

\[J_A^k = \{ j \in J_E \cup J_I \mid g_j(x_k) + \nabla g_j(x_k)^T \Delta x_k^{SD} = 0\}\]

となります．このとき，もう一つの二次計画問題は次のように定められます．

\[\begin{array}{@{}ll@{}} \mbox{目的関数} & \displaystyle \frac{1}{2}(\Delta x_k^N)^T G_k \Delta x_k^N + \nabla f(x_k)^T \Delta x_k^N \quad \rightarrow \quad \mbox{最小化} \\ \mbox{制約条件} & g_j(x_k) + \nabla g_j(x_k)^T \Delta x_k^N = 0, j \in J_A^k \end{array}\]

　ここで$G_k$は元の問題のラグランジュ関数のヘッセ行列です．この問題の解$\Delta x_N$は，反復点が元の問題の解に近づいたときに速い収束をするための方向になっています．また，この問題のKKT条件は，次のように線形方程式系として表すことができます．

\[\left( \begin{array}{cc} G_k & -\nabla g_{J_A^k}(x_k) \\ \nabla g_{J_A^k}(x_k)^T & 0 \end{array} \right) \left( \begin{array}{c} \Delta x_k^N \\ y_{k+1,J_A^k}^N \end{array} \right) = \left( \begin{array}{c} -\nabla f(x_k) \\ -g_{J_A^k}(x_k) \end{array} \right)\]

　ここで，$y_{k+1,J_A^k}^N$はこの問題の制約条件に対するラグランジュ乗数とします．一般に，問題規模が同程度であれば，線形方程式系は二次計画問題に比べ速く解くことができるので，この問題に対する計算コストは，先程の$\Delta x_{SD}$を求める問題と比べて小さいものと考えることができます．

　本手法では，$\Delta x_{SD}$と$\Delta x_N$の凸結合

\[\Delta x_k(\nu_k) = \nu_k \Delta x_k^{SD} + (1 - \nu_k) \Delta x_k^N\]

を探索方向とし，定められた信頼領域の中を探索し，次の反復点を生成します．

B.3.1 準ニュートン法を用いる方法
B.4 制約充足問題ソルバwcsp

 

 

上に戻る