凸优化与约束优化

凸优化是最「美好」的优化问题——局部最优 = 全局最优。SVM、Lasso 回归、线性规划（LP）、二次规划（QP）都是凸优化问题。理解凸性是理解为什么有些模型「好优化」、有些「难训练」的关键。前置阅读：数值优化与数学基础。

核心直觉

凸函数 = 碗形（只有一个底）：想象一个完美的碗，不管你从碗的哪个位置开始滚，小球最终都会滑到同一个最低点——这就是凸优化的”美好”：不存在被局部最优困住的问题。
非凸函数 = 山脉（有很多坑）：神经网络的损失曲面就像连绵山脉，有无数小坑和鞍点，梯度下降只能碰运气找到一个”还可以”的坑。
约束优化 = 在围栏里找最低点：现实问题往往有限制（预算不能超、权重和为 1），你不能满山跑，只能在规定范围内找最优。
拉格朗日乘子法 =「在约束边界上找最优」：想象等高线地图和一条”围栏”（约束），最优解就在等高线与围栏相切的那个点——此时围栏的方向与等高线方向重合，再往任何方向走都会变差。

原理图解

凸函数 vs 非凸函数

凸函数的”碗形”保证了任意局部最优就是全局最优，这是凸优化”好优化”的根本原因：

凸函数的严格定义

光有”碗形”的直觉还不够，我们需要一个可以拿去证明的性质。凸函数的形式化定义是：

对于函数 $f: \mathbb{R}^n \to \mathbb{R}$ ，如果对定义域内任意两点 $x, y$ 和任意 $\theta \in [0,1]$ 都成立

$f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y)$

则 $f$ 是凸函数。

这个不等式翻译成人话就是：任意两点的连线，始终在函数曲面上方——这正是不等号左边（曲面上中点处的值）不超过右边（两个端点值的线性插值）。对可导函数而言，它等价于 $f$ 的二阶导数（Hessian 矩阵，即二阶偏导数组成的方阵 $\nabla^2 f$ ，描述函数在各方向上的曲率）半正定，也就是曲率处处非负，“只朝一个方向弯”。

从定义到 Hessian 半正定的推导

为什么”二阶导数半正定”能推出凸性？这里给出一个直观的推导链，帮助你建立”定义 ↔ 解析条件”之间的桥梁。

第一步：一维情形。 假设 $f: \mathbb{R} \to \mathbb{R}$ 二阶可导。对任意 $x, y$ ，由 Taylor 展开（在 $x$ 处展开到二阶）：

$f(y) = f(x) + f'(x)(y-x) + \frac{1}{2}f''(\xi)(y-x)^2, \quad \xi \in [x, y]$

如果 $f''(\xi) \ge 0$ 对所有 $\xi$ 成立，那么 $f(y) \ge f(x) + f'(x)(y-x)$ ——即函数始终在其切线上方，这正是凸函数的等价定义（“一阶切线条件”）。

第二步：多维情形。 令 $x, y \in \mathbb{R}^n$ ，定义一维函数 $\phi(t) = f(x + t(y-x))$ ，则 $\phi$ 是 $f$ 沿 $x \to y$ 方向的截面。由链式法则：

$\phi'(t) = \nabla f(x+t(y-x))^\top (y-x), \quad \phi''(t) = (y-x)^\top \nabla^2 f(x+t(y-x)) (y-x)$

如果 Hessian $\nabla^2 f \succeq 0$ （半正定，即对所有向量 $v$ 都有 $v^\top \nabla^2 f\, v \ge 0$ ），那么 $\phi''(t) \ge 0$ ，于是 $\phi$ 是一维凸函数，退回到第一步即得 $f$ 的凸性。这个”把多维问题降为一维截面”的技巧在凸分析中反复出现，值得记住。

更一般地，把任意两点推广到任意凸组合，就得到 Jensen 不等式（Jensen’s Inequality）：

$f\!\Big(\sum_i \theta_i x_i\Big) \le \sum_i \theta_i f(x_i), \quad \theta_i \ge 0,\ \sum_i \theta_i = 1$

Jensen 不等式是凸分析的核心工具：交叉熵损失（Cross-Entropy Loss，衡量预测概率分布与真实标签之间差异的损失函数）的凸性、EM 算法的下界推导、信息论里 $-\log$ 的凸性，都建立在它之上。

凸集是另一个基础概念：集合 $C$ 内任意两点连线仍在 $C$ 内。凸优化要求可行域（所有满足约束的点的集合）本身也是凸集——否则就算目标函数是碗形的，你能在碗底”合法到达”的范围也可能不连通。

凸优化问题的标准形式

一个标准的凸优化问题写成：

$\min_{x}\ f(x) \quad \text{s.t.}\quad g_i(x) \le 0,\ h_j(x) = 0$

其中 $f$ 和 $g_i$ 都是凸函数， $h_j$ 是仿射函数（即线性函数加常数，形如 $Ax-b$ ）。这三条”凸性约束”同时满足，才能保证：

局部最优 = 全局最优——不存在被次优解困住的风险。
最优解集是凸集——所有最优解连起来仍然合法。
KKT 条件成为充要条件（满足 Slater 条件时），即理论上可以”精确刻画”最优解。

这也是为什么 SVM、Lasso、LP、QP 这类问题被认为是”友好”的——它们有成熟的多项式时间求解算法（内点法，Interior Point Method），而且解是确定、可复现的。

拉格朗日乘子法与 KKT 条件

约束优化的最优解出现在”等高线与约束边界相切”的点，这就是拉格朗日乘子法的几何直觉：

KKT 条件是拉格朗日乘子法在不等式约束下的推广，是凸优化最优解的充要条件（满足 Slater 条件时）。它包含四条：梯度为零（稳定性）、满足原始约束（原始可行）、乘子非负（对偶可行）、约束与乘子的乘积为零（互补松弛）。SVM 的支持向量就来自互补松弛条件——只有支持向量对应的约束是”紧”的。

对偶理论与强对偶

理解 KKT 之后，自然引出对偶问题（Dual Problem）。对原始问题 $\min f(x)\ \text{s.t.}\ g_i(x)\le 0$ ，构造拉格朗日函数：

$\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j h_j(x)$

对偶函数定义为 $\mathcal{D}(\lambda, \nu) = \inf_x \mathcal{L}(x, \lambda, \nu)$ ，它始终是原始最优值的一个下界——这叫弱对偶。而凸优化最美妙的结论是：只要满足 Slater 条件（可行域内部非空，即存在严格满足不等式约束的点），下界恰好能达到，即强对偶成立，原问题最优值等于对偶问题最优值，对偶间隙为零。

为什么对偶问题往往更好解？以 SVM 为例：原问题是一个带不等式约束的 QP，约束个数等于样本数；转成对偶问题后约束退化为简单的盒约束（ $0 \le \alpha_i \le C$ ），并且决策变量之间的内积 $x_i^\top x_j$ 正好可以被核函数 $K(x_i, x_j)$ 替换——这就是核技巧得以引入的数学根源。详见 SVM 支持向量机。

动手实践

cvxpy 求解线性规划

import cvxpy as cp
import numpy as np

# 线性规划：工厂生产两种产品，最大化利润
# 产品 A 利润 3 元、耗原料 2 单位；产品 B 利润 5 元、耗原料 3 单位
# 原料总量 12 单位，求最优生产方案
x = cp.Variable(2)                                       # 两种产品的产量
objective = cp.Maximize(3 * x[0] + 5 * x[1])             # 最大化总利润
constraints = [2 * x[0] + 3 * x[1] <= 12,                # 原料约束
               x[0] >= 0, x[1] >= 0]                     # 非负约束
prob = cp.Problem(objective, constraints)
prob.solve()
print(f"最优产量: A={x.value[0]:.1f}, B={x.value[1]:.1f}, 最大利润={prob.value:.1f}")
# 最优产量: A=0.0, B=4.0, 最大利润=20.0

Lasso 回归的约束优化视角

Lasso（L1 正则化）的本质是一个带约束的最小二乘问题，L1 约束让解落在坐标轴上（产生稀疏解）：

import cvxpy as cp
import numpy as np

np.random.seed(42)
X = np.random.randn(50, 10)                # 10 个特征，但只有前 3 个有用
true_w = np.array([3, -2, 1, 0, 0, 0, 0, 0, 0, 0])   # 大量零 = 稀疏
y = X @ true_w + 0.1 * np.random.randn(50)

# Lasso = 最小二乘 + L1 范数约束（等价于 L1 正则化）
w = cp.Variable(10)
obj = cp.Minimize(cp.sum_squares(X @ w - y) + 0.5 * cp.norm1(w))
cp.Problem(obj).solve()
print("回归系数:", np.round(w.value, 2))   # 前 3 个非零，其余 ≈ 0（自动特征选择）
# 回归系数: [2.89 -1.96 0.97 0. 0. 0. 0. 0. 0. 0.]

实践要点

判断问题是否凸：凸优化好用的前提是目标函数和约束都是凸的。线性回归、SVM、Lasso 都是凸的；神经网络不是。用 cvxpy 时如果问题非凸，会报错或调用近似求解器。
对偶问题往往更容易求解：SVM 的原始问题是一个带不等式约束的 QP，转成对偶问题后只有简单的盒约束，且自然引入核函数——这是 SVM 理论精妙之处。详见SVM 支持向量机。
L1 正则化 → 稀疏解：Lasso 的 L1 约束让最优解落在坐标轴顶点上（大量系数恰好为零），天然实现了特征选择——这在高维数据（基因、文本）中极有价值。
商业求解器更快：大规模 LP/QP（百万变量级）推荐用 Gurobi / MOSEK / CPLEX 等商业求解器，比开源求解器快几个数量级。

典型应用

SVM 训练：SVM 的最大间隔优化是一个标准的凸二次规划（QP）问题，通过拉格朗日对偶求解，这也是核技巧得以引入的数学基础。详见SVM 支持向量机。
Lasso / L1 正则化：L1 约束产生稀疏解，自动做特征选择，在基因组学、稀疏信号恢复中广泛应用。
线性规划（LP）：物流配送路线优化、生产排程、金融资产配置、航空公司机组排班——运筹学的核心工具，百亿级经济效益。
压缩感知（Compressive Sensing）：用远少于 Nyquist 采样率的测量重建信号，数学基础就是 L1 最小化——核磁共振（MRI）加速成像就是典型应用。
模型预测控制（MPC）：自动驾驶轨迹规划和机器人控制中，每一步求解一个 QP 来决定最优控制输入——Tesla Autopilot、Boston Dynamics 机器人的底层控制都依赖实时凸优化。

典型类库与工具

类库	语言	说明
cvxpy	Python	凸优化建模语言，语法接近数学公式，后端可切换多种求解器
scipy.optimize.minimize	Python	通用约束优化（SLSQP / trust-constr），适合中小规模非凸问题
CVXOPT	Python	凸优化求解器库，提供 LP / QP / SOCP / SDP 求解
Gurobi	C++/Python	商业 LP / QP / MILP 求解器，工业界标杆，学术免费
Google OR-Tools	C++/Python	Google 开源运筹优化工具包，专注于路由、排程、装箱等组合优化

术语表

术语	英文	解释
凸函数	Convex Function	任意两点的连线在函数图像之上的函数，只有一个全局最小值
凸集	Convex Set	集合内任意两点连线仍在集合内的区域，是凸优化的可行域
拉格朗日乘子	Lagrange Multiplier	将约束融入目标函数的对偶变量，几何上反映约束的”影子价格”
KKT 条件	KKT Conditions	带不等式约束的优化问题取得最优解的必要（凸问题下充分）条件
原问题 / 对偶问题	Primal / Dual	同一优化问题的两种等价表述，对偶问题常更易求解且提供下界
线性规划	LP	目标和约束都是线性的凸优化问题，运筹学核心
二次规划	QP	目标是二次函数、约束为线性的凸优化，SVM 训练的标准形式
半定规划	SDP	变量为半正定矩阵的凸优化，是 LP / SOCP 的推广，理论意义重大
对偶间隙	Duality Gap	原问题最优值与对偶问题最优值之差，为零时强对偶成立