凸集

集合 $C\subseteq {ℝ}^n$ 是凸集，指任取 $x,y\in C$ 与 $0\le t\le 1$，线段上的点 $(1-t)x+ty$ 仍属于 $C$。圆盘、矩形、半空间都是凸集；月牙形区域通常不是，因为连接两点的线段可能穿出区域。

一条线段检验定义

区间 $[1,3]$ 是一维凸集，因为两数 $x,y\in [1,3]$ 的加权平均仍介于 1 和 3。集合 $[1,2]\cup [3,4]$ 则不是：取 $x=2$、$y=3$，中点 2.5 不在集合里。反例只需找到一组两点与一个 $t$；证明凸性则必须覆盖所有两点和所有 $t$。

若 $C_1,C_2,\dots$ 都凸，其交集仍凸：两点若属于交集，就分别属于每个 $C_i$，线段也属于每个 $C_i$，所以仍在交集中。并集却未必凸，上述两个分开的区间便是反例。

线性约束形成凸集

半空间 $H=\{x:a^{𝖳}x\le b\}$ 是凸的，因为对可行点 $x,y$， $$a^{𝖳}((1-t)x+ty)=(1-t)a^{𝖳}x+t{a}^{𝖳}y\le b.$$ 多个线性不等式的可行域是半空间的交，因此也是凸集。这是线性规划容易建立全局最优理论的几何原因之一；但仅有可行域凸，不保证任意目标函数都容易优化，仍要看凸函数条件。

参考资料

• Boyd 与 Vandenberghe，Convex Optimization，第 2 章。
• MIT 6.079，凸优化讲义。
• 继续阅读：凸函数、线性规划、拉格朗日对偶。