「ポテンシャル関数 (内点法の)」の版間の差分
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【ぽてんしゃるかんすう (potential function)】 | + | '''【ぽてんしゃるかんすう (potential function)】''' |
標準形の線形計画問題「 <math> \mbox{min. } \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0\,</math> (<math>A\,</math>は<math>m \times n\,</math>行列, <math>b \in {\mathbf R}^m\,</math>, <math>c \in {\mathbf R}^n\,</math>)」 に対する内点法で用いられるポテンシャル関数は,<br> | 標準形の線形計画問題「 <math> \mbox{min. } \ c^{\top}x \ \mbox{s.t.} \ Ax = b, \ x \geq 0\,</math> (<math>A\,</math>は<math>m \times n\,</math>行列, <math>b \in {\mathbf R}^m\,</math>, <math>c \in {\mathbf R}^n\,</math>)」 に対する内点法で用いられるポテンシャル関数は,<br> | ||
| + | |||
<center> | <center> | ||
| − | + | <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> であるとき, その集積点はすべて最適解という性質をもつ. | ||
| + | |||
| + | [[Category:線形計画|ぽてんしゃるかんすう]] | ||
2008年11月13日 (木) 21:55時点における最新版
【ぽてんしゃるかんすう (potential function)】
標準形の線形計画問題「 (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\,}
は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m \times n\,}
行列, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b \in {\mathbf R}^m\,}
, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c \in {\mathbf R}^n\,}
)」 に対する内点法で用いられるポテンシャル関数は,
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x:\rho) := (n+\rho)\ln(c^{\top}x -c^*)-\sum_{j=1}^n \ln x_j\,}
(構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c^*\,}
は主問題の最小値, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho\,}
はパラメータ)で与えられる. カーマーカーが初めて導入した関数であり, 既与の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho > 0\,}
に対して, 正領域内の許容解の点列構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \{x^k\}\,}
が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x^k) \rightarrow -\infty\,}
であるとき, その集積点はすべて最適解という性質をもつ.