「分離問題」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【ぶんりもんだい (separation problem)】 凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$...') |
|||
| 1行目: | 1行目: | ||
【ぶんりもんだい (separation problem)】 | 【ぶんりもんだい (separation problem)】 | ||
| − | + | 凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_*$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b$ $(\forall x \in P)$ かつ$a^{\rm T} x_* > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている. | |
2007年7月13日 (金) 10:53時点における版
【ぶんりもんだい (separation problem)】
凸集合 $P \subseteq {\bf R}^n$ が与えられているとする. このとき, 任意のベクトル $x_* \in {\bf R}^n$ に対して$x_* \in P$ か否かを判定し, $x_* \not\in P$ならば, $P$ と $x_*$ を分離する不等式を求める, すなわち$a^{\rm T} x \leq b$ $(\forall x \in P)$ かつ$a^{\rm T} x_* > b$ なる $a \in {\bf R}^n$ および $b \in {\bf R}$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.