AI 与工程数学 / 系统课时
用线段测试判断集合是否凸
用线段测试判断集合是否凸
判断一个约束集合是否为凸集,核心不在于它看起来是否“圆润”,而是任取集合中的两点后,它们之间整条线段是否仍留在集合内。本节用这条定义快速识别半空间、球和仿射集合,并用孔洞与分离区域构造反例。
学习目标
- 用线段测试准确写出凸集的判定条件
- 判断半空间、欧氏球和仿射集合为什么是凸集
- 通过一个反例证明含孔洞或分离区域的集合不是凸集
线段测试的数学定义
设集合 。如果对任意 和任意 ,都有
那么 就是凸集。
式子 描述从 移动到 的整条线段: 时得到 , 时得到 ,中间值则对应两点之间的位置。因此,凸集的本质就是集合中任意两点之间不存在“越界”的线段部分。

证明一个集合是凸集时,需要说明所有点对和所有 都满足条件;证明它不是凸集则简单得多,只需要找到一组 、 和一个 ,使组合点落到集合外即可。
常见凸集为什么通过测试
半空间可以写成
若 ,则 、。于是对 ,
所以组合点仍在半空间中。
欧氏球
同样是凸集。由三角不等式可得
仿射集合 也满足线段测试,因为 时,
这些结论在优化建模中很实用:线性等式、线性不等式和范数球约束组合起来,往往仍能形成凸可行域。
用一个反例否定凸性
考虑二维圆环
取 和 。两点都位于圆环中,但令 ,其中点为 ,其范数为 ,落入圆环中央的孔洞,因此圆环不是凸集。
下面的程序直接验证这个反例。它只能帮助寻找或确认反例,有限次采样本身不能证明一个集合对所有点都凸。
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))预期输出:
True
True
[0. 0.]
False同样地,如果一个集合由两块互不相连的区域组成,通常也能分别在两块区域中各取一点,使连接线段经过集合外部,从而立即得到非凸性反例。
判断约束集合时的实用顺序
面对一个新的可行域,可以先看它是否能直接识别为半空间、仿射集合、范数球等标准凸集;若由多个约束共同定义,再判断这些凸集的交集。凸集的任意交集仍然是凸集,因此多个凸约束同时成立时通常不会破坏凸性。
如果集合存在孔洞、明显凹陷、互相分离的区域,优先尝试构造两点和其中点。只要找到一次越界,就已经足以证明非凸;反过来,仅仅画图观察或随机测试很多点都没有越界,并不能替代对任意点的数学证明。