「ポテンシャル関数 (内点法の)」の版間の差分
ナビゲーションに移動
検索に移動
| 5行目: | 5行目: | ||
<center> | <center> | ||
<math>f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,</math> | <math>f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,</math> | ||
| − | <center> | + | </center> |
(<math>c^*\,</math>は主問題の最小値, <math>\rho\,</math>はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の<math>\rho > 0\,</math>に対して, 正領域内の許容解の点列<math>\{x^k\}\,</math>が<math>f(x^k) \rightarrow -\infty\,</math> であるとき, その集積点はすべて最適解という性質をもつ. | (<math>c^*\,</math>は主問題の最小値, <math>\rho\,</math>はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の<math>\rho > 0\,</math>に対して, 正領域内の許容解の点列<math>\{x^k\}\,</math>が<math>f(x^k) \rightarrow -\infty\,</math> であるとき, その集積点はすべて最適解という性質をもつ. | ||
2007年7月14日 (土) 15:29時点における版
【ぽてんしゃるかんすう (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\,}
(は行列, , )」 に対する内点法で用いられるポテンシャル関数は,
(構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle c^{*}\,}
は主問題の最小値, はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の構文解析に失敗 (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}\}\,}
が であるとき, その集積点はすべて最適解という性質をもつ.
