凸集之分离与支撑超平面 _超平面

分离与支撑超平面（ and）
1.分离超平面定理
定理：假设C和D是两个不相交的凸集，即C∩D=? 。然后存在一个a≠0和b，这样aTx≤b用于所有x∈C，aTx≥b用于所有x∈D 。
换句话说，仿射函数aTx?b,在C上非正，在D上非负.
超平面{x|aTx=b}称为分离C和D的分离超平面，或者称为分离C和D 。
如图所示，超平面{x|aTx=b}分离了不相交的凸集C和 D. 仿射函数aTx?b在C上非正，在C上非负 D.
分离超平面定理的证明
我们假设C和D之间的（欧几里得）距离，定义为
并且是正的，同时存在点c∈C和d∈D达到最小距离，即||c?d||^2=dist(C，D) 。（满足这些条件，例如，当C和D闭合且一组有界时，这些条件。）
其中
我们将证明仿射函数
在C上非正，在D上非负，即超平面{x|aTx=b}分隔C和D 。该超平面垂直于c和d之间的线段，并穿过其中点。
我们首先证明f在D上是非负的。f在C上是非正的证明是相似的(或者接下来通过交换C和D并考虑?f) 。假设有一个u∈D点
我们可以将f(u)表示为
我们看到意味着(d?c)T(u?d)
所以对于一些小的t>0，与t≤1，我们有
严格分离
我们上面构造的分离超平面满足所有x∈C的aTxb x∈D. 这被称为严格分离集C和 D. 简单的例子表明，一般来说，不相交凸集不需要被超平面严格分离，但在许多特殊情况下，可以建立严格分离。
支撑超平面
假设C?Rn和x0是其边界bdC上的一个点，即，
如果=0对所有x∈C满足aTx≤aTx0，那么超平面{x|aTx=aTx0}在x0点被称为对C的支持超平面。
这相当于这样说点x0和集合C由超平面{x|aTx=aTx0}分开。几何解释是超平面{x|aTx=aTx0}在x0处与C相切，而半空间{x|aTx≤aTx0}包含C 。
【凸集之分离与支撑超平面】如图所示，超平面{x|aTx=aTx0}支持在x0处的C 。