【ぽてんしゃるかんすう (potential function)】
標準形の線形計画問題「 min. c ⊤ x s.t. A x = b , x ≥ 0 {\displaystyle {\mbox{min. }}\ c^{\top }x\ {\mbox{s.t.}}\ Ax=b,\ x\geq 0\,} ( A {\displaystyle A\,} は m × n {\displaystyle m\times n\,} 行列, b ∈ R m {\displaystyle b\in {\mathbf {R} }^{m}\,} , c ∈ R n {\displaystyle c\in {\mathbf {R} }^{n}\,} )」 に対する内点法で用いられるポテンシャル関数は,
f ( x : ρ ) := ( n + ρ ) ln ( c ⊤ x − c ∗ ) − ∑ j = 1 n ln x j {\displaystyle f(x:\rho ):=(n+\rho )\ln(c^{\top }x-c^{*})-\sum _{j=1}^{n}\ln x_{j}\,}
( c ∗ {\displaystyle c^{*}\,} は主問題の最小値, ρ {\displaystyle \rho \,} はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の ρ > 0 {\displaystyle \rho >0\,} に対して, 正領域内の許容解の点列 { x k } {\displaystyle \{x^{k}\}\,} が f ( x k ) → − ∞ {\displaystyle f(x^{k})\rightarrow -\infty \,} であるとき, その集積点はすべて最適解という性質をもつ.
(
は
行列, 
, 
)」 に対する内点法で用いられるポテンシャル関数は,
は主問題の最小値, 
はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の
に対して, 正領域内の許容解の点列
が
であるとき, その集積点はすべて最適解という性質をもつ.