ポテンシャル関数 (内点法の)

【ぽてんしゃるかんすう (potential function)】

標準形の線形計画問題「 $ \mbox{min. } \ c^{\top}x  \  \mbox{s.t.} \ Ax = b, \ x \geq 0$ ($A$は$m \times n$行列, $b \in {\bf R}^m$, $c \in {\bf R}^n$)」 に対する内点法で用いられるポテンシャル関数は,

 \[
f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j
\]

($c^*$は主問題の最小値, $\rho$はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の$\rho > 0$に対して, 正領域内の許容解の点列$\{x^k\}$が$f(x^k) \rightarrow -\infty$ であるとき, その集積点はすべて最適解という性質をもつ.