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

出典: ORWiki

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

標準形の線形計画問題「 \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\,)」 に対する内点法で用いられるポテンシャル関数は,


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\, であるとき, その集積点はすべて最適解という性質をもつ.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%83%9D%E3%83%86%E3%83%B3%E3%82%B7%E3%83%A3%E3%83%AB%E9%96%A2%E6%95%B0_%28%E5%86%85%E7%82%B9%E6%B3%95%E3%81%AE%29" より作成