AI 与工程数学 / 系统课时

用线段测试判断集合是否凸

用线段测试判断集合是否凸

判断一个约束集合是否为凸集,核心不在于它看起来是否“圆润”,而是任取集合中的两点后,它们之间整条线段是否仍留在集合内。本节用这条定义快速识别半空间、球和仿射集合,并用孔洞与分离区域构造反例。

学习目标

  • 用线段测试准确写出凸集的判定条件
  • 判断半空间、欧氏球和仿射集合为什么是凸集
  • 通过一个反例证明含孔洞或分离区域的集合不是凸集

线段测试的数学定义

设集合 C⊆RnC \subseteq \mathbb{R}^n。如果对任意 x,y∈Cx,y\in C 和任意 θ∈[0,1]\theta\in[0,1],都有

θx+(1−θ)y∈C,\theta x+(1-\theta)y\in C,

那么 CC 就是凸集。

式子 θx+(1−θ)y\theta x+(1-\theta)y 描述从 yy 移动到 xx 的整条线段:θ=0\theta=0 时得到 yy,θ=1\theta=1 时得到 xx,中间值则对应两点之间的位置。因此,凸集的本质就是集合中任意两点之间不存在“越界”的线段部分。

凸集与非凸集的线段测试对比

证明一个集合是凸集时,需要说明所有点对和所有 θ\theta 都满足条件;证明它不是凸集则简单得多,只需要找到一组 xx、yy 和一个 θ\theta,使组合点落到集合外即可。

常见凸集为什么通过测试

半空间可以写成

C={x∣aTx≤b}.C=\{x\mid a^Tx\le b\}.

若 x,y∈Cx,y\in C,则 aTx≤ba^Tx\le b、aTy≤ba^Ty\le b。于是对 θ∈[0,1]\theta\in[0,1],

aT(θx+(1−θ)y)=θaTx+(1−θ)aTy≤b.a^T(\theta x+(1-\theta)y)=\theta a^Tx+(1-\theta)a^Ty\le b.

所以组合点仍在半空间中。

欧氏球

C={x∣∥x−c∥2≤r}C=\{x\mid \|x-c\|_2\le r\}

同样是凸集。由三角不等式可得

∥θx+(1−θ)y−c∥2≤θ∥x−c∥2+(1−θ)∥y−c∥2≤r.\|\theta x+(1-\theta)y-c\|_2\le \theta\|x-c\|_2+(1-\theta)\|y-c\|_2\le r.

仿射集合 C={x∣Ax=b}C=\{x\mid Ax=b\} 也满足线段测试,因为 Ax=Ay=bAx=Ay=b 时,

A(θx+(1−θ)y)=θb+(1−θ)b=b.A(\theta x+(1-\theta)y)=\theta b+(1-\theta)b=b.

这些结论在优化建模中很实用:线性等式、线性不等式和范数球约束组合起来,往往仍能形成凸可行域。

用一个反例否定凸性

考虑二维圆环

C={x∈R2∣1≤∥x∥2≤2}.C=\{x\in\mathbb{R}^2\mid 1\le\|x\|_2\le2\}.

取 x=(1.5,0)x=(1.5,0) 和 y=(−1.5,0)y=(-1.5,0)。两点都位于圆环中,但令 θ=0.5\theta=0.5,其中点为 (0,0)(0,0),其范数为 00,落入圆环中央的孔洞,因此圆环不是凸集。

下面的程序直接验证这个反例。它只能帮助寻找或确认反例,有限次采样本身不能证明一个集合对所有点都凸。

python
import numpy as np


def in_annulus(p: np.ndarray) -> bool:
    radius = np.linalg.norm(p)
    return 1.0 <= radius <= 2.0


x = np.array([1.5, 0.0])
y = np.array([-1.5, 0.0])
theta = 0.5
mid = theta * x + (1.0 - theta) * y

print(in_annulus(x))
print(in_annulus(y))
print(mid)
print(in_annulus(mid))

预期输出:

text
True
True
[0. 0.]
False

同样地,如果一个集合由两块互不相连的区域组成,通常也能分别在两块区域中各取一点,使连接线段经过集合外部,从而立即得到非凸性反例。

判断约束集合时的实用顺序

面对一个新的可行域,可以先看它是否能直接识别为半空间、仿射集合、范数球等标准凸集;若由多个约束共同定义,再判断这些凸集的交集。凸集的任意交集仍然是凸集,因此多个凸约束同时成立时通常不会破坏凸性。

如果集合存在孔洞、明显凹陷、互相分离的区域,优先尝试构造两点和其中点。只要找到一次越界,就已经足以证明非凸;反过来,仅仅画图观察或随机测试很多点都没有越界,并不能替代对任意点的数学证明。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用线段测试判断集合是否凸

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通