修正 KKT 条件#

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

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

(59)#\[\begin{split}\begin{array}{l} \begin{array}{ll} \min & f(x) \\ \mathrm{s.t.} & g(x) = 0 \\ & x \ge 0 \end{array} \\ \begin{array}{l} x \in \mathbb{R}^n, \ f \colon \mathbb{R}^n \to \mathbb{R}, \ g \colon \mathbb{R}^n \to \mathbb{R} \end{array} \end{array}\end{split}\]

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

(60)#\[\begin{split}\begin{array}{l} \begin{pmatrix} \nabla_x L(x,y,z) \\ g(x) \\ XZe \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \\ x \ge 0, \ z \ge 0 \end{array}\end{split}\]

但し \(y,z\) はそれぞれ制約 \(g(x)=0, \ x \ge 0\) の双対変数であり，

(61)#\[\begin{split}\begin{array}{l} L(x,y,z) = f(x) - y^\top g(x) - z^\top x \\ X= \begin{pmatrix} x_1 & & \\ & \ddots & \\ & & x_n \end{pmatrix} , \ Z= \begin{pmatrix} z_1 & & \\ & \ddots & \\ & & z_n \end{pmatrix} , \ e= \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix} \end{array}\end{split}\]

であるものとする．

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

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

(62)#\[\begin{split}\begin{array}{l} \begin{pmatrix} \nabla_x L(x,y,z) \\ g(x) \\ XZe \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \mu e \end{pmatrix} \\ x \ge 0, \ z \ge 0 \end{array}\end{split}\]

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

(63)#\[\begin{split}\begin{array}{l} \begin{array}{ll} \min & f(x) - \mu \sum_{i=1}^n{\log(x_i)}\\ \mathrm{s.t.} & g(x) = 0 \end{array} \\ \begin{array}{l} x \in \mathbb{R}_+^n, \ f \colon \mathbb{R}^n \to \mathbb{R}, \ g \colon \mathbb{R}^n \to \mathbb{R} \end{array} \end{array}\end{split}\]

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

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