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

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

標準形の線形計画問題「 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{min. }}\ c^{\top }x\ {\mbox{s.t.}}\ Ax=b,\ x\geq 0\,} ($A\,$は$m\times n\,$行列, $b\in {\mathbf {R} }^{m}\,$, $c\in {\mathbf {R} }^{n}\,$)」 に対する内点法で用いられるポテンシャル関数は,

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x:\rho ):=(n+\rho )\ln(c^{\top }x-c^{*})-\sum _{j=1}^{n}\ln x_{j}\,}

(構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle c^{*}\,} は主問題の最小値, $\rho \,$はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \rho >0\,} に対して, 正領域内の許容解の点列構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{x^{k}\}\,} が$f(x^{k})\rightarrow -\infty \,$ であるとき, その集積点はすべて最適解という性質をもつ.