「分離問題」の版間の差分
ナビゲーションに移動
検索に移動
細 ("分離問題" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_*\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_* > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている. | 凸集合 <math>P \subseteq {\mathbf R}^n\,</math> が与えられているとする. このとき, 任意のベクトル <math>x_* \in {\mathbf R}^n\,</math> に対して<math>x_* \in P\,</math> か否かを判定し, <math>x_* \not\in P\,</math>ならば, <math>P\,</math> と <math>x_*\,</math> を分離する不等式を求める, すなわち<math>a^{\mathrm T} x \leq b\,</math> <math>(\forall x \in P)\,</math> かつ<math>a^{\rm T} x_* > b\,</math> なる <math>a \in {\mathbf R}^n\,</math> および <math>b \in {\mathbf R}\,</math>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている. | ||
| + | |||
| + | [[Category:線形計画|ぶんりもんだい]] | ||
2008年11月13日 (木) 15:57時点における最新版
【ぶんりもんだい (separation problem)】
凸集合 が与えられているとする. このとき, 任意のベクトル に対して か否かを判定し, ならば, と を分離する不等式を求める, すなわち かつ なる および を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.
