凸优化基础理论

凸优化是现代机器学习和深度学习的数学基石。尽管深度神经网络本身是非凸的，但许多理论分析、技术理解和算法设计都依赖于凸优化的工具和直觉。本文档系统介绍凸优化中最重要的基础概念：凸集、凸函数及其基本性质。

1. 凸集

1.1 定义与基本性质

定义（凸集）：设 $C\subseteq {\mathbb{R}}^n$ 为一个集合，如果对于任意 $x,y\in C$ 和任意 $\lambda \in [0,1]$，都有

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

则称 $C$ 是凸集。

几何上，这意味着连接集合中任意两点的线段完全包含在该集合内。

常见凸集：

集合类型	定义	凸性
仿射集	$\{x\mid Ax=b\}$	凸
半空间	$\{x\mid a^{T}x\le b\}$	凸
欧几里得球	$\{x\mid \Vert x-x_c{\Vert }_2\le r\}$	凸
椭球	$\{x\mid (x-x_c{)}^T{P}^{-1}(x-x_c)\le 1\}$	凸
多面体	$\{x\mid Ax\le b,Cx=d\}$	凸
范数球	$\{x\mid \Vert x\Vert \le 1\}$	凸
半正定锥	${\mathbb{S}}_{+}^n=\{X\mid X⪰0\}$	凸

1.2 凸集运算

凸集的闭包、交集、和、透视变换等操作保持凸性：

定理（凸集运算保持凸性）：

• 交集：$C_1\cap C_2$ 是凸集
• 和：$C_1+C_2=\{x+y\mid x\in C_1,y\in C_2\}$ 是凸集
• 仿射变换：$f(C)=\{f(x)\mid x\in C\}$ 是凸集
• 透视变换：$P(z,t)=z/t$ 保持凸性

1.3 分离定理与支撑超平面

分离定理是凸分析中最重要的结果之一，它建立了凸集边界的几何结构。

分离超平面定理：设 $C$ 和 $D$ 为两个非空不相交的凸集，则存在非零向量 $a$ 和常数 $b$，使得

$$a^{T}x\le b\le a^{T}y,\forall x\in C,y\in D$$

即超平面 $\{x\mid a^{T}x=b\}$ 分离了 $C$ 和 $D$。

支撑超平面定理：设 $C$ 为凸集，$x_0\in \partial C$（边界点）。则存在非零向量 $a$，使得

$$a^{T}x\le a^T{x}_0,\forall x\in C$$

这意味着存在支撑超平面在 $x_0$ 处”支撑”凸集 $C$。

1.4 极点和极点定理

定义（极点）：点 $x\in C$ 是极点，如果不存在 $y,z\in C$（$y\ne z$）和 $\lambda \in (0,1)$ 使得 $x=\lambda y+(1-\lambda )z$。

** Kreŭn-Milman 定理**：每个紧凸集是其极点的凸包：

$$C=\text{conv}(\text{extreme}(C))$$

这一定理在理论上保证了凸集可以用有限个极点完全描述。

2. 凸函数

2.1 定义与基本性质

定义（凸函数）：函数 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 是凸函数，如果 $\text{dom}(f)$ 是凸集，且对任意 $x,y\in \text{dom}(f)$ 和 $\lambda \in [0,1]$：

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

严格凸：如果不等式在 $x\ne y$ 和 $\lambda \in (0,1)$ 时严格成立。

几何解释：函数图像上任意两点之间的弦线位于函数图像上方。

常见凸函数：

函数	定义	凸性条件
指数函数	$e^{ax}$	恒凸
对数函数	$-\log x$	凸
范数	$\Vert x{\Vert }_p$	凸（$p\ge 1$）
线性函数	$a^{T}x+b$	凸
二次函数	$x^{T}Px+q^{T}x+r$	$P⪰0$
负熵	$x\log x$	凸
逻辑斯蒂	$\log (1+e^x)$	凸
行列式的对数	$\log \det (X)$	凸（$X\succ 0$）

2.2 凸函数的等价条件

一阶条件：可微函数 $f$ 是凸函数，当且仅当

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

这称为梯度不等式，几何上表示切平面位于函数下方。

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

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

2.3 共轭函数

定义（共轭函数）：给定函数 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$，其 Fenchel 共轭 $f^{\ast }:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 定义为

$$f^{\ast }(y)=\underset{x\in \text{dom}(f)}{\sup }\{y^{T}x-f(x)\}$$

共轭函数的性质：

1. Fenchel 不等式：$f(x)+f^{\ast }(y)\ge x^{T}y$
2. 双向共轭：如果 $f$ 是闭凸函数，则 $f^{\ast \ast }=f$
3. 凸性：$f^{\ast }$ 总是闭凸函数

示例：

原函数 $f$	共轭函数 $f^{\ast }$
$\frac{1}{2}{x}^2$	$\frac{1}{2}{y}^2$
$\Vert x{\Vert }_1$	${\delta }_{\{\Vert y{\Vert }_{\infty }\le 1\}}$
$-\log x$	$-1-\log (-y)$ （$y<0$）
$e^x$	$y\log y-y$ （$y>0$）

2.4 函数的闭包与延拓

有效域：$\text{dom}(f)=\{x\mid f(x)<+\infty \}$

闭包：闭包 $\text{cl}f$ 是使得 $f$ 成为下半连续的最小的扩展函数。

扩展值延伸：扩展函数 $\tilde{f}:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 定义为

$$\tilde{f}(x)=\{\begin{array}{ll}f(x)& x\in \text{dom}(f)\\ +\infty & x\notin \text{dom}(f)\end{array}$$

3. 凸优化问题

3.1 标准形式

凸优化问题的标准形式为：

$$\begin{array}{rl}\underset{x}{\min }& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

其中 $f$ 和 $g_i$ 是凸函数，$h_j$ 是仿射函数。

3.2 凸优化问题的性质

关键性质：

1. 全局最优性：任何局部最优解都是全局最优解
2. 最优性条件：在适当条件下（见KKT条件），解满足一阶最优性条件
3. 对偶理论：强对偶通常成立（Slater条件）

凸优化问题的分类：

问题类型	特殊形式	应用
线性规划 (LP)	线性目标 + 线性约束	调度、资源分配
二次规划 (QP)	二次目标 + 线性约束	投资组合
半正定规划 (SDP)	线性目标 + 半正定约束	控制系统
二阶锥规划 (SOCP)	线性目标 + 二阶锥约束	鲁棒优化

3.3 等价变换

许多非标准形式的问题可以通过变量替换或约束重组转化为标准凸优化形式：

1. 绝对值消除：$|x_i|$ 替换为 $t_i$，添加 $x_i\le t_i,-x_i\le t_i$
2. 分段函数：使用指示函数或 log-barrier
3. 范数松弛：$\Vert Ax-b\Vert$ 可转化为 SOCP

4. 一阶最优性条件

4.1 无约束问题

对于无约束可微凸优化问题 ${\min }_{x}f(x)$，最优性条件为

$$\nabla f(x^{\ast })=0$$

这是因为 $f$ 凸意味着 $\nabla f(x^{\ast })=0$ 既是必要条件也是充分条件。

4.2 等式约束问题

对于问题 ${\min }_{x}f(x)$ s.t. $Ax=b$，KKT条件给出

$$\{\begin{array}{l}\nabla f(x^{\ast })+A^T{\nu }^{\ast }=0\\ A{x}^{\ast }=b\end{array}$$

其中 ${\nu }^{\ast }$ 是拉格朗日乘子。

4.3 不等式约束问题

对于不等式约束问题，一阶必要条件涉及 互补松弛：

$${\lambda }_i^{\ast }\ge 0,{\lambda }_i^{\ast }{g}_i(x^{\ast })=0,i=1,\dots ,m$$

5. 经典算法

5.1 梯度下降法

对于无约束凸优化问题

$$x^{k+1}=x^k-{\alpha }_k\nabla f(x^k)$$

收敛性：设 $f$ 为 $\mu$-强凸且 $L$-光滑，则

$$f(x^k)-f(x^{\ast })\le {\left(1-\frac{\mu }{L}\right)}^k[f(x^0)-f(x^{\ast })]$$

收敛速率为线性，条件数 $\kappa =L/\mu$ 决定收敛速度。

5.2 投影梯度下降

对于约束优化问题，投影梯度下降为

$$x^{k+1}={\text{Proj}}_C\left(x^k-{\alpha }_k\nabla f(x^k)\right)$$

其中 ${\text{Proj}}_C(\cdot )$ 是到可行域 $C$ 的投影。

5.3 近端梯度法

对于复合目标 $f(x)=g(x)+h(x)$，其中 $g$ 光滑、$h$ 闭凸：

$$x^{k+1}={\text{prox}}_{\alpha h}\left(x^k-\alpha \nabla g(x^k)\right)$$

近端算子 ${\text{prox}}_h$ 定义为

$${\text{prox}}_h(x)=\arg \underset{y}{\min }\left\{h(y)+\frac{1}{2}\Vert y-x{\Vert }_2^2\right\}$$

6. 与深度学习的联系

6.1 凸代理问题

虽然神经网络训练是非凸的，但许多分析使用凸代理：

• 线性规划松弛：用于分析网络表达能力
• 核方法视角：无限宽网络对应凸优化
• 损失 Landscape 分析：使用凸函数的下界

6.2 凸组合解释

在特定条件下，深度网络的某些组件可以解释为凸优化问题的解：

• softmax 对应多项 logistic 回归（凸）
• ReLU 激活 分割输入空间，每个区域线性（分段凸）

6.3 对偶与正则化

对偶理论为理解正则化提供了几何视角：

• 权重衰减（$L^2$ 正则）对应欧几里得范数的对偶
• $L^1$ 正则 促进稀疏性，对应 ${\ell }_1$ 范数约束

7. 总结

凸优化提供了理解深度学习优化问题的强大框架：

1. 凸集与凸函数 建立了优化问题数学结构的基础
2. 对偶理论 提供了分析约束问题和理解正则化的工具
3. 最优性条件（KKT条件）连接了原问题与对偶问题
4. 收敛理论 为算法设计提供了理论基础

尽管深度神经网络训练本质上是非凸的，但凸优化的工具和直觉在理论分析和算法设计中仍然不可或缺。理解凸优化的基础对于深入研究深度学习理论至关重要。

参考资料

---

相关主题：拉格朗日对偶与KKT条件、Fenchel对偶与近端算子、自适应优化器收敛性理论