凸集、凸函数与凸优化
“优化的圣杯不是线性与非线性，而是凸与非凸”。 探索凸组合几何直观、支撑超平面一阶充要条件、局优即全优黄金定理与实战谱系！
凸集与凸组合动态实验台
在画布上点击任意处添加顶点或拖拽顶点。系统实时计算并渲染点集的凸包 (Convex Hull)，并利用滑块检验两点线段插值 $\alpha x_1 + (1-\alpha)x_2$ 是否始终保留在集合内。
设 $\Omega \subseteq \mathbb{R}^n$，对于所有的 $x_1, x_2 \in \Omega$ 及 $\alpha \in [0, 1]$，都有： $$\alpha x_1 + (1-\alpha)x_2 \in \Omega$$ 则称 $\Omega$ 为凸集。几何意义：集合内任意两点的连线段均完全包含在集合内部。
设 $a = [a_1, a_2, a_3]^\top, b = [b_1, b_2, b_3]^\top \in \Omega$，满足： $$a_1 + 2a_2 - a_3 = 4, \quad b_1 + 2b_2 - b_3 = 4$$
$\forall \alpha \in [0, 1]$，设 $c = \alpha a + (1-\alpha)b$。即： $$c_i = \alpha a_i + (1-\alpha)b_i, \quad i=1, 2, 3$$
将 $c$ 代入平面的左端方程： $$\begin{aligned} c_1 + 2c_2 - c_3 &= (\alpha a_1 + (1-\alpha)b_1) + 2(\alpha a_2 + (1-\alpha)b_2) - (\alpha a_3 + (1-\alpha)b_3) \\ &= \alpha (a_1 + 2a_2 - a_3) + (1-\alpha)(b_1 + 2b_2 - b_3) \\ &= \alpha \cdot 4 + (1-\alpha) \cdot 4 = 4 \end{aligned}$$ 因此 $c \in \Omega$，由定义知 $\Omega$ 必为凸集。证毕！
六大重要凸集交互探针
在最优化算法中，这六大几何体构成了所有可行域与约束锥的基石。点击切换探针，实时观察法向量旋转、半正定矩阵二次型曲面与锥体切片。
超平面 (Hyperplane)：
$$\{x \in \mathbb{R}^n \mid a^\top x = b\} \quad (a \neq 0)$$闭半空间 (Halfspace)：
$$\{x \in \mathbb{R}^n \mid a^\top x \le b\}$$- 法向量 $a$：正交于超平面本身，指示半空间的指向方向。
- 截距 $b$ 与原点距离：原点到超平面的有向欧氏几何距离为 $d = \frac{b}{\|a\|_2}$。
- 凸性证明：设 $x_1, x_2$ 满足 $a^\top x_i \le b$。则 $\forall \alpha \in [0, 1]$： $$a^\top (\alpha x_1 + (1-\alpha)x_2) = \alpha a^\top x_1 + (1-\alpha)a^\top x_2 \le \alpha b + (1-\alpha)b = b$$ 因此半空间恒为凸集。
对称正定矩阵 $P = P^\top \succ 0$，其谱分解为：
$$P = R(\theta) \begin{bmatrix} r_1^2 & 0 \\ 0 & r_2^2 \end{bmatrix} R(\theta)^\top$$特征值分别为 $\lambda_1 = r_1^2, \lambda_2 = r_2^2$。主轴方向由正交阵 $R(\theta)$ 的特征向量决定。
令 $P = A A^\top$（Cholesky分解），则椭球可以看作是单位欧氏球 $B(0, 1) = \{u \mid \|u\|_2 \le 1\}$ 经过仿射变换后的像： $$\mathcal{E} = \{x_c + A u \mid \|u\|_2 \le 1\}$$ 因为欧氏球是凸集，而仿射变换保凸，所以椭球必然是凸集！
- 有限半空间交集：$Ax \le b$ 对应 $m$ 个半空间 $a_i^\top x \le b_i$ 的交集。
- 多胞形 (Polytope)：有界的多面体称为多胞形。
- 保凸性：由于每个超平面 $c_j^\top x = d_j$ 和每个半空间 $a_i^\top x \le b_i$ 都是凸集，根据“任意多个凸集的交集仍为凸集”，多面体恒为凸集。
- 线性规划的可行域：标准型 LP 的可行域 $\{x \mid Ax = b, x \ge 0\}$ 正是一个多面体！
由 Minkowski 不等式，当 $p \ge 1$ 时满足三角不等式 $\|x+y\|_p \le \|x\|_p + \|y\|_p$，因此所有的范数函数均为凸函数，范数球是凸集。
例如 $p=0.5$ 时，图像向内凹陷（类似星形十字），违背连线段在集合内的条件，三角不等式失效。这解释了为什么机器学习中做稀疏特征选择时，优先选择最小的凸松弛——$\ell_1$ 范数（LASSO），而非直接求解 NP-hard 的非凸 $\ell_0$ 或 $\ell_{0.5}$！
考虑所有 $2 \times 2$ 对称矩阵：
$$X = \begin{bmatrix} x & y \\ y & z \end{bmatrix} \in \mathbb{S}^2$$$X \succeq 0$（半正定）的充要条件为各阶顺序主子式均非负：
$$x \ge 0, \quad z \ge 0, \quad \det(X) = xz - y^2 \ge 0 \iff y^2 \le xz$$
令 $u = x+z \ge 0$，$v = x-z$。则 $xz = \frac{u^2 - v^2}{4}$。
不等式 $xz \ge y^2$ 可重写为：
$$\left(\frac{u}{2}\right)^2 \ge \left(\frac{v}{2}\right)^2 + y^2$$
在坐标系 $(u, v, y)$ 中，这正是标准的二阶旋转圆锥 (Lorentz Cone)！顶点在原点 $(0, 0, 0)$，沿 $u$ 轴正向开口。
保凸运算解析
判断一个复杂集合是否为凸集，绝大多数情况下无需从头验证定义，而是借助三大保凸运算法则。
若集合族 $\{S_i\}_{i \in I}$ 中每一个 $S_i$ 均为凸集，则它们的交集 $\bigcap_{i \in I} S_i$ 必定为凸集（无论是有穷交还是无穷交）。
设 $f(x) = Ax + b$ 为仿射映射。若 $S \subseteq \mathbb{R}^n$ 为凸集，则其像集： $$f(S) = \{Ax + b \mid x \in S\}$$ 也是凸集。缩放、平移、旋转、正交投影均是仿射变换，因而均保凸。
若 $C \subseteq \mathbb{R}^m$ 为凸集，则其在仿射映射下的原像集： $$f^{-1}(C) = \{x \in \mathbb{R}^n \mid Ax + b \in C\}$$ 必定为凸集。多面体 $Ax \le b$ 本质上就是非正象限 $\mathbb{R}^m_-$ 的仿射逆像！
两个凸集的并集 $S_1 \ cup S_2$ 通常不是凸集（如两个分离的球，两点各取一个，中点直接掉入真空区域）。
凸函数判定条件动态图解
从 0 阶 Jensen 不等式割线，到 1 阶支撑超平面（一阶充要条件），再到 2 阶黑塞矩阵半正定性。
凸函数定义 (Jensen Inequality)：
$$f(\alpha x_1 + (1-\alpha)x_2) \le \alpha f(x_1) + (1-\alpha)f(x_2), \quad \forall \alpha \in [0, 1]$$几何意义：连接 $(x_1, f(x_1))$ 与 $(x_2, f(x_2))$ 的割线段（弦）永远位于函数曲线的上方！
一阶充要条件定理：设 $f: D \to \mathbb{R}$ 可微，$D$ 为凸集。$f$ 为凸函数充要条件为：
$$f(y) \ge f(x) + \nabla f(x)^\top (y - x), \quad \forall x, y \in D$$几何直观：$f(x) + \nabla f(x)^\top (y-x)$ 是函数在 $x$ 处的仿射一阶逼近（切超平面），在全空间中处处构成函数全局下界！
由定义 $f(\alpha y + (1-\alpha)x) \le \alpha f(y) + (1-\alpha)f(x)$。
移项得：$f(y) - f(x) \ge \frac{f(x + \alpha(y-x)) - f(x)}{\alpha}$。
由一阶泰勒展开，右侧分子为 $\alpha \nabla f(x)^\top (y-x) + o(\alpha)$。
两边令 $\alpha \to 0^+$ 取极限，即得：
$$f(y) - f(x) \ge \nabla f(x)^\top (y-x) \implies f(y) \ge f(x) + \nabla f(x)^\top (y-x)$$
任取 $x, y \in D, \alpha \in (0, 1)$，令 $z = \alpha x + (1-\alpha)y \in D$。
在点 $z$ 处分别对 $x$ 和 $y$ 应用条件：
$f(x) \ge f(z) + \nabla f(z)^\top (x - z) \quad (1)$
$f(y) \ge f(z) + \nabla f(z)^\top (y - z) \quad (2)$
计算 $\alpha \times (1) + (1-\alpha) \times (2)$：
$\alpha f(x) + (1-\alpha)f(y) \ge f(z) + \nabla f(z)^\top [\alpha(x-z) + (1-\alpha)(y-z)] = f(z) + 0$。
即 $\alpha f(x) + (1-\alpha)f(y) \ge f(\alpha x + (1-\alpha)y)$，充分性得证！
二阶充要条件定理：连续二阶可微函数 $f$ 在凸集 $D$ 上为凸函数 $\iff \nabla^2 f(x) \succeq 0$ 对所有 $x \in D$ 成立。
$$\begin{aligned} f(x) &= \frac{1}{2}(Ax - b)^\top (Ax - b) \\ &= \frac{1}{2} x^\top A^\top A x - b^\top A x + \frac{1}{2} b^\top b \end{aligned}$$
一阶梯度：$\nabla f(x) = A^\top A x - A^\top b = A^\top(Ax - b)$
二阶导数：$\nabla^2 f(x) = A^\top A$
对任意非零向量 $v \in \mathbb{R}^n$，考察二次型： $$v^\top (\nabla^2 f(x)) v = v^\top (A^\top A) v = (Av)^\top (Av) = \|Av\|_2^2 \ge 0$$ 由于对任意向量 $v$，该值非负，故矩阵 $A^\top A$ 是半正定矩阵（即 $A^\top A \succeq 0$）。因此最小二乘目标函数恒为凸函数！
凸优化核心黄金性质：局部最优即全局最优
为什么工程师与科学家如此偏好建立凸优化模型？正是因为这一无与伦比的黄金定理！
设优化问题 $\min_{x \in \Omega} f(x)$ 为凸优化问题（即可行域 $\Omega$ 为凸集，$f$ 为定义在 $\Omega$ 上的凸函数）。
定理：该问题的任何局部最优解，必定也是全局最优解！
设 $x^{(1)} \in \Omega$ 是局部最优解。由定义，存在邻域半径 $\delta > 0$，使得： $$\forall x \in \Omega \cap B(x^{(1)}, \delta), \quad f(x^{(1)}) \le f(x)$$
假设 $x^{(1)}$ 不是全局最优解。那么在可行域 $\Omega$ 内必定存在另一点 $x^{(2)} \in \Omega$，满足： $$f(x^{(2)}) < f(x^{(1)})$$
$\forall \alpha \in (0, 1)$，构造连线点 $x_\alpha = \alpha x^{(1)} + (1-\alpha) x^{(2)}$。
由于可行域 $\Omega$ 是凸集，故连线点 $x_\alpha \in \Omega$。
由于 $f$ 是凸函数，满足 Jensen 不等式： $$\begin{aligned} f(x_\alpha) &\le \alpha f(x^{(1)}) + (1-\alpha) f(x^{(2)}) \\ &< \alpha f(x^{(1)}) + (1-\alpha) f(x^{(1)}) = f(x^{(1)}) \end{aligned}$$ 即：在整条连线段上，所有中间点的函数值均严格小于 $f(x^{(1)})$！
当 $\alpha \to 1^-$ 时，$x_\alpha$ 与 $x^{(1)}$ 的距离：
$$\|x_\alpha - x^{(1)}\| = (1-\alpha)\|x^{(2)} - x^{(1)}\| < \delta$$
即只要取 $\alpha > 1 - \frac{\delta}{\|x^{(2)} - x^{(1)}\|}$，点 $x_\alpha$ 便进入局部最优邻域 $B(x^{(1)}, \delta)$，且其函数值 $f(x_\alpha) < f(x^{(1)})$。
这与 $x^{(1)}$ 是局部最优解产生不可调和的矛盾！故假设不成立，局部最优必是全局最优。证毕！
右侧非凸多峰：粒子被困在各自局部的凹坑中，陷入假最优（局部极小）！
四大常见凸优化问题谱系与几何约束锥
线性规划 (LP) $\subset$ 二次规划 (QP) $\subset$ 二阶锥规划 (SOCP) $\subset$ 半定规划 (SDP) $\subset$ 广义凸规划。
| 问题类别 | 标准目标函数 | 约束条件特征 | 几何对偶锥 (Cone) | 经典工业与算法应用 |
|---|---|---|---|---|
| 线性规划 (LP) | $c^\top x$ (线性) | $Ax \le b, \ Cx = d$ (仿射超平面与半空间) | 非负象限锥 $\mathbb{R}^n_+$ | 资源分配、运筹学网络流、单纯形法 |
| 二次规划 (QP) | $\frac{1}{2} x^\top Q x + c^\top x \ (Q \succeq 0)$ | $Ax \le b, \ Cx = d$ (线性不等式/等式) | 多面体锥 (Polyhedral) | 支持向量机 (SVM)、马科维茨资产组合配置 |
| 二阶锥规划 (SOCP) | $c^\top x$ (线性) | $\|A_i x + b_i\|_2 \le c_i^\top x + d_i$ (二阶锥) | 洛伦兹二阶锥 / 冰淇淋锥 $\mathcal{Q}^{n+1}$ | 鲁棒线性规划、天线阵列波束赋形、空间飞行器软着陆 |
| 半定规划 (SDP) | $c^\top x$ (线性) | $F_0 + \sum_{j=1}^n x_j F_j \succeq 0$ (LMI 线性矩阵不等式) | 半正定对称锥 $\mathbb{S}^m_+$ | MAX-CUT 图割近似算法、现代控制理论 LMI |
每一个低维问题均是高维广义锥规划的特例！例如将半定规划的约束矩阵约束在对角线上，SDP 立即精确退化为 LP； 在计算复杂度方面，内点法（Interior Point Methods）能在多项式时间内统一求解上述全部四种锥规划。
作业速攻实战助手 (Homework 1 Solutions)
针对《最优化算法》第一次作业中涉及本章的全部核心题目（第 5, 6, 7, 8 题），提供交互式数值/几何探针与一键推导展开。
设 $\Omega \subset \mathbb{R}^n$ 为凸集，函数 $f_i: \Omega \to \mathbb{R} \ (i = 1, \dots, \ell)$ 是凸函数。证明 $g(x) = \max\{f_1(x), \dots, f_\ell(x)\}$ 是凸函数。
任取 $x_1, x_2 \in \Omega$ 及 $\alpha \in [0, 1]$。由于 $\Omega$ 是凸集，凸组合点 $x_\alpha = \alpha x_1 + (1-\alpha)x_2 \in \Omega$。
对任意指标 $i \in \{1, \dots, \ell\}$，由 $f_i$ 的凸性有： $$f_i(\alpha x_1 + (1-\alpha)x_2) \le \alpha f_i(x_1) + (1-\alpha)f_i(x_2)$$
由于对所有 $i$，均有 $f_i(x_1) \le g(x_1)$ 以及 $f_i(x_2) \le g(x_2)$，且 $\alpha \ge 0, 1-\alpha \ge 0$： $$\alpha f_i(x_1) + (1-\alpha)f_i(x_2) \le \alpha g(x_1) + (1-\alpha)g(x_2)$$ 从而对每个 $i = 1, \dots, \ell$，均有： $$f_i(\alpha x_1 + (1-\alpha)x_2) \le \alpha g(x_1) + (1-\alpha)g(x_2)$$
由于上式右端与指标 $i$ 完全无关，因此左侧对所有 $i$ 取最大值，不等式依然成立： $$g(\alpha x_1 + (1-\alpha)x_2) = \max_{1 \le i \le \ell} f_i(\alpha x_1 + (1-\alpha)x_2) \le \alpha g(x_1) + (1-\alpha)g(x_2)$$ 由凸函数定义，函数 $g(x)$ 必为凸函数。证毕！
考虑优化问题： $$\min \ \frac{1}{2}\|Ax - b\|^2 \quad \text{s.t.} \quad \sum_{i=1}^n x_i = 1, \quad x_i \ge 0 \ (i=1,\dots,n)$$ 这是一个凸规划吗？如果是，给出详细证明；如果不是，给出理由。
设 $f(x) = \frac{1}{2}\|Ax - b\|^2$。
其二阶黑塞矩阵为 $\nabla^2 f(x) = A^\top A$。
对任意向量 $v \in \mathbb{R}^n$：
$$v^\top (A^\top A) v = (Av)^\top (Av) = \|Av\|_2^2 \ge 0$$
因此 $\nabla^2 f(x) \succeq 0$（半正定）。由二阶充分条件，目标函数在 $\mathbb{R}^n$ 上是凸函数。
可行集 $\Omega = \{x \in \mathbb{R}^n \mid \mathbf{1}^\top x = 1, \ -x_i \le 0 \ (i=1,\dots,n)\}$。
它是 1 个超平面 $\{\mathbf{1}^\top x = 1\}$ 与 $n$ 个闭半空间 $\{-x_i \le 0\}$ 的交集。
因为超平面和半空间均为凸集，且凸集的任意交集保持凸性，所以可行集 $\Omega$ 是凸集。
证明：若 $f: \mathbb{R}^n \to \mathbb{R}$ 是凸函数，则对任意实数 $c$，其下水平集 $S_c = \{x \in \mathbb{R}^n \mid f(x) \le c\}$ 是凸集。
1. 若 $S_c = \emptyset$，空集根据定义自然是凸集。
2. 若 $S_c \neq \emptyset$，任取 $x_1, x_2 \in S_c$ 及 $\alpha \in [0, 1]$。
根据集合定义，有：
$$f(x_1) \le c \quad \text{且} \quad f(x_2) \le c$$
3. 考虑连线点 $x_\alpha = \alpha x_1 + (1-\alpha)x_2$。由 $f$ 为凸函数及 $\alpha \in [0, 1]$：
$$f(x_\alpha) \le \alpha f(x_1) + (1-\alpha) f(x_2)$$
4. 将 $f(x_1) \le c, f(x_2) \le c$ 代入，注意到 $\alpha \ge 0, 1-\alpha \ge 0$：
$$f(x_\alpha) \le \alpha c + (1-\alpha) c = (\alpha + 1 - \alpha) c = c$$
5. 这表明 $f(x_\alpha) \le c$，即连线点 $x_\alpha \in S_c$。
由定义可知，下水平集 $S_c$ 必为凸集。证毕！
设 $A, B \in \mathbb{R}^{n \times n}$ 对称且 $A \succeq 0, B \succeq 0$。$\forall \alpha \in (0, 1)$：
对称性显然保持。对任意非零向量 $z \in \mathbb{R}^n$：
$$z^\top (\alpha A + (1-\alpha)B) z = \alpha (z^\top A z) + (1-\alpha)(z^\top B z)$$
因为 $z^\top A z \ge 0, z^\top B z \ge 0$，且 $\alpha > 0, 1-\alpha > 0$，故该二次型和恒 $\ge 0$。
由定义 $\alpha A + (1-\alpha)B \succeq 0$，故半正定锥是凸锥（凸集）。
目标函数 $c^\top x$ 是线性函数，为凸函数。
约束映射 $F(x) = F_0 + \sum_{j=1}^n x_j F_j$ 是仿射映射。
可行域为半正定锥在仿射映射下的原像 $\mathcal{K} = \{x \mid F(x) \in \mathbb{S}^m_+\}$。
由于半正定锥是凸集，且仿射逆像保凸，因此可行域 $\mathcal{K}$ 必为凸集。该问题为严格凸优化！
输入 LP 约束 $Ax \ge b$ 中的参数，实时生成对应的 SDP 对角分块矩阵 $F_0, F_1, F_2$：