aiwiki.page
中文
数学 / 几何与拓扑 / hyperplane-separation-theorem

超平面分离定理

超平面分离定理给出将凸集置于超平面两侧的条件,是凸分析与优化的重要基础。

30 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
凸集超平面凸优化泛函分析欧几里得空间内积半空间向量空间超平面分离…

超平面分离定理是一族定理,指出在适当条件下,两个凸集可以由一个超平面分离。在有限维实空间中,对于任意两个非空、不相交的凸集,都存在一个非零线性泛函,使其在一个集合上的取值不大于在另一个集合上的取值。紧性与闭性等更强的假设,可以保证两集合之间存在正的间隔。这些结果将凸集的几何性质与线性不等式联系起来,是凸优化和泛函分析中许多理论的基础。

几何与代数表述

在欧几里得空间 Rn\mathbb{R}^n 中,仿射超平面的形式为

H={x∈Rn:aTx=α},H=\{x\in\mathbb{R}^n:a^\mathsf{T}x=\alpha\},

其中,a≠0a\neq 0 是法向量,α∈R\alpha\in\mathbb{R}。记号 aTxa^\mathsf{T}x 表示欧几里得内积。该超平面是以下两个闭半空间的边界:

H−={x:aTx≤α},H+={x:aTx≥α}.H^-=\{x:a^\mathsf{T}x\leq\alpha\}, \qquad H^+=\{x:a^\mathsf{T}x\geq\alpha\}.

若满足

aTx≤α≤aTyfor every x∈A, y∈B.a^\mathsf{T}x\leq\alpha\leq a^\mathsf{T}y \qquad \text{for every }x\in A,\ y\in B.

则称该超平面分离集合 AA 和 BB。

等价地,

sup⁡x∈AaTx≤inf⁡y∈BaTy.\sup_{x\in A}a^\mathsf{T}x \leq \inf_{y\in B}a^\mathsf{T}y.

法向量必须非零,否则这些不等式不提供任何几何信息。

更一般地,在实向量空间中,分离关系通过非零线性泛函 ff 表述。在拓扑向量空间中,分离定理通常要求 ff 连续。此时,分离超平面就是水平集 {x:f(x)=α}\{x:f(x)=\alpha\}。

分离的不同程度

几种互不等价的结论都被称为“分离”。不同文献的术语用法有所差异,因此,相较于名称,不等式本身更为明确。

弱分离

若存在 a≠0a\neq 0 和 α\alpha,使得

aTx≤α≤aTy(x∈A, y∈B).a^\mathsf{T}x\leq\alpha\leq a^\mathsf{T}y \quad(x\in A,\ y\in B).

则称两集合弱分离。

其中一个集合或两个集合都可以与超平面相交。两个集合甚至可以完全包含在超平面内,因此仅有弱分离并不意味着它们不相交。

真分离

若一个弱分离满足 A∪BA\cup B 不包含在分离超平面内,则称其为真分离。等价地,至少有一个分离不等式在至少一个点处严格成立。

这排除了仅仅将两个集合置于同一个超平面内的分离情形。

严格分离

按照一种常见约定,严格分离是指

aTx<α<aTy(x∈A, y∈B).a^\mathsf{T}x<\alpha<a^\mathsf{T}y \quad(x\in A,\ y\in B).

每个点都严格位于其所属的一侧,但集合可以任意接近超平面。特别地,逐点成立的严格不等式不一定意味着在 AA 上的上确界与在 BB 上的下确界之间存在正的间隔。

强分离

强分离要求

sup⁡x∈AaTx<inf⁡y∈BaTy.\sup_{x\in A}a^\mathsf{T}x < \inf_{y\in B}a^\mathsf{T}y.

等价地,存在 a≠0a\neq 0、α\alpha 和 ε>0\varepsilon>0,使得

aTx≤α−ε,aTy≥α+ε.a^\mathsf{T}x\leq\alpha-\varepsilon, \qquad a^\mathsf{T}y\geq\alpha+\varepsilon.

这给出了统一的分离间隔。由柯西—施瓦茨不等式可知,两集合之间的欧几里得距离至少为 2ε/∥a∥2\varepsilon/\|a\|。

有些作者用“严格分离”指代这一更强的条件。

有限维空间中的主要定理

设 A,B⊆RnA,B\subseteq\mathbb{R}^n 非空且为凸集。

不相交的凸集

若 A∩B=∅A\cap B=\varnothing,则 AA 和 BB 可以真分离,因而也可以弱分离。

这一结论不需要开性、闭性或有界性假设。然而,仅有不相交性并不能保证严格分离或强分离。

一个更一般的判据使用相对内部,即集合在包含它的最小仿射空间中的内部。两个非空凸集可以真分离,当且仅当它们的相对内部不相交。因此,即使集合具有公共边界点,也可能真分离。

开凸集

若 AA 是开集,且与 BB 不相交,则可以选取分离超平面,使得

aTx<α≤aTy(x∈A, y∈B).a^\mathsf{T}x<\alpha\leq a^\mathsf{T}y \quad(x\in A,\ y\in B).

若两个集合都是开集,则两侧的不等式都可以取为严格不等式:

aTx<α<aTy.a^\mathsf{T}x<\alpha<a^\mathsf{T}y.

开性本身并不能保证统一的分离间隔。

一个紧集与一个闭集

若 AA 是紧集,BB 是闭集,且两集合不相交,则它们可以强分离。

特别地,非空闭凸集外的一点可以与该集合强分离。其中一个集合的紧性,排除了两个不相交集合仅在“无穷远处”彼此趋近的情形。

正距离

更一般地,若

dist⁡(A,B)=inf⁡{∥x−y∥:x∈A, y∈B}>0,\operatorname{dist}(A,B) = \inf\{\|x-y\|:x\in A,\ y\in B\}>0,

则这两个凸集可以强分离。反过来,强分离意味着距离为正。

因此,在有限维欧几里得空间中,正距离是两个非空凸集可以强分离的充要条件。仅有两个集合的闭性并不足够。

证明思路

最近点与垂直分离超平面

设 AA 是紧集,BB 是闭集,且它们非空、凸、不相交。存在点 p∈Ap\in A 和 q∈Bq\in B,使两点间的距离等于两集合之间的正的最小距离。令

a=q−p.a=q-p.

对于任意 x∈Ax\in A,由凸性可知,当 0≤t≤10\leq t\leq1 时,p+t(x−p)∈Ap+t(x-p)\in A。由于 p,qp,q 实现最小距离,在 t=0t=0 处对距离的平方求导,得到

aT(x−p)≤0.a^\mathsf{T}(x-p)\leq0.

对 BB 作类似论证,可得

aT(y−q)≥0(y∈B).a^\mathsf{T}(y-q)\geq0 \qquad(y\in B).

因此,

sup⁡x∈AaTx≤aTp<aTq≤inf⁡y∈BaTy,\sup_{x\in A}a^\mathsf{T}x \leq a^\mathsf{T}p < a^\mathsf{T}q \leq \inf_{y\in B}a^\mathsf{T}y,

这是因为

aT(q−p)=∥q−p∥2>0.a^\mathsf{T}(q-p)=\|q-p\|^2>0.

经过连接 pp 与 qq 的线段中点、且垂直于该线段的超平面,将这两个集合强分离。

归结为与原点的分离

对于一般的不相交凸集,考虑它们的差集

C=B−A={y−x:y∈B, x∈A}.C=B-A=\{y-x:y\in B,\ x\in A\}.

该集合为凸集,且不包含 00。由点与凸集的分离定理,存在非零向量 aa,满足

aTc≥0(c∈C).a^\mathsf{T}c\geq0 \qquad(c\in C).

于是

aTx≤aTy(x∈A, y∈B),a^\mathsf{T}x\leq a^\mathsf{T}y \qquad(x\in A,\ y\in B),

从而得到一个弱分离超平面。

一种有限维证明方法是将 00 与 CC 的闭包分离。若 00 位于该闭包之外,则可采用最近点论证。若 00 位于其边界上,则可以对附近外部点所对应的分离法向量作归一化;由单位球面的紧性,可取出收敛子列,并得到一个非零的极限法向量。在仿射包内进一步细化这一论证,即可得到真分离。

支撑超平面

与此密切相关的结果是支撑超平面定理。若 C⊆RnC\subseteq\mathbb{R}^n 是非空凸集,且 x0x_0 是 CC 的边界点,则存在 a≠0a\neq0,使得

aTx≤aTx0(x∈C).a^\mathsf{T}x\leq a^\mathsf{T}x_0 \qquad(x\in C).

因此,经过 x0x_0 的这一超平面是某个包含 CC 的半空间的边界。

对于内部为空的集合,支撑超平面可能包含整个集合。采用相对内部的表述,可以将这种包含情形与真正体现集合在其仿射包内边界的支撑情形区分开来。

点与集合的分离还给出了表示式

C=⋂{H−:H− is a closed half-space containing C}C= \bigcap \{H^-:H^-\text{ is a closed half-space containing }C\}

它对每个非空闭凸集 C⊆RnC\subseteq\mathbb{R}^n 都成立。因此,一个集合能够表示为闭半空间的交,所需的性质恰好就是凸性与闭性。

无限维版本

在实局部凸拓扑向量空间中,分离通过连续线性泛函表述。其中两个核心版本是:

  • 非空开凸集与一个和它不相交的非空凸集可以分离,且开集一侧的不等式可以严格成立。
  • 非空闭凸集外的一点可以与该集合强分离。

这些陈述与哈恩—巴拿赫定理密切相关。其分析形式用于延拓受控的线性泛函,几何形式则给出分离泛函。连续分离泛函属于连续对偶空间。

每个赋范向量空间都是局部凸的,因此上述版本在赋范向量空间中均适用。与有限维情形不同,闭有界集不一定是紧集,实现最小距离的点也不一定存在。因此,泛函分析中的证明不能总是依赖最近点对。

局部凸性是实质性的条件:缺少这一条件时,拓扑向量空间可能没有足够多的连续线性泛函来分离点与闭凸集。

应用

优化与不可行性证书

在数学优化中,分离将几何上的不相容性转化为线性证书。对于闭凸可行集外的一点,可以用一个有效线性不等式将其排除,同时保留所有可行点。

这一原理是基于分离的算法以及法尔卡斯引理等结果的基础。对于实矩阵 MM 和向量 bb,下列两个系统中恰有一个有解:

Mx=b,x≥0,Mx=b,\qquad x\geq0,

或

MTy≥0,bTy<0.M^\mathsf{T}y\geq0,\qquad b^\mathsf{T}y<0.

第二个系统的解提供了第一个系统无解的证书。

分离也是拉格朗日对偶以及卡鲁什—库恩—塔克条件推导的基础。所得结论的强弱取决于适当的正则性假设;仅有凸性并不能保证所有强对偶结论成立。

凸函数

凸函数的上图是凸集。上图的支撑超平面给出仿射下界,并在相应条件成立时给出次梯度。

对于可微凸函数 f:Rn→Rf:\mathbb{R}^n\to\mathbb{R},由此得到

f(y)≥f(x)+∇f(x)T(y−x).f(y)\geq f(x)+\nabla f(x)^\mathsf{T}(y-x).

这里,梯度决定了上图在 (x,f(x))(x,f(x)) 处的支撑超平面的斜率。

线性分类

在机器学习中,有限的带标签数据集存在严格的仿射线性分离超平面,当且仅当两类数据的凸包不相交。由于有限点集的凸包是紧集,不相交性也意味着存在正的分离间隔。

支持向量机利用这一几何性质寻找最大间隔分离超平面。若两个凸包相交,则在原始特征空间中,不存在能严格分离所有训练点的超平面。

局限性与反例

不相交的闭凸集不一定能强分离

考虑

A={(x,y)∈R2:y≥ex},B={(x,y)∈R2:y≤0}.A=\{(x,y)\in\mathbb{R}^2:y\geq e^x\}, \qquad B=\{(x,y)\in\mathbb{R}^2:y\leq0\}.

两者都是闭凸集,且互不相交。然而,它们的距离为零,因为当 x→−∞x\to-\infty 时,ex→0e^x\to0。因此,它们不能强分离。

按照上文定义的双侧逐点严格不等式,它们也不能严格分离。BB 的水平边界迫使任何分离超平面都必须是水平的,而 AA 又可以任意接近这一边界。不过,它们确实可以单侧严格分离:

yB≤0<yA.y_B\leq0<y_A.

凸性通常不可省略

令

A={(−1,0),(1,0)},B={(0,−1),(0,1)}.A=\{(-1,0),(1,0)\}, \qquad B=\{(0,-1),(0,1)\}.

这两个集合不相交,但不存在将它们弱分离的非零线性泛函。任何分离泛函也必然分离它们的凸包;而这两条水平与竖直线段会迫使该泛函在两个坐标方向上的取值都为零。

更一般地,一个线性不等式若在某集合上成立,就也在其凸包上成立。因此,超平面可分离性取决于集合的凸包,而不仅仅取决于原集合是否相交。