分離問題

【ぶんりもんだい (separation problem)】

凸集合 $P\subseteq {\mathbf {R} }^{n}\,$ が与えられているとする. このとき, 任意のベクトル $x_{*}\in {\mathbf {R} }^{n}\,$ に対して$x_{*}\in P\,$ か否かを判定し, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_* \not\in P\,} ならば, $P\,$ と $x_{*}\,$ を分離する不等式を求める, すなわち構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a^{\mathrm T} x \leq b\,} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\forall x \in P)\,} かつ$a^{\rm {T}}x_{*}>b\,$ なる $a\in {\mathbf {R} }^{n}\,$ および $b\in {\mathbf {R} }\,$を求める問題を分離問題と呼ぶ. 凸集合に関する分離問題と(線形関数)最適化問題に対して,一方が多項式時間で解けるならば, 他方も多項式時間で解けることが証明されている.