「分離問題」の版間の差分
ナビゲーションに移動
検索に移動
| 1行目: | 1行目: | ||
| − | 【ぶんりもんだい (separation problem)】 | + | '''【ぶんりもんだい (separation problem)】''' |
凸集合 <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>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている. | ||
2007年7月17日 (火) 13:59時点における版
【ぶんりもんだい (separation problem)】
凸集合 が与えられているとする. このとき, 任意のベクトル に対して か否かを判定し, ならば, と を分離する不等式を求める, すなわち かつ なる および を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.
