Separation Oracle

定义 Definition

separation oracle（分离预言机/分离判定器）：在凸优化与计算几何中，一种“黑盒”程序。给定一个点 \(x\) 与一个凸集合 \(K\)，它要么判断 \(x \in K\)（点在集合内），要么返回一条将 \(x\) 与 \(K\) 分开的超平面（通常以一个线性不等式/割平面表示），从而证明 \(x \notin K\)。
（该术语也常与 membership oracle 等一起出现；不同文献对输出形式的细节略有差异。）

发音 Pronunciation (IPA)

/ˌsɛpəˈreɪʃən ˈɔːrəkəl/

例句 Examples

We built a separation oracle to check whether a point lies inside the convex set.
我们构建了一个分离预言机，用来检查一个点是否位于该凸集合内部。

In the ellipsoid method, a separation oracle can replace an explicit list of constraints by generating a separating hyperplane whenever the current point is infeasible.
在椭球法中，分离预言机可以替代显式列出所有约束：当当前点不可行时，它会生成一个分离超平面作为“证据”。

词源 Etymology

separation 来自拉丁语 separare（分开、分离），oracle 原指“神谕/预言者”，在计算机科学里常借用来表示“能回答某类查询的黑盒”。组合起来，separation oracle 字面意思就是“能给出分离证据的黑盒回答器”：要么确认“在里面”，要么给出“把它分开”的线性证据（超平面/割）。

相关词 Related Words

• Oracle
• Separation
• Ellipsoid Method
• Convex Set
• Polytope
• Cutting Plane
• Constraint
• Feasibility
• Optimization
• Membership Oracle

文学与名著中的用例 Literary / Notable Works

• Geometric Algorithms and Combinatorial Optimization — Martin Grötschel, László Lovász, Alexander Schrijver（经典著作中系统讨论“分离”与“优化”的等价性与预言机模型）
• Convex Optimization — Stephen Boyd, Lieven Vandenberghe（介绍凸优化基础背景，相关算法思想中常提及分离/割平面观念）
• Interior-Point Polynomial Algorithms in Convex Programming — Yurii Nesterov, Arkadii Nemirovskii（凸优化理论与算法框架中涉及相关“预言机”与可行性判定思想）
• Combinatorial Optimization: Polyhedra and Efficiency — Alexander Schrijver（多面体、可行性与分离思想在组合优化中的权威来源之一）