凸优化

凸优化 (Convex Optimization)

凸优化是数学优化中一类特殊问题，核心优势：任何局部最优解同时也是全局最优解。相比于一般非凸优化（通常是NP-hard的），凸优化在理论上易于求解，存在高效可靠算法。

凸集与凸函数

凸集：对于集合 $C$ 中任意两点 $x_1, x_2 \in C$ 和任意 $0 \le \theta \le 1$，有 $\theta x_1 + (1-\theta)x_2 \in C$。凸集是“饱满”的，无凹陷或洞（如圆盘、实心正方形）。

凸函数（琴生不等式）：$f(\theta x_1 + (1-\theta)x_2) \le \theta f(x_1) + (1-\theta)f(x_2)$。图像呈“碗”形（如 $f(x)=x^2$）。可微函数的判据：一维 $f''(x) \ge 0$；多维 Hessian矩阵 $\nabla^2 f(x)$ 半正定。

凸优化问题的标准形式

凸优化条件：$f_0(x)$ 凸、$f_i(x)$ 凸、$h_j(x)$ 为仿射函数（$a^T x + b$）。凸函数的水平集是凸集，仿射函数定义的超平面也是凸集。任意多个凸集的交集仍是凸集——整个可行集是凸的。

核心定理：局部最优 = 全局最优

反证法证明：假设 $x^*$ 局部最优但非全局最优，则存在 $y$ 使 $f_0(y) < f_0(x^*)$。构造 $z = \theta y + (1-\theta)x^*$（$\theta$ 小正数）。由凸性得 $f_0(z) \le \theta f_0(y) + (1-\theta)f_0(x^*) < f_0(x^*)$。当 $\theta$ 很小时 $z$ 任意接近 $x^*$，与 $x^*$ 是局部最优矛盾。因此局部最优必为全局最优。

常见实例

• 线性规划 (LP)：目标函数和约束全为线性，凸优化最简单子类
• 二次规划 (QP)：目标二次、约束线性。如马科维茨投资组合优化——给定收益下最小化方差
• 支持向量机 (SVM)：寻找最大间隔超平面，可构建为凸二次规划

重要性

1. 理论可解性：“局部即全局”提供坚实理论保证
2. 计算高效性：内点法可在多项式时间求解，现代求解器（CVXPY, Gurobi, MOSEK）可处理数百万变量的大规模问题
3. 对偶理论：原问题和对偶问题在温和条件下最优值相等（强对偶性），对偶变量可解释为“影子价格”，为算法设计和最优性检验提供强大工具