分離問題のソースを表示

'''【ぶんりもんだい (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>を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.