引言

在机器学习领域，几乎所有算法——无论是有监督学习、无监督学习还是强化学习——最终都可以归结为求解一个最优化问题。换句话说，最优化方法贯穿于机器学习模型的推导与实现全过程，始终占据着核心地位。本文旨在系统梳理机器学习中常见的优化算法，理清它们之间的演进脉络，帮助读者从全局视角深入理解这一关键知识体系。

机器学习所求解的数学模型

绝大多数机器学习算法，本质上都是在寻找某个目标函数的极值。例如在有监督学习中，我们需要找到一个最优的映射函数 f(x)，使得它对训练样本的损失函数最小化（即最小化经验风险或结构风险）：

其中，N 代表训练样本数量，L 是单个样本的损失函数，w 是待求解的模型参数，xi 为样本特征，yi 为标签。有时我们也需要求解最优的概率密度函数 p(x)，使得训练样本的对数似然最大化（即最大似然估计）：

至于无监督学习，以聚类算法为例，其目标是使每个类中的样本到该类中心距离之和最小：

其中 k 是类别数目，x 是样本向量，μi 是第 i 个类的中心向量，Si 是第 i 个类的样本集合。

强化学习则要求解最优策略——即从状态 s 到动作 a 的映射（或在非确定性策略下为概率分布）：

使得在任意给定状态下，按照该策略执行动作后获得的累计回报最大化：

这里采用的是状态价值函数。简而言之，机器学习的核心可以概括为三个步骤：构建模型（映射函数）、定义评价标准（目标函数）、求解目标函数的极值。前两步属于机器学习的研究范畴，而第三步则是纯粹的数学问题——最优化方法，这也是本文重点关注的内容。

最优化算法的分类

面对各式各样的目标函数，研究者们开发了多种求解算法。除了极少数场景可以通过暴力搜索直接获得最优解外，机器学习中常用的优化算法大致可分为两类（不考虑模拟退火、遗传算法等随机优化方法）：

• 公式求解（解析解）
• 数值优化（近似解）

前者能够给出精确的公式解，通常出现在理论推导中；后者则在极值点难以精确计算时，通过数值方法近似求解。此外，分治、动态规划等思想也常被用于优化问题，后文会单独介绍。一个好的优化算法需要满足两个条件：一是能够正确找到各种情况下的极值点，二是计算速度快。下图展示了这些算法的分类与相互关系：

接下来，我们将按照这张图逐步展开讲解。

费马定理

对于可导函数，求极值的标准方法是寻找导数为零的点——这就是费马定理。微积分告诉我们，在极值点处导数必然为零：

对于多元函数，条件变为梯度为零：

导数为零的点称为驻点。需要注意的是，导数为零只是极值存在的必要条件，而非充分条件——它只是“疑似”极值点。究竟是极大值还是极小值，需要借助更高阶的导数来判断。对于一元函数，如果 x 是驻点：

• f''(x) > 0 → 极小值
• f''(x) < 0 → 极大值
• f''(x) = 0 → 还需考察更高阶导数

对于多元函数，Hessian 矩阵正定对应极小值，负定对应极大值，不定则需进一步分析（此处应为“还需考虑更高阶信息”）。在导数为零的点，函数也可能不取极值，这类点称为鞍点。下图展示了一个鞍点的示例（来自 SIGAI 云端实验室）：

除了鞍点，局部极值也是常见问题。如果对优化问题施加一定限制，例如凸优化——要求可行域为凸集、目标函数为凸函数，就可以有效避免这两类困扰。尽管驻点不是充要条件，但找到驻点再加以判断筛选，比直接寻找极值要容易得多。通常，无论是理论分析还是数值算法，都以寻找驻点为主要目标。对于一元函数，求解导数方程；对于多元函数，求解偏导方程组——这些是微积分的基本方法。幸运的是，机器学习中大部分目标函数都是可导的，因此这套方法具有很强的实用性。

拉格朗日乘数法

费马定理处理的是无约束极值问题，但实际应用中常常遇到带有等式或不等式约束的情况。对于等式约束问题，经典的解法是拉格朗日乘数法。例如：

构造拉格朗日乘子函数：

在最优点处，对 x 和乘子 λi 的导数都必须为零：

解这个方程组即可得到最优解。拉格朗日乘数法在机器学习中的典型应用包括：主成分分析、线性判别分析、流形学习中的拉普拉斯特征映射，以及隐马尔可夫模型。

KKT条件

KKT条件是拉格朗日乘数法的推广，用于同时包含等式和不等式约束的极值问题。给定优化问题：

类似于拉格朗日对偶，构造乘子函数：

λ 和 μ 称为 KKT 乘子。在最优点 x* 处需满足以下条件：

等式约束 hj(x*)=0 和不等式约束 gk(x*) ≤ 0 是问题本身必须满足的；梯度为零条件与拉格朗日乘数法一致。此外，新增的条件与 gi(x) 相关：

KKT条件同样只是必要条件。它在机器学习中最著名的应用是支持向量机（SVM）。

数值优化算法

前面介绍的三种方法在理论推导和某些可求解析解的场景（如线性函数、正态分布的最大似然估计）中很有效，但大多数情况下，梯度等于零的方程组无法直接求解——例如方程中包含指数、对数等超越函数。此时必须借助近似算法，即数值优化。数值优化通常利用导数的信息：一阶导数对应一阶优化，二阶导数对应二阶优化。

工程实现中最常用的方法是迭代法：从一个初始点 x0 出发，反复按照某种规则从 xk 移动到下一个点 xk+1，构造数列直到收敛到梯度为零的点。即：

规则通常利用一阶导数（梯度）或二阶导数（Hessian 矩阵）。迭代法的核心是得到由前一个点确定下一个点的迭代公式：

梯度下降法

梯度下降法沿着梯度的反方向进行搜索，利用一阶导数信息。迭代公式为：

根据一阶泰勒展开，在负梯度方向上函数值会下降。只要学习率足够小且尚未到达梯度为零的点，每次迭代函数值必然下降。学习率需要设置得非常小，是为了保证迭代后的 xk+1 仍位于 xk 的邻域内，从而忽略泰勒展开中的高次项，确保下降方向正确。梯度下降法及其变种在机器学习中应用广泛，尤其在深度学习领域。

动量项

为了加快收敛速度并减少震荡，引入了动量项。动量项会累积之前迭代的梯度值，更新公式变为：

其中 Vt+1 取代了原来的梯度项，其计算方式为：

这是上一时刻动量与本次梯度的加权平均，α 是学习率，μ 是动量系数。按时间展开后，第 t 次迭代实际上使用了从 1 到 t 的所有梯度，且较早的梯度按 μ^t 指数衰减：

动量项相当于让迭代过程沿着之前的惯性方向前进。

AdaGrad算法

AdaGrad 是梯度下降法的直接改进。标准梯度下降法依赖人工设置学习率——太小会导致收敛缓慢，太大则可能无法收敛，很难找到一个合适的值。AdaGrad 根据历史梯度动态调整每个参数的学习率（每个分量 xi 都有自己的学习率）。更新公式为：

这里 α 是学习因子，gt 是第 t 次迭代的梯度向量，ε 是一个很小的正数用于避免除零，下标 i 表示分量。与标准梯度下降相比，多了分母中的累积项——它累积了历史梯度的平方和。历史梯度绝对值越大的分量，学习率越小，反之则越大。但这也有缺点：需要人工设置全局学习率 α，且分母随时间累积会越来越大，导致学习率趋近于零，参数无法有效更新。

RMSProp算法

RMSProp 改进了 AdaGrad，避免了学习率过早衰减到零。具体做法是构造一个向量 RMS，初始化为零，按衰减系数累积历史梯度平方值：

不同于 AdaGrad 直接累加所有历史梯度平方和，这里按 δt 衰减后再累加。参数更新公式为：

δ 是人工参数，与 AdaGrad 一样仍需要全局学习率 α。

AdaDelta算法

AdaDelta 进一步改进了 AdaGrad，既避免了学习率衰减到零，又去掉了对全局学习率的依赖。假设要优化参数 x，第 t 次迭代的梯度为 gt。算法先初始化两个向量为零：

E[g²] 是梯度平方（每个分量分别平方）的累计值，更新公式为：

然后计算 RMS 量：

再计算参数更新值：

RMS[Δx]t-1 的算法类似。这个更新值仍然通过梯度构造，但学习率由梯度的历史值自动确定。最终更新公式为：

参数迭代公式为：

Adam算法

Adam 将自适应学习率与动量项整合到了一起。算法利用梯度构造两个向量 m 和 v：m 相当于动量项，v 累积梯度平方和用于自适应学习率。初始值均为零，更新公式为：

β1、β2 是人工参数，i 为分量下标。然后构造参数更新值：

这里 m 类似动量，v 用于构造学习率。

随机梯度下降法

假设训练集包含 N 个样本，有监督学习优化的是平均损失函数：

L(w,xi,yi) 是单个样本的损失，r(w) 是正则项，λ 是正则化权重。当 N 很大时，每次迭代使用所有样本计算成本太高。改进方法是每次迭代只选取一批样本（M << N）来近似损失函数。目标函数变为：

随机梯度下降在概率意义下收敛。

牛顿法

牛顿法是二阶优化方法，利用一阶和二阶导数直接寻找梯度为零的点。迭代公式为：

其中 H 是 Hessian 矩阵，g 是梯度。牛顿法不能保证每次迭代函数值都下降，也不能保证收敛到极小值。实现时也需要设置学习率（原因同梯度下降法），通常采用直线搜索（line search）。一般不直接求 Hessian 逆矩阵，而是求解线性方程组：

其解 d 称为牛顿方向。迭代终止条件为梯度充分接近零或达到最大迭代次数。牛顿法收敛速度快，但每次迭代都需要计算 Hessian 矩阵并求解线性方程组，运算量较大，且 Hessian 矩阵可能不可逆。牛顿法在 logistic 回归、AdaBoost 等算法中有实际应用。

拟牛顿法

牛顿法需要计算 Hessian 矩阵并求解线性方程组，且 Hessian 可能不可逆。拟牛顿法不直接计算 Hessian 逆，而是通过其他手段构造一个近似的正定对称矩阵来替代。具体做法是构造一个近似 Hessian 矩阵或其逆的正定对称矩阵，并用该矩阵进行牛顿迭代。

可信域牛顿法

标准牛顿法可能不收敛，也不保证函数值递减。解决方法有两种：直线搜索和可信区域法。可信域牛顿法是截断牛顿法的一个变种，用于处理带界限约束的优化问题。每一步有一个迭代点 xk、可信域大小 Δk 以及二次目标函数（由泰勒展开近似得到，忽略二次以上项）：

然后寻找 sk 在满足 ||S|| ≤ Δk 的前提下近似最小化 qk(S)。接着检查比值：

这是实际减少量与二次模型预测减少量的比值，据此动态调整可信域的大小。可信域牛顿法在 logistic 回归、线性支持向量机的求解中有实际应用（可参考 liblinear 开源库）。

分治法

分治法将大问题分解为若干子问题分别求解，再组合成整个问题的解。在最优化中，具体做法是每次只调整优化向量的部分分量，其余固定不变。

坐标下降法

坐标下降法每次只优化一个变量，是典型的分治策略。需要求解的优化问题为：

流程是每次选择一个分量 xi 进行优化，固定其他分量，将多元函数极值转化为一元函数极值。当问题规模很大时，这种方法能有效加速。坐标下降法在 logistic 回归、线性支持向量机的求解中有应用（参考 liblinear）。

SMO算法

SMO 算法也是一种分治法，用于求解支持向量机的对偶问题。加入松弛变量和核函数后的对偶问题为：

SMO 的核心思想是每次挑出两个分量 αi 和 αj 进行优化，其他固定，这样能够满足等式约束（因为只调整一个分量会破坏等式）。选好两个分量后，它们的目标函数是二元二次函数，带等式和不等式约束，可以直接求得公式解——相当于某个区间内一元二次函数的极值问题。

分阶段优化

分阶段优化每次迭代时，先固定优化变量 X 的一部分 a，对另一部分 b 进行优化；然后固定 b，对 a 进行优化，如此反复直到收敛。AdaBoost 是典型代表。AdaBoost 使用指数损失函数：

强分类器是多个弱分类器的加权和，代入损失函数得到目标函数：

这里将指数损失拆分成两部分：已有的强分类器 Fj−1（视为常数）和当前弱分类器 f 的损失。目标函数简化为：

其中：

这个问题分两步求解：首先将弱分类器权重 β 视为常数，求最优弱分类器 f；得到 f 后再优化权重系数 β。

动态规划算法

动态规划也是一种重要的求解思想，它将问题分解为相互关联的子问题。如果整个问题的最优解中某一部分同时也是子问题的最优解（即最优子结构），那么就可以通过求解子问题逐步得到全局最优解。隐马尔可夫模型的解码算法（维特比算法）以及强化学习中的动态规划都是典型代表。这类问题通常涉及离散变量的组合优化，前面基于导数的算法无法直接使用。动态规划的基础是贝尔曼最优化原理，一旦写出递归形式的最优化方程，就能构造出高效的求解算法。