「カーマーカー法」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
1984年にカーマーカーが提案した, 初めての内点法. 「<math>\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0 \,</math> (<math>A \,</math>は<math>m \times n \,</math>行列, <math>c \in \mathbf{R}^n \,</math>, <math>e \in \mathbf{R}^n \,</math>は 要素がすべて<math>1 \,</math>のベクトル)」の線形計画問題に対して, 「(1) <math>A \,</math>の階数は<math>m \,</math>, (2)<math>A(e/n)=0 \,</math>, (iii)最適値は<math>0 \,</math>」の仮定の下で, 初期点 <math>x^0 =e/n \,</math> から最適解に収束する点列 <math>\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\} \,</math> を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる. | 1984年にカーマーカーが提案した, 初めての内点法. 「<math>\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0 \,</math> (<math>A \,</math>は<math>m \times n \,</math>行列, <math>c \in \mathbf{R}^n \,</math>, <math>e \in \mathbf{R}^n \,</math>は 要素がすべて<math>1 \,</math>のベクトル)」の線形計画問題に対して, 「(1) <math>A \,</math>の階数は<math>m \,</math>, (2)<math>A(e/n)=0 \,</math>, (iii)最適値は<math>0 \,</math>」の仮定の下で, 初期点 <math>x^0 =e/n \,</math> から最適解に収束する点列 <math>\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\} \,</math> を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる. | ||
| + | |||
| + | [[Category:線形計画|かーまーかーほう]] | ||
| + | |||
| + | [[Category:非線形計画|かーまーかーほう]] | ||
2008年11月7日 (金) 14:54時点における最新版
【かーまーかーほう (Karmarkar's algorithm)】
1984年にカーマーカーが提案した, 初めての内点法. 「 (は行列, , は 要素がすべてのベクトル)」の線形計画問題に対して, 「(1) の階数は, (2), (iii)最適値は」の仮定の下で, 初期点 から最適解に収束する点列 を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.
