修正 KKT 条件#
読み: しゅうせいけーけーてぃーじょうけん
英名: Modified Karush-Kuhn-Tucker Conditions
別名: バリア KKT 条件,BKKT 条件
適当にスラック変数を導入する事により,一般の非線形計画問題は次の標準形に直す事が可能である.
この標準形に対する KKT 条件は次の形で表わされる.
但し \(y,z\) はそれぞれ制約 \(g(x)=0, \ x \ge 0\) の双対変数であり,
であるものとする.
一般に数理計画問題に対して内点法を適用する際,KKT 条件の中の相補性条件 \(XZe=0\) はそのまま取り扱う事ができない.この際に適切な \(\mu > 0\) を設定し,相補性条件を \(XZe=\mu e\) と置きなおす.この様に修正された KKT 条件を修正 KKT 条件と呼ぶ.
具体的に修正 KKT条件は次のように書き下せる [1].
修正 KKT 条件はバリア KKT 条件(Barrier Karush-Kuhn-Tucker Conditions)と呼ばれる事もある.これは修正 KKT 条件が,以下に述べるバリア関数最小化問題に対する KKT 条件とも見なせるからである.
内点法では \(\mu \downarrow 0\) と降下させながら,逐次修正 KKT 条件を満たす点を求める事で,KKT 条件を満たす解を得る.非線形計画問題に対する内点法では,\(\mu\) を更新する操作の事を「外部反復」,修正 KKT 条件を満たす点を求める反復操作の事を「内部反復」と呼んで区別している. 線形計画問題の場合,理論的には内部反復に相当する操作は各 1 回で十分である.
修正 KKT 条件を満たす点の集合は中心パス (Center Path) と呼ばれ,一般に滑らかである事が知られている.
関連
参考文献
Hiroshi Yamashita. A globally convergent primal-dual interior point method for constrained optimization. Optimization Methods and Software, 10(2):443–469, jan 1998. URL: https://www.tandfonline.com/doi/full/10.1080/10556789808805723, doi:10.1080/10556789808805723.