一、引言：为什么要学习凸优化？

机器学习的训练过程本质上是一个优化问题：我们试图找到一组参数，使得模型在给定数据上的「损失」最小。

对于许多经典机器学习模型（如支持向量机 SVM、Lasso 回归等）来说，这个损失函数是凸的，它们的理论分析和高效求解可以通过凸优化这个工具来完成。但可惜，对于复杂的深度神经网络而言，通常是一个非凸的函数，意味着它拥有无数个局部最小值，这让优化过程充满了挑战。

这是否意味着，在深度学习时代，凸优化理论就没有用武之地了呢？也不尽然。

尽管整个深度网络是非凸的，但在其训练过程中，我们常常会遇到一些凸的子问题，或者优化算法本身的设计灵感来源于凸优化——例如正则化项的处理、某些高效优化器的设计思想等等。理解这些「老古董」有助于我们触类旁通，理解深度学习的某些设计哲学。

二、凸集与凸函数：构建优化问题的「地形」

在深入探讨凸优化问题之前，我们必须先理解其最基础的「砖块」——凸集和凸函数。它们是定义优化问题「地形」的关键概念，也是保证凸优化问题具有良好性质（例如全局最优解的存在性）的根本原因。

2.1 凸集：形状的「良好」性质

假设你站在一个区域内，如果从这个区域内的任意一点走向任意另一点，你都能保证整个行进路线都在这个区域内部，那么这个区域就是一个凸集。

用数学的语言描述：一个集合 $C$ 被称为凸集 (Convex Set)，如果对于任意两点 $x$ 和 $y \in C$ ，以及任意实数 $\theta \in [0, 1]$ ，都有：

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

其中， $\theta x + (1-\theta)y$ 表示连接 $x$ 和 $y$ 的线段上的所有点。

凸集在几何上最大的特点就是它「没有洞」，也没有「凹陷」或「内角」。你可以把它想象成一个「紧致内聚」的区域。比如：

是凸集：圆形、方形、三角形、超平面、半空间（超平面一侧的区域）。
不是凸集：星形、弯月形、带洞的甜甜圈形，因为你可以在这些形状中找到两点，它们之间的连线会穿过形状的外部。

💡 重要性质： 任意多个凸集的交集仍然是凸集。这在构建复杂的优化问题可行域时非常有用，因为许多约束条件都可能定义一个凸集，而所有约束同时满足的区域（即所有凸集的交集）依然是凸集。

2.2 凸函数：碗状的损失曲面

有了凸集的概念，我们就可以定义凸函数 (Convex Function) 了。直观上，一个凸函数就像一个「碗」，它的函数图像总是「向上弯曲」或平坦的，没有局部凹陷。

数学上，一个函数 $f(x)$ 被称为凸函数，如果其定义域 $dom(f)$ 是一个凸集，且对于任意 $x, y \in dom(f)$ 和任意 $\theta \in [0, 1]$ ，都有：

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

这个不等式被称为 Jensen 不等式。它的几何意义是：函数图像上任意两点连线（割线）上的值，总是在函数图像的上方或与其重合。

比如一个一维的函数 $f(x) = x^2$ ，它的图像是一个开口向上的抛物线，就像一个碗。无论你取抛物线上哪两点，连接它们的线段都会在抛物线的上方。
而像 $f(x) = \sin(x)$ 这样的函数就不是凸函数，因为它有「波峰」和「波谷」。
将这个概念扩展到更高维度，例如二维的 $f(x,y) = x^2 + y^2$ ，它的图像就像一个三维的碗。

凸函数最令人欣喜的性质，也是其在优化领域如此重要的原因，就是：凸函数的任意一个局部最小值，都是其全局最小值。

这意味着，如果你找到了一个凸函数的局部最低点，你就不必担心它是不是「假」的最低点，它一定是整个函数图像的最低点。此外，所有全局最小值的集合，也构成一个凸集。

三、凸优化：我变「凸」了，也变简单了

现在我们已经理解了凸集和凸函数，就可以正式定义凸优化问题 (Convex Optimization Problem) 了。凸优化是优化理论中一个非常重要且研究深入的分支，因为它具有许多优美的理论性质和高效的求解算法。

3.1 凸优化问题的标准形式

回忆一下约束优化的标准形式：

\begin{aligned} \min_{x} \quad & f_0(x) \\ \text{s.t.} \quad & f_i(x) \le 0, \quad i=1,\dots,m \\ & h_i(x) = 0, \quad i=1,\dots,p \end{aligned}

其中：

$x$ 是我们要优化的变量。
$f_0(x)$ 是目标函数 (Objective Function)，我们需要最小化它。
$f_i(x) \le 0$ 是 $m$ 个不等式约束 (Inequality Constraints)。
$h_i(x) = 0$ 是 $p$ 个等式约束 (Equality Constraints)。

为了使这个问题成为一个凸优化问题，必须满足以下条件：

目标函数 $f_0(x)$ 必须是凸函数。
不等式约束函数 $f_i(x)$ 必须是凸函数。这意味着由 $f_i(x) \le 0$ 定义的可行区域是一个凸集。
等式约束函数 $h_i(x)$ 必须是仿射函数 (Affine Function)。仿射函数是指 $h_i(x) = a_i^T x + b_i = 0$ 这种形式（线性函数是仿射函数的一种特殊情况，即 $b_i=0$ ）。

如果一个优化问题满足以上条件，它就拥有了凸优化问题的「良好」性质：

全局最优性保证：任何局部最优解都是全局最优解。这意味着一旦找到一个解，它就是最好的。
高效可解性：存在许多成熟且高效的算法（如内点法、牛顿法、梯度下降法等）可以找到凸优化问题的全局最优解。这些算法通常具有多项式时间复杂度。

3.2 经典机器学习中的凸优化问题

许多经典机器学习模型在特定形式下就是凸优化问题：

线性回归与 L2 正则化 (Ridge Regression)：最小化均方误差 (MSE) 加上参数 L2 范数的平方，这是一个无约束的凸优化问题。
逻辑回归与 L2 正则化：最小化负对数似然损失加上参数 L2 范数的平方，同样是凸优化问题。
支持向量机 (SVM) 的原始问题：最大化分类间隔，同时满足样本分类正确的约束，这是一个带不等式约束的二次规划问题，也是凸优化问题。

3.3 KKT 条件

在之前的学习中，我们初步介绍了拉格朗日乘子法和 KKT 条件作为求解一般约束优化问题的必要条件。快速回顾一下，我们构造拉格朗日函数：

L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)

其中 $\lambda_i$ 是与不等式约束相关的拉格朗日乘子， $\nu_i$ 是与等式约束相关的拉格朗日乘子。

如果 $x^*$ 是一个局部最优解，并且满足某些正则性条件，那么必然存在 $\lambda^*$ 和 $\nu^*$ ，使得以下 KKT 条件成立：

驻点条件 (Stationarity)：

\nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{i=1}^p \nu_i^* \nabla h_i(x^*) = 0

这在几何上意味着：目标函数的梯度与约束的法向量在最优点处处于严格平衡，任何进一步降低目标函数的尝试都会违反约束条件。

在约束边界处，目标函数的梯度恰好与约束的法向量方向相反（或线性相关），此时目标函数的下降方向正被约束边界「阻挡」。

原问题可行性条件 (Primal Feasibility)： $f_i(x^*) \le 0, \quad h_i(x^*) = 0$
对偶可行性条件 (Dual Feasibility)： $\lambda_i^* \ge 0$
互补松弛条件 (Complementary Slackness)： $\lambda_i^* f_i(x^*) = 0$
这告诉我们，只有那些「紧绷」的约束（即 $f_i(x^*) = 0$ ）才会对最优解产生影响（即 $\lambda_i^* > 0$ ）。那些「松弛」的约束意味着我们可以在那个方向上稍微移动而不触碰到边界，因此它们对应的乘子 $\lambda_i^* = 0$ 。

3.4 Slater 条件

对于凸优化问题，如果满足一些特殊的条件，那么 KKT 条件不仅是局部最优解的必要条件，更是充要条件。

Slater 条件就是这些特殊条件中的一种：对于凸优化问题，若存在一个严格可行点 $x$ ，使得所有非仿射不等式约束严格成立（即 $f_i(x) < 0$ ，不能取等号），而其他仿射约束正常满足，则称 Slater 条件成立。

你可以把 Slater 条件理解为一种「非退化条件」或者「内部点条件」。它要求对于曲面状的（非仿射）约束，你的可行域不能仅仅是这些曲面的边界，而必须包含内部的「活动空间」。这一特性极大地简化了凸优化问题的求解，我们只要找到满足 KKT 条件的点，就找到了全局最优解。

3.5 算法视角

内点法 (Interior-Point Methods) 等高效凸优化算法，就是基于 KKT 条件迭代求解的。
在支持向量机 (SVM) 中，互补松弛条件 $\lambda_i^* f_i(x^*) = 0$ 对于识别「支持向量」至关重要：如果 $\lambda_i^* > 0$ ，则 $f_i(x^*) = 0$ ，样本点位于分类超平面的边界上（即支持向量）；如果 $\lambda_i^* = 0$ ，则该样本点在分类边界内，不是支持向量。

四、拉格朗日对偶：从另一个角度看问题

拉格朗日对偶理论是优化领域中最优雅、最强大的工具之一。它能将一个看似困难的问题转化为一个更容易解决的对偶问题，并能揭示原问题中隐藏的深刻结构。

4.1 拉格朗日函数与对偶函数

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

g(\lambda, \nu) = \inf_{x \in D} L(x, \lambda, \nu) = \inf_{x \in D} \left( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right)

对偶函数 $g(\lambda, \nu)$ 总是凹函数 (Concave Function)，无论原始问题是否是凸的！这是一个非常强大的性质，因为它意味着最大化对偶函数本身就是一个极其标准的凸优化问题。

4.2 几何视角：支撑超平面和下界

对偶函数可以被看作是原函数及其约束的线性组合的下确界。直观地，你可以将对偶函数看作是一系列原函数图像的支撑超平面。每组 $(\lambda, \nu)$ 定义了一个支撑超平面，对偶函数的值就是这些超平面能够「抬升」到的最高位置，同时仍然保持在原函数图像的下方。

对偶函数的一个直接应用是：它提供原问题最优值 $p^*$ 的一个下界。即 $g(\lambda, \nu) \le p^*$ 。

4.3 弱对偶与强对偶

我们定义对偶问题 (Dual Problem) 为：

\max_{\lambda \ge 0, \nu} \quad g(\lambda, \nu)

设其最优值为 $d^*$ 。

弱对偶 (Weak Duality)： $d^* \le p^*$ 总是成立。对偶问题的最优值总是小于或等于原问题的最优值。
强对偶 (Strong Duality)：在某些条件下（如满足 Slater 条件的凸优化问题），有 $d^* = p^*$ 。此时我们通过解决对偶问题就能获得原问题的最优解。

4.4 物理视角与算法意义

物理视角：如果原问题是寻找弹簧系统在约束下的最小势能，那么拉格朗日乘子就可以理解为为了维持约束所施加的「反作用力」。对偶问题就是找到这些力的最大值。
算法意义：对偶问题往往更容易求解（可能变量更少，或变为无约束问题）。更重要的是，它为机器学习中的核技巧 (Kernel Trick) 奠定了数学基础。

五、非光滑优化：处理尖锐的损失函数

在深度学习和机器学习的实践中，我们经常遇到在某些点不可微的凸函数，如 ReLU 激活函数在 $x=0$ 点不可微，L1 范数在 $x=0$ 点也不可微。传统的梯度下降无法直接应用。

5.1 什么是次梯度 (Subgradient)？

对于一个凸函数 $f(x)$ ，它的次梯度 (Subgradient) 是一个向量 $g$ ，满足对于定义域内的任意点 $y$ ，都有：

f(y) \ge f(x) + g^T(y - x)

在光滑点，函数图像只有一个唯一的切平面，其余斜率就是梯度。
在非光滑点（尖点/角点），可以有多个切平面「支撑」在函数图像下方。这些切平面的斜率集合就是次梯度集合 $\partial f(x)$ 。

例如，Lasso 回归中的 L1 正则化项 $\|w\|_1$ 在 $w=0$ 处不可微，使用次梯度方法就能有效促使模型参数变得稀疏。

5.2 次梯度方法

次梯度方法是梯度下降法的一个直接推广，迭代更新公式为：

x^{(k+1)} = x^{(k)} - \alpha_k g^{(k)}

其中 $g^{(k)}$ 是在 $x^{(k)}$ 点处的任意一个次梯度。次梯度方法简单易实现，但收敛速度较慢，且通常需要递减的步长 $\alpha_k$ 。

5.3 近端算子与近端梯度方法

对于可以分解为「光滑部分 + 非光滑部分」的目标函数（如 $f(x) + h(x)$ ），我们可以引入近端算子 (Proximal Operator)：

prox_{\alpha h}(x) = \arg\min_z \left( h(z) + \frac{1}{2\alpha}\|z - x\|_2^2 \right)

近端算子旨在找到一个点 $z$ ，使得 $h(z)$ 较小，同时又尽量接近输入点 $x$ 。以 L1 范数为例，其近端算子是著名的软阈值算子 (Soft-thresholding operator)：

S_{\alpha}(x) = \text{sign}(x) \max(|x| - \alpha, 0)

近端梯度方法 (Proximal Gradient Method) 的更新公式为：

x^{(k+1)} = prox_{\alpha h} \left( x^{(k)} - \alpha \nabla f(x^{(k)}) \right)

这相当于先对光滑部分做一次梯度下降，然后用近端算子对结果进行「修正」（例如将绝对值极小的参数直接收缩为 0，从而实现特征选择）。

六、机器学习中的应用

6.1 支持向量机 (SVM) 的对偶解析

原始问题：寻找最大化分类间隔的超平面，是一个凸二次规划问题。
对偶问题：通过拉格朗日对偶，我们发现最优解只依赖于样本之间的内积 $x_i^T x_j$ 。
核技巧 (Kernel Trick)：将内积替换为核函数 $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$ ，我们就可以在无需显式计算高维特征的情况下，隐式地将数据映射到高维空间，优雅地解决非线性分类问题。

6.2 正则化项中的凸优化思想

L2 正则化 (Ridge)：损失中加入 $\lambda \|w\|_2^2$ ，这是一个光滑凸函数，给梯度增加了一个「权重衰减」项，防止过拟合。
L1 正则化 (Lasso)：损失中加入 $\lambda \|w\|_1$ ，这是一个非光滑凸函数，它促使参数趋向于 $0$ ，实现稀疏性，提高可解释性。

6.3 其他应用概述

优化器理论：Adam、RMSProp 等虽然优化非凸损失，但设计灵感常借鉴凸优化理论。
网络剪枝与量化：常被建模为带有稀疏性约束或整数约束的近似凸优化问题。
对抗样本生成：在给定扰动预算（如 Lp 范数约束的凸集）下最大化分类错误的优化问题。

七、总结

认识「凸」：理解凸集和凸函数这些核心概念，它们是构建所有凸优化问题的基础。
驾驭「对偶」：学习拉格朗日对偶理论，掌握如何将一个优化问题转化为其对偶形式，并理解弱对偶和强对偶的含义。
应对「非光滑」：探讨在深度学习中常见的非光滑凸函数的优化方法——次梯度法和近端算法。
融会贯通：虽然深度学习的核心优化问题是非凸的，但凸优化和对偶理论仍然是理解局部最优、泛化能力以及设计现代优化算法的核心基石和参考框架。

Chen Kunpeng

【深度学习数学基础】凸函数与凸优化