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

B.1.4 線形計画問題専用内点法

　問題が線形の場合，KKT条件

\begin{align} \nabla_x L(x,y,z) & = 0, \nonumber \\ g(x) &= 0, \nonumber \\ XZe &= 0 \end{align}

の第1式，第2式は線形であり，非線形なのは第3式のみとなります．この方程式系に関するステップ幅1のニュートン法を適用すると線形な式の残差は原理的に零になり，非線形な第3式のみに

\[\Delta X_N \cdot \Delta Z_N e\]

なる形の残差が現れます（$\Delta X_N$，$\Delta Z_N$はニュートン法のステップ方向を対角に並べた行列）．この式にこの残差が発生することを見越してニュートン法のステップ方向を修正する（高次方向（Higher Order）の修正を加える）ことによって，より良いステップ方向を得ることができます．ニュートン法のステップ方向修正分を計算するためにはニュートン法のステップ方向の計算時に得られる副産物を有効に利用できるため，少ない計算コストでニュートン方向を改善することができ，計算を効率化することができます．

　

　Nuorium Optimizerにはこのことを利用し，さらに問題が線形であることに特化したチューニングを加えた手法が組み込まれています．

B.1.3 信頼領域を利用する方法
B.1.5 半正定値計画問題専用内点法

 

 

上に戻る