凸优化12：超平面分离定理

超平面分离定理

假设和是两个不相交的凸集，即，那么存在和使得对于所有的有、对于所有有。

换言之，仿射函数在中为非正，而在中为非负。

超平面称为和的分离超平面，或称超平面分离了集合和。

证明

这里只考虑特殊情况。使用距离，将集合和的距离定义为并且存在达到这个最小距离，即.

定义

我们将会得到一个仿射函数

在中非正而在中非负，即分离了和。这个超平面是连接之间的线段的中垂面（如同上面的图中的形状），直觉上来讲是成立的。

我们首先来证明在中非负。关于在中非正的证明是相似的。

假设存在点，且.这意味着

可以将表示为:

.

结合上面的两个式子，可以观察到

因此对于足够小的及，我们有

即比更加靠近。因为是包含的凸集，我们有，但这和我们的假设是相违背的。

严格分离

如果之前构造的分离超平面满足更强的条件，即对于任意有并且对于有，则称其为集合和的严格分离。

超平面分离定理的逆定理

超平面分离定理的逆定理（即分离超平面的存在表明和不相交）是不成立的，除非在凸性之外在给这两个集合附加其他约束。一个反例是，超平面可以分离和。

给增加条件后，可以得到超平面分离定理的一些逆定理。例如，设是凸集，是开集，若存在一个仿射函数，其在中非正而在中非负，那么不相交。

将逆定理和原定理相结合，可以得到如下结论：任何两个凸集如果其中至少有一个是开集，那么当且仅当存在分离超平面的时候，它们不相交。