最適化セミナーのご案内

B.7 外点法

 内点法は変数が正の領域(内点)に反復点を取る方法ですが,B.1.1で取り上げた問題を

\begin{align*} & f(x) + \rho \sum_i |x_i|_{-},\quad x \in \mathbf{R}^n, \\ & g(x) = 0 \end{align*}

のように変形して(実際にはこの問題の滑らかな近似を考えます),非負制約を除去,このKKT条件を解くと考えると,やはり直線探索・信頼領域法に基づく最適化アルゴリズムを構成することができ,大域的収束性を保証することができます.Numerical Optimizerに組み込まれているlepmは直線探索法に基づく外点法,tepmは信頼領域法に基づく外点法です.

 内点法とほぼ同等のパフォーマンスを示しますが,$\rho$の大きさが相対的に小さいと非負制約を満たさない実行不可能な解に収束することはあり得ます.逆に実行不可能な問題でも,等式制約を満たし,なるべく最適解に近い点を返すことが期待されます.$\rho$の値はパラメータexhroですることができます.

 内点法に比べてのメリットは,内点以外の点からも出発できるという点です.内点法では変数値を,非負制約を満たす内点に移動してから反復計算をスタートさせなければならないので,良い初期値が得られている場合でも,その操作により情報を失ってしまいます.外点法なら初期値を加工することなく,そのまま用いることができますので,良い初期値が得られている場合やリスタート時に比較的良好な性能が得られます.


 

 

上に戻る