凸优化深度指南

文档概述

凸优化是现代机器学习与统计推断的理论支柱。本指南系统介绍凸集与凸函数的基本理论、典型优化问题（LP、QP）、对偶理论与KKT条件、梯度下降法及其收敛性分析，以及各类一阶二阶优化方法。

关键词

序号	关键词	英文	核心概念
1	凸集	Convex Set	$\forall x,y\in C,\theta \in [0,1]:\theta x+(1-\theta )y\in C$
2	凸函数	Convex Function	$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$
3	线性规划	Linear Programming	$\min c^{T}x\text{ s.t. }Ax\le b$
4	二次规划	Quadratic Programming	$\min \frac{1}{2}{x}^{T}Qx+c^{T}x\text{ s.t. }Ax\le b$
5	KKT条件	Karush-Kuhn-Tucker	最优性的必要条件
6	对偶问题	Dual Problem	原问题的下界优化
7	梯度下降	Gradient Descent	$x_{k+1}=x_k-\eta \nabla f(x_k)$
8	收敛率	Convergence Rate	$O(1/k),O(1/k^2),\exp (-k)$
9	Lipschitz连续	Lipschitz Continuity	$\Vert f(x)-f(y)\Vert \le L\Vert x-y\Vert$
10	强凸	Strong Convexity	$f(x)-\frac{\mu }{2}\Vert x{\Vert }^2$ 凸
11	Frank-Wolfe	Frank-Wolfe Algorithm	线性约束优化的投影自由方法
12	拉格朗日	Lagrangian	$L(x,\lambda ,\nu )=f_0(x)+\sum {\lambda }_i{f}_i(x)+\sum {\nu }_j{h}_j(x)$

---

一、凸集与凸函数

1.1 凸集的定义与性质

凸集：集合 $C\subseteq {\mathbb{R}}^n$ 是凸的，当且仅当对任意 $x,y\in C$ 和 $\theta \in [0,1]$，有：

$\theta x+(1-\theta )y\in C$

几何直观：凸集内任意两点的线段完全包含在集合内。

常见的凸集：

• 超平面：$\{x:a^{T}x=b\}$
• 半空间：$\{x:a^{T}x\le b\}$
• 多面体：有限个半空间和超平面的交集
• 范数球：$\{x:\Vert x\Vert \le 1\}$（任意范数）
• 仿射集：$\{x:Ax=b\}$
• 正象限：${\mathbb{R}}_{+}^n$

凸集的运算保凸性：

• 交集：凸集的交集仍是凸集
• 和：如果 $C_1,C_2$ 凸，则 $C_1+C_2=\{x+y:x\in C_1,y\in C_2\}$ 凸
• 仿射变换：$f(C)=\{f(x):x\in C\}$ 保持凸性
• 透视变换：保持凸性

凸集示例

1. 单位球 $B=\{x:\Vert x{\Vert }_2\le 1\}$ 是凸的
2. 三角形的内部是凸的
3. 圆盘（平面内）是凸的
4. 环形区域 $\{x:1\le \Vert x\Vert \le 2\}$ 不是凸的（因为不包含原点到边界点的线段）

1.2 凸函数的定义

凸函数：函数 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 是凸的，当且仅当 $\text{dom}(f)$ 是凸集，且对任意 $x,y\in \text{dom}(f)$ 和 $\theta \in [0,1]$：

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

几何意义：函数图像上任意弦线位于函数图像上方。

严格凸：若上述不等式在 $x\ne y$ 和 $\theta \in (0,1)$ 时严格成立。

凹函数：$-f$ 是凸的。

Jensen不等式：凸函数的离散形式：对任意 $x_1,\dots ,x_k$ 和 ${\theta }_i\ge 0$，$\sum {\theta }_i=1$：

$f\left({\sum }_i{\theta }_i{x}_i\right)\le {\sum }_i{\theta }_{i}f(x_i)$

1.3 凸函数的判别与性质

一阶条件：若 $f$ 可微，则 $f$ 凸当且仅当

$f(y)\ge f(x)+\nabla f(x{)}^T(y-x),\forall x,y$

即函数位于任一点切平面的上方（支持超平面性质）。

二阶条件：若 $f$ 二阶可微，则 $f$ 凸当且仅当其Hessian矩阵半正定：

${\nabla }^{2}f(x)⪰0,\forall x\in \text{dom}(f)$

常见的凸函数：

• 指数函数 $e^{ax}$
• 负对数 $-\log x$（在 $x>0$）
• 范数 $\Vert x{\Vert }_p$（任意 $p\ge 1$）
• 二次函数 $\frac{1}{2}{x}^{T}Qx+b^{T}x+c$（$Q⪰0$）
• 最大函数 $\max (x_1,\dots ,x_n)$
• 指数和函数 $\log {\sum }_i{e}^{x_i}$（log-sum-exp）

凸函数的重要性

凸优化问题的局部最优解即全局最优解。这一性质使得凸问题在理论上”容易”求解——只需找到局部最优即可。

---

二、典型优化问题

2.1 线性规划（LP）

线性规划的标准形式：

${\min }_x{c}^{T}x$ $\text{s.t.}Ax=b$ $x\ge 0$

或不等式形式：

${\min }_x{c}^{T}x$ $\text{s.t.}Ax\le b$

线性规划的几何：目标函数定义一族平行超平面。约束定义一个多面体（凸集）。最优解出现在多面体的顶点。

单纯形法：通过在顶点间移动来寻找最优解，最坏情况指数时间，但实际中通常很快。

内点法：通过障碍函数在多面体内部移动，多项式时间复杂度。

diet problem（饮食问题）

最小化成本选择食物满足营养需求： $\min {\sum }_j{c}_j{x}_j\text{s.t.}{\sum }_j{a}_{ij}{x}_j\ge b_i,x_j\ge 0$ 其中 $x_j$ 是食物 $j$ 的量，$c_j$ 是单价，$a_{ij}$ 是营养 $i$ 的含量，$b_i$ 是每日需求。

2.2 二次规划（QP）

二次规划：

${\min }_x\frac{1}{2}{x}^{T}Qx+c^{T}x$ $\text{s.t.}Ax\le b$

当 $Q⪰0$（半正定）时，问题为凸二次规划，全局最优可达。

等效于：最小二乘的正则化形式

${\min }_x\Vert Ax-b{\Vert }^2+\lambda \Vert x{\Vert }^2$

KKT条件简化（无不等式约束时）：

$\nabla f(x)=Qx+c=0\Rightarrow x^{\ast }=-Q^{-1}c$

2.3 二次约束二次规划（QCQP）

QCQP：

${\min }_x\frac{1}{2}{x}^T{Q}_{0}x+c_0^{T}x$ $\text{s.t.}\frac{1}{2}{x}^T{Q}_{i}x+c_i^{T}x+r_i\le 0,i=1,\dots ,m$

当所有 $Q_i⪰0$ 时，QCQP是凸问题。

二阶锥规划（SOCP） 是QCQP的推广：

${\min }_x{f}^{T}x$ $\text{s.t.}\Vert A_{i}x+b_i{\Vert }_2\le c_i^{T}x+d_i$

SOCP包含LP、QP和QCQP作为特例，在信号处理和鲁棒优化中广泛应用。

---

三、对偶理论与KKT条件

3.1 拉格朗日函数

考虑标准优化问题（原问题）：

${\min }_x{f}_0(x)$ $\text{s.t.}{f}_i(x)\le 0,i=1,\dots ,m$ $h_j(x)=0,j=1,\dots ,p$

拉格朗日函数：

$L(x,\lambda ,\nu )=f_0(x)+{\sum }_{i=1}^m{\lambda }_i{f}_i(x)+{\sum }_{j=1}^p{\nu }_j{h}_j(x)$

其中 ${\lambda }_i\ge 0$（不等式约束的乘子），${\nu }_j$（等式约束的乘子）。

3.2 拉格朗日对偶函数

对偶函数定义为拉格朗日函数关于 $x$ 的下确界：

$g(\lambda ,\nu )={\inf }_{x\in \mathcal{D}}L(x,\lambda ,\nu )$

其中 $\mathcal{D}={\bigcap }_i\text{dom}(f_i)\cap {\bigcap }_j\text{dom}(h_j)$。

对偶函数的性质（弱对偶性）：

$g(\lambda ,\nu )\le p^{\ast },\forall \lambda \ge 0,\forall \nu$

即对偶函数给出原问题最优值 $p^{\ast }$ 的下界。

3.3 对偶问题

对偶问题（拉格朗日对偶）：

${\max }_{\lambda ,\nu }g(\lambda ,\nu )$ $\text{s.t.}\lambda \ge 0$

对偶问题的最优值记为 $d^{\ast }$，恒有 $d^{\ast }\le p^{\ast }$（弱对偶性）。

强对偶性：在某些条件下，$d^{\ast }=p^{\ast }$。这些条件包括：

• Slater条件：存在严格可行的 $x$（对于凸问题），即 $\exists x$ 使得 $f_i(x)<0$（而非 $\le 0$）且 $Ax=b$。
• 约束规范：如线性约束独立、KKT条件满足等。

3.4 KKT条件

对于最优解 $x^{\ast }$ 和对偶变量 ${\lambda }^{\ast },{\nu }^{\ast }$，KKT条件为：

1. 原始可行性：$f_i(x^{\ast })\le 0$，$h_j(x^{\ast })=0$
2. 对偶可行性：${\lambda }_i^{\ast }\ge 0$
3. 互补松弛：${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$
4. 拉格朗日平稳性：$\nabla f_0(x^{\ast })+{\sum }_i{\lambda }_i^{\ast }\nabla f_i(x^{\ast })+{\sum }_j{\nu }_j^{\ast }\nabla h_j(x^{\ast })=0$

KKT的意义

在强对偶性成立的条件下，KKT条件是 $x^{\ast }$ 为原问题最优解的充要条件。这使得我们可以将约束优化问题转化为解方程组。

几何解释：在最优解处，梯度 $\nabla f_0(x^{\ast })$ 可以表示为约束梯度的非负线性组合，且约束在边界处必须”夹住”梯度方向。

---

四、梯度下降与收敛性分析

4.1 梯度下降法

梯度下降是最基本的迭代优化方法：

$x_{k+1}=x_k-{\eta }_k\nabla f(x_k)$

其中 ${\eta }_k>0$ 是步长（学习率）。

收敛性分析的基本假设：

1. Lipschitz连续梯度：$\Vert \nabla f(x)-\nabla f(y)\Vert \le L\Vert x-y\Vert$，即Hessian有界：$\Vert {\nabla }^{2}f(x)\Vert \le L$
2. 步长选择：固定步长 $\eta \le \frac{1}{L}$ 或随迭代变化

4.2 凸函数的收敛率

一般凸函数（Lipschitz连续）： $f(x_k)-f(x^{\ast })\le \frac{\Vert x_0-x^{\ast }{\Vert }^2}{2\eta k}$

取最优步长 $\eta =\frac{\Vert x_0-x^{\ast }\Vert }{L\sqrt{k}}$，得 $O(1/\sqrt{k})$ 收敛率。

强凸函数：设 $f$ $\mu$-强凸，即 $f(x)-\frac{\mu }{2}\Vert x{\Vert }^2$ 凸。

取 $\eta =1/L$，则： $f(x_k)-f(x^{\ast })\le {\left(1-\frac{\mu }{L}\right)}^k(f(x_0)-f(x^{\ast }))$

收敛率为 $O((1-\frac{\mu }{L}{)}^k)$，即线性收敛。

条件数的影响

收敛速度依赖于条件数 $\kappa =L/\mu$。条件数越大，收敛越慢。这解释了为什么预处理（preconditioning）可以加速优化。

4.3 非凸函数的收敛性

对于非凸函数，梯度下降保证：

• 梯度范数收敛到0：$\Vert \nabla f(x_k)\Vert \to 0$
• 收敛到稳定点（梯度为零的点），不一定是全局最优

在深度学习中，损失函数是非凸的，但梯度下降仍能有效找到好的局部最优解（实践中往往也接近全局最优）。

---

五、一阶与二阶优化方法

5.1 一阶方法

动量法（Momentum）： $v_{k+1}=\beta v_k+\nabla f(x_k)$ $x_{k+1}=x_k-\eta v_{k+1}$

动量累积历史梯度方向，加速收敛并减少震荡。Nesterov动量更激进：

$v_{k+1}=\beta v_k+\nabla f(x_k-\eta v_k)$

Adam（Adaptive Moment Estimation）： $m_k={\beta }_1{m}_{k-1}+(1-{\beta }_1)\nabla f(x_k)\text{（一阶矩）}$ $v_k={\beta }_2{v}_{k-1}+(1-{\beta }_2)(\nabla f(x_k){)}^2\text{（二阶矩）}$ ${\hat{m}}_k=\frac{m_k}{1-{\beta }_1^k},{\hat{v}}_k=\frac{v_k}{1-{\beta }_2^k}$ $x_{k+1}=x_k-\eta \frac{{\hat{m}}_k}{\sqrt{{\hat{v}}_k}+ϵ}$

Adam自动调整每个参数的学习率，在实践中效果极佳。

5.2 二阶方法

牛顿法： $x_{k+1}=x_k-({\nabla }^{2}f(x_k){)}^{-1}\nabla f(x_k)$

牛顿法的收敛率：对于强凸函数，达到 $O(e^{-c{k}^2})$（二次收敛），远超线性收敛。

但牛顿法的问题：

1. 需要计算和存储Hessian矩阵（$O(n^2)$ 存储）
2. 需要求解Hessian线性系统（$O(n^3)$ 计算）
3. Hessian可能不正定

拟牛顿法：用低秩矩阵逼近Hessian或其逆：

• BFGS：逼近Hessian
• L-BFGS：限制记忆的BFGS变体
• OWL-QN：用于L1正则化问题

5.3 约束优化的投影方法

投影梯度法： $x_{k+1}={\text{Proj}}_C\left(x_k-{\eta }_k\nabla f(x_k)\right)$

其中 ${\text{Proj}}_C(x)=\arg {\min }_{y\in C}\Vert x-y\Vert$ 是到凸集 $C$ 的投影。

对于简单约束（如箱约束 $x\in [l,u]$），投影有闭式解：

${\text{Proj}}_{[l,u]}(x{)}_i=\min (\max (x_i,l_i),u_i)$

---

六、Frank-Wolfe算法

6.1 算法描述

Frank-Wolfe算法（也称条件梯度法）是处理线性约束凸优化问题的投影自由方法：

初始化：$x_0\in \mathcal{D}$

迭代：

1. 线性最小化子问题：求解 $s_k=\arg {\min }_{s\in \mathcal{D}}\nabla f(x_k{)}^{T}s$
2. 步长计算：${\gamma }_k=\frac{2}{k+2}$（或线搜索）
3. 更新：$x_{k+1}=(1-{\gamma }_k)x_k+{\gamma }_k{s}_k$

6.2 与投影梯度法的对比

Frank-Wolfe的优势：

• 投影自由：只需解决线性最小化，而非投影到复杂集合
• 当 $\mathcal{D}$ 是多面体时，线性最小化可能比投影更高效
• 稀疏解：解天然是原子的凸组合

Frank-Wolfe的劣势：

• 收敛速度较慢：$O(1/k)$ 而非 $O(1/k^2)$
• 对于非多面体约束集合，线性最小化可能仍困难

SVM与Frank-Wolfe

支持向量机的对偶问题可以用Frank-Wolfe求解。线性最小化子问题退化为寻找支持向量，复杂度与活跃约束数成正比。

6.3 收敛性分析

对于强凸目标函数 $f$，Frank-Wolfe达到 $O(1/k)$ 的收敛率：

$f(x_k)-f(x^{\ast })\le \frac{2C_f}{k+2}$

其中 $C_f$ 是与函数曲率相关的常数。

条件梯度滑动（Conditional Gradient Sliding）结合了Frank-Wolfe与Nesterov加速的思想，可以达到更好的收敛率。

---

参考文献

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
2. Nesterov, Y. (2018). Lectures on Convex Optimization (2nd ed.). Springer.
3. Bertsekas, D. P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific.
4. Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
5. Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2), 223-311.

---

相关文档

• 线性代数深度指南 - 矩阵分解在优化中的应用
• 统计学深度指南 - MLE的优化视角与EM算法
• 信息论深度指南 - 互信息优化与信息瓶颈