トップ > 数理計画用語集 > 修正 KKT 条件

数理計画用語集

修正 KKT 条件

読み:しゅうせいけーけーてぃーじょうけん
英名:Modified Karush-Kuhn-Tucker Conditions
別名:バリア KKT 条件,BKKT 条件
関連KKT 条件相補性条件

適当にスラック変数を導入する事により,一般の非線形計画問題は次の標準形に直す事が可能である.

equation

この標準形に対する KKT 条件は次の形で表わされる.

equation

但し equation はそれぞれ制約 equation双対変数であり,

equation

equation

であるものとする.

一般に数理計画問題に対して内点法を適用する際, KKT 条件の中の相補性条件 equation はそのまま取り扱う事ができない.この際に適切な equation を設定し,相補性条件equation と置きなおす.この様に修正された KKT 条件を修正 KKT 条件と呼ぶ.

具体的に修正 KKT条件は次のように書き下せる[1].

equation

修正 KKT 条件はバリア KKT 条件(Barrier Karush-Kuhn-Tucker Conditions)と呼ばれる事もある.これは修正 KKT 条件が,以下に述べるバリア関数最小化問題に対する KKT 条件とも見なせるからである.

equation

内点法では equation と降下させながら,逐次修正 KKT 条件を満たす点を求める事で, KKT 条件を満たす解を得る.非線形計画問題に対する内点法では,equation を更新する操作の事を「外部反復」,修正 KKT 条件を満たす点を求める反復操作の事を「内部反復」と呼んで区別している.線形計画問題の場合,理論的には内部反復に相当する操作は各 1 回で十分である.

修正 KKT 条件を満たす点の集合は中心パス(Center Path)と呼ばれ,一般に滑らかである事が知られている.

[参考]
[1] H.Yamashita, A globally convergent primal-dual interior point method for constrained optimization, Math. Programming, 1998