分離問題

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

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