SLPSQP#

読み: えすえるぴーえすきゅーぴー
英名:

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

ここでは簡単のため，不等式制約は各変数の下限制約のみとする．制約充足のフェイズでは次の問題を繰り返し解く．

(22)#\[\begin{split}\begin{array}{ll} \min & \nabla f(x_k)^\top s + \frac{1}{2} s^\top G_k s \\ \mathrm{s.t.} & g_j(x_k) + \nabla g_j(x_k)^\top s = 0, \ j \in J_E \\ & x_k + s \ge 0, \ j \in J_I \\ & \| s \|_\infty \le \Delta_k \end{array}\end{split}\]

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

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

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

(23)#\[\begin{split}\begin{array}{ll} \min & \nabla f(x_k)^\top s_T + \frac{1}{2} {s_T}^\top G_k s_T \\ \mathrm{s.t.} & \nabla g_j(x_k)^\top 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{split}\]

ここでは制約充足フェイズの場合と同様に \(G_k\) は零行列あるいはラグランジュ関数のヘッセ行列，または，その近似行列とする．この問題は \(\Delta_T = \Delta_{T_k}\) から始め \(s_\rho\) が一定の制約充足度を満たすようになるまで \(\Delta_T\) を半減させつつ繰り返し解く．この内部反復により最終的に得られた \(s_\rho\) を \(s_{\rho_k}\) として，\(s_{\rho_k}\) による目的関数の減少量が，その二次近似関数の減少量と比べて十分だった場合は，\(\Delta_T\) を拡大し \(\Delta_{T_{k+1}} = 2 \Delta_T\) とする．逆に一定比率以上で二次近似関数の減少量の方が上回った時は \(\Delta_{T_{k+1}} = \frac{1}{2} \Delta_T\) として，どちらでもない場合は \(\Delta_{T_{k+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\) がラグランジュ関数のヘッセ行列，あるいは近似行列であった場合，各反復において二次計画問題を解くことになる．問題によっては，二次計画問題の求解が高コストになる事もある．そのために，Nuorium Optimizerでは，この二次計画問題を直接解くのではなく，線形計画問題と，その結果得られる等式のみの二次計画問題の解を組合せ，近似的な解を構成するという工夫をしている．