最適化セミナーのご案内

B.3.3 逐次線形二次計画(SLP-SQP)法

 逐次線形二次計画法(SLP-SQP)は制約充足のためのフェーズと目的関数値最小化のフェーズという二つのフェーズから構成され,これらを交互に行う事でペナルティ関数無しに大域的収束性を保証します.各フェーズでは元の問題を線形計画問題,あるいは二次計画問題で近似し,それらの解を用いて探索を行います.

 ここでは簡単のため,不等式制約は各変数の下限制約のみとします.制約充足のフェーズでは次の問題を繰り返し解きます.

\[\begin{array}{@{}ll@{}} \mbox{最小化} & \displaystyle \nabla f(x_k)^T s + \frac{1}{2} s^T G_k s \\ \mbox{条\hskip1zw 件} & \begin{array}{@{}l@{}} g_j(x_k) + \nabla g_j(x_k)^T s = 0, j \in J_E \\ x_k + s \ge 0, j \in J_I \\ \| s \|_\infty \le \Delta_k \end{array} \end{array}\]

 $G_k$は零行列あるいはラグランジュ関数のヘッセ行列,または,その近似行列です.条件式が与えられた上下限制約のもとでの$g_j(x) = 0$, $j \in J_E$の一次近似になっているため,上記問題の解方向に直線探索をすると,制約の充足度を向上させる事が出来ます.また,$G_k$をラグランジュ関数のヘッセ行列,あるいは近似行列とすれば,反復点$x_k$が解に近い時には通常の信頼領域二次計画法と同等の反復点を生成する事になり,超一次収束が保障されます.

 制約充足のフェーズが,実行可能領域への接近を目標としている事に対し,目的関数値最小化フェーズでは等式制約が定める領域の接方向へと移動し目的関数値の最小化を目指します.

 具体的には,実行可能領域へ近付くステップ$s$と,目的関数の減少を意図した接方向へのステップ$s_T$との組合せ$s_\rho$を探索方向の候補とします.$s_T$は次の問題の解として取得します.

\[\begin{array}{@{}ll@{}} \mbox{最小化} & \displaystyle \nabla f(x_k)^T s_T + \frac{1}{2} s_T^T G_k s_T  \\ \mbox{条\hskip1zw 件} & \begin{array}{@{}l@{}} \nabla g_j(x_k)^T s_T = 0, j \in J_E \\ x_k + s_T \ge 0, j \in J_I \\ \| s_T \|_\infty \le \Delta_T \end{array} \end{array}\]

 ここでは制約充足フェーズの場合と同様に$G_k$は零行列あるいはラグランジュ関数のヘッセ行列,または,その近似行列とします.この問題は$\Delta_T = \Delta_{Tk}$から始め$s_\rho$が一定の制約充足度を満たすようになるまで$\Delta_T$を半減させつつ繰り返し解きます.この内部反復により最終的に得られた$s_\rho$$s_{\rho_k}$として,$s_{\rho_k}$による目的関数の減少量が,その二次近似関数の減少量と比べて十分だった場合は,$\Delta_T$を拡大し$\Delta_{Tk+1} = 2\Delta_T$とします.逆に一定比率以上で二次近似関数の減少量の方が上回った時は$\displaystyle \Delta_{Tk+1} = \frac{1}{2} \Delta_T$として,どちらでもない場合は$\Delta_{Tk+1} = \Delta_T$とします.そして次の反復点候補$x_k + s_{\rho_k}$が現在点での目的関数値$f(x_k)$をより減少させるのならば$x_{k+1} = x_k + s_{\rho_k}$,そうでなければ$x_{k+1} = x_k$として次の反復へと進みます.

 制約充足フェーズ,目的関数値最小化フェーズにおいて$G_k$がラグランジュ関数のヘッセ行列,あるいは近似行列であった場合,各反復において二計画問題を解くことになります.問題によっては,二次計画問題の求解が高コストになる事もあります.そのために,Numerical Optimizerでは,この二次計画問題を直接解くのではなくて,線形計画問題と,その結果得られる等式のみの二次計画問題の解を組合せ,近似的な解を構成するという工夫をしています.


 

 

上に戻る