优化理论(Optimization Theory)是数学和机器学习中最重要的基础理论之一,也是人工智能模型训练的底层支撑。它研究如何从一组可行解中找到使目标函数达到极值(最大值或最小值)的解。在机器学习和深度学习中,几乎所有模型的训练都可以归结为一个优化问题——寻找使得损失函数最小的参数组合。从线性回归的最小二乘法到大型语言模型的万亿参数预训练,优化理论贯穿了 AI 开发的每一个环节。理解优化理论中的核心概念(凸性、对偶性、约束优化)是掌握训练算法(如随机梯度下降 SGD)的前提。
以下全景图展示了优化理论的核心分支及其相互关系:
mindmap
root((优化理论))
问题分类
无约束优化
约束优化
不等式约束
等式约束
凸优化
凸集
凸函数
凸组合
核心技术
拉格朗日对偶
KKT条件
Slater条件
求解算法
梯度下降及其变体
牛顿法
拟牛顿法BFGS
内点法
投影梯度法
应用领域
机器学习训练
SVM支持向量机
信号处理
运筹与控制
金融量化
一个标准优化问题可以写成:
min x ∈ R n f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p \begin{aligned}
\min_{x \in \mathbb{R}^n} \quad & f(x) \\
\text{s.t.} \quad & g_i(x) \leq 0, \quad i = 1, \dots, m \\
& h_j(x) = 0, \quad j = 1, \dots, p
\end{aligned}
x ∈ R n min s.t. f ( x ) g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p
其中 f ( x ) f(x)f ( x ) 是目标函数,g i ( x ) g_i(x)g i ( x ) 是不等式约束,h j ( x ) h_j(x)h j ( x ) 是等式约束。x ∈ R n x \in \mathbb{R}^nx ∈ R n 是决策变量。求解优化问题的目标是在满足所有约束的前提下,找到使 f ( x ) f(x)f ( x ) 最小的 x xx 。
优化问题可按多个维度分类,分类方式直接影响算法的选择:
分类维度
类型
典型特征
举例
有/无约束
无约束优化
无 g i , h j g_i, h_jg i , h j
最小二乘回归、神经网络训练
约束优化
存在约束条件
SVM、线性规划、工程设计
目标函数
线性规划
f ff 为线性
运输问题、生产计划
二次规划
f ff 为二次
带正则化的回归、SVM 原始问题
非线性规划
f ff 为一般非线性
神经网络训练、参数估计
锥规划
约束为锥
半定规划(SDP)
凸性
凸优化
f ff 和可行域均为凸
Logistic 回归、线性/二次规划
非凸优化
存在多个局部极值
深度神经网络、混合整数规划
变量类型
连续优化
变量连续
绝大多数机器学习问题
离散优化
变量整数
组合优化、图问题、调度问题
混合整数优化
混合变量
供应链优化、设施选址
变量维度
小规模
n < 10 3 n < 10^3n < 1 0 3
经典回归、SVM
中等规模
10 3 ≤ n < 10 5 10^3 \leq n < 10^51 0 3 ≤ n < 1 0 5
Lasso、逻辑回归
大规模
n ≥ 10 5 n \geq 10^5n ≥ 1 0 5
深度学习、推荐系统
以下是优化理论的发展脉络,展示了从古典方法到现代 AI 优化的演进路径:
timeline
title 优化理论发展历史
17-19世纪 : 牛顿法(Newton, 1669)
: 最小二乘法(Gauss, 1795)
: 变分法(Euler, Lagrange)
20世纪上半 : 线性规划(Dantzig, 1947)
: 单纯形法
: Kuhn-Tucker 条件(1951)
20世纪下半 : 内点法(Karmarkar, 1984)
: 拟牛顿法 BFGS(1970s)
: 约束优化序列二次规划
21世纪初 : 凸优化系统化(Boyd, 2004)
: SGD 广泛使用(Bottou, 1998-2010)
: ADMM(Boyd et al., 2011)
2010年代 : Adam 优化器(Kingma, 2014)
: 深度学习优化浪潮
: 联邦优化
2020年代 : 大模型分布式优化
: ZerO/优化器状态分片
: 混合精度训练优化
凸优化是优化理论中最重要且研究最透彻的分支。如果一个优化问题是凸的,那么它的任何局部最优解都是全局最优解——这一性质在实际应用中极为宝贵,使得凸优化问题可以高效、可靠地求解。
凸集 :一个集合 C CC 是凸的,如果对于任意 x , y ∈ C x, y \in Cx , y ∈ C 和 θ ∈ [ 0 , 1 ] \theta \in [0, 1]θ ∈ [ 0 , 1 ] ,有:
θ x + ( 1 − θ ) y ∈ C \theta x + (1 - \theta) y \in C
θ x + ( 1 − θ ) y ∈ C
直观理解:凸集中任意两点的连线都完全落在该集合内部。正方形、圆、欧几里得空间等都是凸集;而环形、空心圆则不是凸集。
凸函数 :函数 f ff 是凸的,如果其定义域是凸集,且对任意 x , y x, yx , y 和 θ ∈ [ 0 , 1 ] \theta \in [0, 1]θ ∈ [ 0 , 1 ] :
f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) f(y)
f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y )
几何含义:函数图像上任意两点的连线都位于函数图像之上。对于凸函数,其一阶条件是:
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) , ∀ x , y f(y) \geq f(x) + \nabla f(x)^T (y - x), \quad \forall x, y
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) , ∀ x , y
即凸函数的图像始终位于其切线/切平面之上。这个性质在优化中至关重要——它意味着局部梯度信息可以给出全局下界。
以 f ( x ) = x 2 f(x) = x^2f ( x ) = x 2 为例,验证凸性定义:
x xx
y yy
θ \thetaθ
θ x + ( 1 − θ ) y \theta x + (1-\theta)yθ x + ( 1 − θ ) y
f ( θ x + ( 1 − θ ) y ) f(\theta x + (1-\theta)y)f ( θ x + ( 1 − θ ) y )
θ f ( x ) + ( 1 − θ ) f ( y ) \theta f(x) + (1-\theta)f(y)θ f ( x ) + ( 1 − θ ) f ( y )
是否满足
1
3
0.5
2
4
(0.5)(1)+(0.5)(9)=5
✅
1
3
0.2
1.4
1.96
(0.2)(1)+(0.8)(9)=7.4
✅
0
5
0.3
1.5
2.25
(0.3)(0)+(0.7)(25)=17.5
✅
可以看到 f ( θ x + ( 1 − θ ) y ) f(\theta x + (1-\theta)y)f ( θ x + ( 1 − θ ) y ) 始终小于或等于 θ f ( x ) + ( 1 − θ ) f ( y ) \theta f(x)+(1-\theta)f(y)θ f ( x ) + ( 1 − θ ) f ( y ) ,验证了 x 2 x^2x 2 是凸函数。
对于二次可微函数,凸性等价于 Hessian 矩阵 ∇ 2 f ( x ) \nabla^2 f(x)∇ 2 f ( x ) 半正定(对所有 x xx )。对于 f ( x 1 , x 2 ) = x 1 2 + 2 x 2 2 − x 1 x 2 f(x_1, x_2) = x_1^2 + 2x_2^2 - x_1x_2f ( x 1 , x 2 ) = x 1 2 + 2 x 2 2 − x 1 x 2 :
∇ 2 f = [ 2 − 1 − 1 4 ] \nabla^2 f = \begin{bmatrix} 2 & -1 \\ -1 & 4 \end{bmatrix}
∇ 2 f = [ 2 − 1 − 1 4 ]
其特征值为 λ 1 = 3 + 2 ≈ 4.41 > 0 \lambda_1 = 3 + \sqrt{2} \approx 4.41 > 0λ 1 = 3 + 2 ≈ 4.41 > 0 ,λ 2 = 3 − 2 ≈ 1.59 > 0 \lambda_2 = 3 - \sqrt{2} \approx 1.59 > 0λ 2 = 3 − 2 ≈ 1.59 > 0 ,所以 f ff 是凸函数。从初始点 x 0 = ( 10 , − 8 ) x_0 = (10, -8)x 0 = ( 10 , − 8 ) 开始梯度下降:
迭代
x xx
f ( x ) f(x)f ( x )
0
(10.00, -8.00)
356.00
1
(5.56, -1.78)
49.63
2
(3.09, 0.16)
13.68
3
(1.72, 1.16)
5.63
4
(0.95, 1.60)
3.19
...
...
...
10
(0.01, 1.99)
2.00
无论从何处出发,都稳定收敛到全局最小值。这正是凸优化在机器学习中如此重要的原因。
函数
表达式
定义域
凸性依据
线性函数
f ( x ) = a T x + b f(x) = a^T x + bf ( x ) = a T x + b
R n \mathbb{R}^nR n
Hessian 为零矩阵(既是凸也是凹)
二次凸函数
f ( x ) = x T Q x f(x) = x^T Q xf ( x ) = x T Q x (Q QQ 半正定)
R n \mathbb{R}^nR n
Hessian = 2 Q ⪰ 0 = 2Q \succeq 0= 2 Q ⪰ 0
绝对值
f ( x ) = ∥ x ∥ f(x) = \|x\|f ( x ) = ∥ x ∥
R n \mathbb{R}^nR n
范数公理保证凸性
负对数
f ( x ) = − log x f(x) = -\log xf ( x ) = − log x
( 0 , ∞ ) (0, \infty)( 0 , ∞ )
二阶导 = 1 / x 2 > 0 = 1/x^2 > 0= 1/ x 2 > 0
指数函数
f ( x ) = e a x f(x) = e^{ax}f ( x ) = e a x
R \mathbb{R}R
二阶导 = a 2 e a x > 0 = a^2 e^{ax} > 0= a 2 e a x > 0
负熵
f ( x ) = x log x f(x) = x \log xf ( x ) = x log x
( 0 , ∞ ) (0, \infty)( 0 , ∞ )
二阶导 = 1 / x > 0 = 1/x > 0= 1/ x > 0
最大分量
f ( x ) = max { x 1 , … , x n } f(x) = \max\{x_1, \dots, x_n\}f ( x ) = max { x 1 , … , x n }
R n \mathbb{R}^nR n
凸函数逐点上确界保持凸性
范数平方
f ( x ) = ∥ x ∥ 2 f(x) = \|x\|^2f ( x ) = ∥ x ∥ 2
R n \mathbb{R}^nR n
等价于 x T I x x^T I xx T I x ,I II 正定
具体数值例子 :考虑最小化 f ( x ) = ( x − 3 ) 2 + 1 f(x) = (x - 3)^2 + 1f ( x ) = ( x − 3 ) 2 + 1 ,这是一个凸函数(二次函数,系数为正)。通过求导得到全局最小值 x ∗ = 3 , f ( x ∗ ) = 1 x^* = 3, f(x^*) = 1x ∗ = 3 , f ( x ∗ ) = 1 。
如果用梯度下降法从任意初始点开始(比如 x 0 = 0 x_0 = 0x 0 = 0 ),每一步都会朝着全局最小值移动,永远不会陷入局部陷阱。相比之下,如果是非凸函数 g ( x ) = sin ( x ) + 0.1 x 2 g(x) = \sin(x) + 0.1x^2g ( x ) = sin ( x ) + 0.1 x 2 ,从不同初始值出发会收敛到不同的局部极值:
初始点 x 0 x_0x 0
收敛点(约)
函数值(约)
类型
0.0
4.5
-0.87
局部极小
2.0
4.5
-0.87
同一局部极小
6.0
7.9
1.30
另一局部极小
8.0
10.9
-0.59
全局极小(约)
-2.0
-1.9
0.38
局部极小
这就是为什么深度学习训练中,初始化策略如此重要——非凸问题收敛到何处完全取决于初始位置。随机初始化、预训练、学习率 warmup 等技巧的设计初衷就是为了不陷入差的局部极小值。
深度学习中的损失函数几乎总是高度非凸的。以下是非凸优化的主要挑战和对应的缓解策略:
graph TD
A[非凸优化挑战] --> B[局部极小值]
A --> C[鞍点]
A --> D[平坦区域]
A --> E[梯度消失/爆炸]
B --> B1[多起始点随机初始化]
B --> B2[模拟退火/扰动]
C --> C1[高阶方法: 牛顿法]
C --> C2[动量法跨越鞍点]
D --> D1[学习率调度]
D --> D2[梯度裁剪]
E --> E1[残差连接]
E --> E2[归一化层]
E --> E3[梯度裁剪]
style A fill:#f9f,stroke:#333
style B fill:#fdd,stroke:#333
style C fill:#dfd,stroke:#333
style D fill:#ddf,stroke:#333
style E fill:#fdf,stroke:#333
函数
公式
极小值点数量
全局最小值
f ( x ) = x 2 f(x) = x^2f ( x ) = x 2
二次凸
1
x = 0 x=0x = 0
f ( x ) = sin ( x ) + 0.1 x 2 f(x) = \sin(x) + 0.1x^2f ( x ) = sin ( x ) + 0.1 x 2
非凸
约 6 个
取决于区间范围
Rosenbrock 函数
非凸
1(在狭窄山谷中)
x = ( 1 , 1 ) x=(1,1)x = ( 1 , 1 )
Rastrigin 函数
高度非凸
与维数指数相关
x = 0 x=0x = 0
Ackley 函数
高度非凸
大量局部极小
x = 0 x=0x = 0
ResNet-56 损失景观
极度复杂
不可计数
依赖训练策略
拉格朗日对偶性(Lagrange Duality)是处理约束优化问题的核心方法。它的基本思路是将约束条件"吸收"到目标函数中,从而将约束优化转化为无约束优化。
对于原始问题:
min x f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p \begin{aligned}
\min_x \quad & f(x) \\
\text{s.t.} \quad & g_i(x) \leq 0, \quad i = 1, \dots, m \\
& h_j(x) = 0, \quad j = 1, \dots, p
\end{aligned}
x min s.t. f ( x ) g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p
定义拉格朗日函数(Lagrangian):
L ( x , λ , ν ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ j = 1 p ν j h j ( x ) L(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \nu_j h_j(x)
L ( x , λ , ν ) = f ( x ) + i = 1 ∑ m λ i g i ( x ) + j = 1 ∑ p ν j h j ( x )
其中 λ i ≥ 0 \lambda_i \geq 0λ i ≥ 0 是不等式约束对应的拉格朗日乘子,ν j ∈ R \nu_j \in \mathbb{R}ν j ∈ R 是等式约束对应的乘子。
对偶函数定义为拉格朗日函数关于原始变量 x xx 的下确界:
g ( λ , ν ) = inf x L ( x , λ , ν ) g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu)
g ( λ , ν ) = x inf L ( x , λ , ν )
关键性质 :对偶函数是凹的,且对任意 λ ≥ 0 \lambda \geq 0λ ≥ 0 和 ν \nuν ,给出原始最优值 p ∗ p^*p ∗ 的下界:
g ( λ , ν ) ≤ p ∗ g(\lambda, \nu) \leq p^*
g ( λ , ν ) ≤ p ∗
graph LR
subgraph 原始问题
P[原始问题] --> |定义| L[拉格朗日函数 Lxλν]
P --> PF[原始最优值 p*]
end
subgraph 对偶问题
L --> |对x求下确界| D[对偶函数 gλν]
D --> |最大化| DP[对偶问题]
DP --> DF[对偶最优值 d*]
end
P --> |弱对偶性| WEAK[d* ≤ p*]
P --> |强对偶性| STRONG[d* = p*]
WEAK --> GAP[对偶间隙 p*-d*]
为了获得最好的下界,我们需要求解对偶问题:
max λ , ν g ( λ , ν ) s.t. λ ≥ 0 \begin{aligned}
\max_{\lambda, \nu} \quad & g(\lambda, \nu) \\
\text{s.t.} \quad & \lambda \geq 0
\end{aligned}
λ , ν max s.t. g ( λ , ν ) λ ≥ 0
设对偶问题的最优值为 d ∗ d^*d ∗ ,则总有 d ∗ ≤ p ∗ d^* \leq p^*d ∗ ≤ p ∗ 。这一性质称为弱对偶性 (Weak Duality)。p ∗ − d ∗ p^* - d^*p ∗ − d ∗ 称为对偶间隙。
如果 d ∗ = p ∗ d^* = p^*d ∗ = p ∗ ,则称为强对偶性 (Strong Duality)成立。
考虑一个非凸优化问题,它的对偶间隙可能很大:
min x ∈ [ 0 , 1 ] f ( x ) = 2 x − x 2 \min_{x \in [0, 1]} f(x) = 2x - x^2
x ∈ [ 0 , 1 ] min f ( x ) = 2 x − x 2
f ff 是凹函数(二阶导数为负)。其原始最优解 p ∗ p^*p ∗ :
f ′ ( x ) = 2 − 2 x = 0 ⇒ x = 1 f'(x) = 2 - 2x = 0 \Rightarrow x = 1f ′ ( x ) = 2 − 2 x = 0 ⇒ x = 1 (边界)
f ( 0 ) = 0 , f ( 1 ) = 1 f(0) = 0, f(1) = 1f ( 0 ) = 0 , f ( 1 ) = 1 ,所以 p ∗ = 0 p^* = 0p ∗ = 0 (最小值在 x = 0 x=0x = 0 )
对偶函数比较复杂。实际上对于非凸问题,对偶间隙大多为正。下表展示不同情况下的对偶性表现:
问题类型
p ∗ p^*p ∗
d ∗ d^*d ∗
对偶间隙
强对偶性是否成立
凸+Slater成立
可精确求解
= p ∗ =p^*= p ∗
0
✅
凸+Slater不满足
可精确求解
≤ p ∗ \leq p^*≤ p ∗
≥ 0 \geq 0≥ 0
❌ 可能不成立
非凸(一般)
难求解
≤ p ∗ \leq p^*≤ p ∗
≥ 0 \geq 0≥ 0
❌
非凸(某些特殊)
难求解
≤ p ∗ \leq p^*≤ p ∗
≥ 0 \geq 0≥ 0
❌(但可能存在对偶嵌入)
强对偶性成立的条件称为约束规范性。最重要的条件是 Slater 条件 :存在一个严格可行点 x xx ,使得所有不等式约束严格成立,即 g i ( x ) < 0 g_i(x) < 0g i ( x ) < 0 。对于凸优化问题,Slater 条件保证强对偶性成立。
KKT 条件(Karush-Kuhn-Tucker 条件)是最优解的必要条件(在凸优化中也是充分条件)。它通过一组方程和不等式来刻画最优解的特征。
flowchart TD
A[KKT 条件] --> B[稳定性条件]
A --> C[原始可行性]
A --> D[对偶可行性]
A --> E[互补松弛性]
B --> B1[梯度为零: 目标+约束的加权梯度之和=0]
C --> C1[约束必须被满足: gix≤0, hjx=0]
D --> D1[拉格朗日乘子非负: λi≥0]
E --> E1[活性约束: λi gix = 0, 要么λi=0要么gix=0]
style A fill:#eef,stroke:#339
style B fill:#efe,stroke:#393
style C fill:#fee,stroke:#933
style D fill:#eef,stroke:#33e
style E fill:#fef,stroke:#939
假设 f , g i , h j f, g_i, h_jf , g i , h j 可微,则最优解 x ∗ x^*x ∗ 处的 KKT 条件为:
稳定性条件 (Stationarity):
∇ f ( x ∗ ) + ∑ i = 1 m λ i ∗ ∇ g i ( x ∗ ) + ∑ j = 1 p ν j ∗ ∇ h j ( x ∗ ) = 0 \nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(x^*) = 0
∇ f ( x ∗ ) + i = 1 ∑ m λ i ∗ ∇ g i ( x ∗ ) + j = 1 ∑ p ν j ∗ ∇ h j ( x ∗ ) = 0
原始可行性 (Primal Feasibility):
g i ( x ∗ ) ≤ 0 , h j ( x ∗ ) = 0 g_i(x^*) \leq 0, \quad h_j(x^*) = 0
g i ( x ∗ ) ≤ 0 , h j ( x ∗ ) = 0
对偶可行性 (Dual Feasibility):
λ i ∗ ≥ 0 \lambda_i^* \geq 0
λ i ∗ ≥ 0
互补松弛性 (Complementary Slackness):
λ i ∗ g i ( x ∗ ) = 0 \lambda_i^* g_i(x^*) = 0
λ i ∗ g i ( x ∗ ) = 0
互补松弛性尤其值得深入理解:它意味着如果第 i ii 个不等式约束在最优解处是"松弛的"(即 g i ( x ∗ ) < 0 g_i(x^*) < 0g i ( x ∗ ) < 0 ),则对应的拉格朗日乘子 λ i ∗ = 0 \lambda_i^* = 0λ i ∗ = 0 ;反之,如果 λ i ∗ > 0 \lambda_i^* > 0λ i ∗ > 0 ,则该约束是"紧的"(g i ( x ∗ ) = 0 g_i(x^*) = 0g i ( x ∗ ) = 0 )。换句话说,只有那些在最优解处起作用的约束才被"定价"。
通过一个完整的数值例子来展示 KKT 条件的应用。
问题 :
min x 1 , x 2 f ( x ) = x 1 2 + x 2 2 s.t. x 1 + x 2 − 1 ≤ 0 \begin{aligned}
\min_{x_1, x_2} \quad & f(x) = x_1^2 + x_2^2 \\
\text{s.t.} \quad & x_1 + x_2 - 1 \leq 0
\end{aligned}
x 1 , x 2 min s.t. f ( x ) = x 1 2 + x 2 2 x 1 + x 2 − 1 ≤ 0
求解过程 :
步骤 1 :构造拉格朗日函数。
L ( x , λ ) = x 1 2 + x 2 2 + λ ( x 1 + x 2 − 1 ) L(x, \lambda) = x_1^2 + x_2^2 + \lambda(x_1 + x_2 - 1)
L ( x , λ ) = x 1 2 + x 2 2 + λ ( x 1 + x 2 − 1 )
步骤 2 :稳定性条件对 x 1 , x 2 x_1, x_2x 1 , x 2 求偏导。
∂ L ∂ x 1 = 2 x 1 + λ = 0 ⇒ x 1 = − λ 2 \frac{\partial L}{\partial x_1} = 2x_1 + \lambda = 0 \Rightarrow x_1 = -\frac{\lambda}{2}
∂ x 1 ∂ L = 2 x 1 + λ = 0 ⇒ x 1 = − 2 λ
∂ L ∂ x 2 = 2 x 2 + λ = 0 ⇒ x 2 = − λ 2 \frac{\partial L}{\partial x_2} = 2x_2 + \lambda = 0 \Rightarrow x_2 = -\frac{\lambda}{2}
∂ x 2 ∂ L = 2 x 2 + λ = 0 ⇒ x 2 = − 2 λ
步骤 3 :应用互补松弛性。
如果 λ = 0 \lambda = 0λ = 0 ,则 x 1 = x 2 = 0 x_1 = x_2 = 0x 1 = x 2 = 0 ,此时 x 1 + x 2 − 1 = − 1 < 0 x_1 + x_2 - 1 = -1 < 0x 1 + x 2 − 1 = − 1 < 0 ,约束满足,KKT 全部成立。
如果 λ > 0 \lambda > 0λ > 0 ,则 g ( x ) = 0 g(x) = 0g ( x ) = 0 ,即 x 1 + x 2 = 1 x_1 + x_2 = 1x 1 + x 2 = 1 ,代入得 − λ / 2 − λ / 2 = 1 -\lambda/2 - \lambda/2 = 1− λ /2 − λ /2 = 1 ,λ = − 1 \lambda = -1λ = − 1 ,但需要 λ ≥ 0 \lambda \geq 0λ ≥ 0 ,矛盾。
因此最优解为:x 1 ∗ = x 2 ∗ = 0 , λ ∗ = 0 x_1^* = x_2^* = 0, \lambda^* = 0x 1 ∗ = x 2 ∗ = 0 , λ ∗ = 0 ,目标值 f ∗ = 0 f^* = 0f ∗ = 0 。
现在修改约束为等式:x 1 + x 2 − 1 = 0 x_1 + x_2 - 1 = 0x 1 + x 2 − 1 = 0 ,则 x 1 = x 2 = 0.5 , f ∗ = 0.5 x_1 = x_2 = 0.5, f^* = 0.5x 1 = x 2 = 0.5 , f ∗ = 0.5 。对比可见:
约束类型
最优解 ( x 1 , x 2 ) (x_1, x_2)( x 1 , x 2 )
最优值 f ∗ f^*f ∗
约束是否起作用
λ ∗ \lambda^*λ ∗
无约束
( 0 , 0 ) (0, 0)( 0 , 0 )
0
—
—
x 1 + x 2 ≤ 1 x_1 + x_2 \leq 1x 1 + x 2 ≤ 1 (松弛)
( 0 , 0 ) (0, 0)( 0 , 0 )
0
否
0
x 1 + x 2 = 1 x_1 + x_2 = 1x 1 + x 2 = 1 (等式约束)
( 0.5 , 0.5 ) (0.5, 0.5)( 0.5 , 0.5 )
0.5
是
λ = − 1 \lambda = -1λ = − 1 (等式的 ν \nuν 可负)
x 1 + x 2 ≤ 0 x_1 + x_2 \leq 0x 1 + x 2 ≤ 0 (紧)
( 0 , 0 ) (0, 0)( 0 , 0 )
0
是
λ > 0 \lambda > 0λ > 0
支持向量机(SVM)是最经典的 KKT 应用案例。SVM 的原始问题:
min w , b 1 2 ∥ w ∥ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , … , m \min_{w, b} \frac{1}{2} \|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i = 1, \dots, m
w , b min 2 1 ∥ w ∥ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , … , m
互补松弛性 α i [ y i ( w T x i + b ) − 1 ] = 0 \alpha_i [y_i(w^T x_i + b) - 1] = 0α i [ y i ( w T x i + b ) − 1 ] = 0 在这里有深刻的几何含义:
如果样本 x i x_ix i 位于决策边界上(即 y i ( w T x i + b ) = 1 y_i(w^T x_i + b) = 1y i ( w T x i + b ) = 1 ),则该点是支持向量 ,对应的 α i > 0 \alpha_i > 0α i > 0
如果样本 x i x_ix i 远离决策边界(即 y i ( w T x i + b ) > 1 y_i(w^T x_i + b) > 1y i ( w T x i + b ) > 1 ),则 α i = 0 \alpha_i = 0α i = 0 ,该点对决策面没有贡献
这意味着 SVM 的决策面仅由少数"边界点"决定——这与人类直觉一致:最靠近分界线的点决定了分界线在哪里,远离分界线的点可以忽略。
优化理论为实际算法提供了理论基础。以下深入对比最常用的优化算法及其适用场景。
算法
更新规则
收敛速度
每步计算
存储
适用规模
对 Hessian 需求
梯度下降 (GD)
x k + 1 = x k − α ∇ f ( x k ) x_{k+1} = x_k - \alpha \nabla f(x_k)x k + 1 = x k − α ∇ f ( x k )
线性 O ( 1 / ϵ ) O(1/\epsilon)O ( 1/ ϵ )
O ( n ) O(n)O ( n )
O ( n ) O(n)O ( n )
极大
无
随机梯度下降 (SGD)
x k + 1 = x k − α ∇ f i ( x k ) x_{k+1} = x_k - \alpha \nabla f_i(x_k)x k + 1 = x k − α ∇ f i ( x k )
次线性 O ( 1 / ϵ ) O(1/\sqrt{\epsilon})O ( 1/ ϵ )
O ( n ) O(n)O ( n )
O ( n ) O(n)O ( n )
极大(大数据)
无
带动量 SGD
v k + 1 = β v k + ∇ f i ( x k ) v_{k+1} = \beta v_k + \nabla f_i(x_k)v k + 1 = β v k + ∇ f i ( x k )
加速收敛
O ( n ) O(n)O ( n )
O ( n ) O(n)O ( n )
极大
无
牛顿法
x k + 1 = x k − H k − 1 ∇ f ( x k ) x_{k+1} = x_k - H_k^{-1} \nabla f(x_k)x k + 1 = x k − H k − 1 ∇ f ( x k )
二次 O ( log log ( 1 / ϵ ) ) O(\log \log (1/\epsilon))O ( log log ( 1/ ϵ ))
O ( n 3 ) O(n^3)O ( n 3 )
O ( n 2 ) O(n^2)O ( n 2 )
小(n < 10 4 n<10^4n < 1 0 4 )
需 Hessian
拟牛顿 BFGS
近似 Hessian 逆
超线性
O ( n 2 ) O(n^2)O ( n 2 )
O ( n 2 ) O(n^2)O ( n 2 )
中(n < 10 5 n<10^5n < 1 0 5 )
近似
L-BFGS
低秩近似
超线性
O ( n ) O(n)O ( n )
O ( n ) O(n)O ( n )
中-大
近似
共轭梯度
共轭方向
线性的 n nn 步
O ( n ) O(n)O ( n )
O ( n ) O(n)O ( n )
大
无
Adam
自适应学习率
快速实操收敛
O ( n ) O(n)O ( n )
O ( 2 n ) O(2n)O ( 2 n )
极大
无
对于 L LL -光滑的凸函数(即 ∇ f \nabla f∇ f 是 L LL -Lipschitz 连续的),使用步长 α = 1 / L \alpha = 1/Lα = 1/ L 的梯度下降,有:
f ( x k ) − f ( x ∗ ) ≤ L ∥ x 0 − x ∗ ∥ 2 2 k f(x_k) - f(x^*) \leq \frac{L \|x_0 - x^*\|^2}{2k}
f ( x k ) − f ( x ∗ ) ≤ 2 k L ∥ x 0 − x ∗ ∥ 2
这意味着为了达到精度 ϵ \epsilonϵ ,需要 O ( 1 / ϵ ) O(1/\epsilon)O ( 1/ ϵ ) 次迭代。
如果函数还是 μ \muμ -强凸的,则收敛速度更快:
f ( x k ) − f ( x ∗ ) ≤ L 2 ( 1 − μ L ) k ∥ x 0 − x ∗ ∥ 2 f(x_k) - f(x^*) \leq \frac{L}{2} \left(1 - \frac{\mu}{L}\right)^k \|x_0 - x^*\|^2
f ( x k ) − f ( x ∗ ) ≤ 2 L ( 1 − L μ ) k ∥ x 0 − x ∗ ∥ 2
这是线性收敛 ,达到精度 ϵ \epsilonϵ 只需要 O ( log ( 1 / ϵ ) ) O(\log(1/\epsilon))O ( log ( 1/ ϵ )) 次迭代。
考虑 f ( x ) = 1 2 ( x − 5 ) 2 f(x) = \frac{1}{2}(x - 5)^2f ( x ) = 2 1 ( x − 5 ) 2 ,其 L = 1 , μ = 1 L = 1, \mu = 1L = 1 , μ = 1 (因为 ∇ 2 f = 1 \nabla^2 f = 1∇ 2 f = 1 )。
迭代 k kk
GD x k x_kx k
GD f ( x k ) f(x_k)f ( x k )
牛顿 x k x_kx k
牛顿 f ( x k ) f(x_k)f ( x k )
0
0.00
12.500
0.00
12.500
1
5.00
0.000
5.00
0.000
2
5.00
0.000
5.00
0.000
牛顿法一步到达精确解(因为二次函数的 Hessian 是常数)。对一般函数,牛顿法也表现出二次收敛:
迭代次数 k kk
牛顿法精度(一般函数)
梯度下降精度(L = 1 L=1L = 1 )
梯度下降精度(L = 50 L=50L = 50 )
1
10 − 1 10^{-1}1 0 − 1
≈ 0.5 \approx 0.5≈ 0.5
≈ 25 \approx 25≈ 25
2
10 − 3 10^{-3}1 0 − 3
≈ 0.33 \approx 0.33≈ 0.33
≈ 16.7 \approx 16.7≈ 16.7
3
10 − 7 10^{-7}1 0 − 7
≈ 0.25 \approx 0.25≈ 0.25
≈ 12.5 \approx 12.5≈ 12.5
4
10 − 15 10^{-15}1 0 − 15
≈ 0.20 \approx 0.20≈ 0.20
≈ 10.0 \approx 10.0≈ 10.0
10
机器精度
≈ 0.09 \approx 0.09≈ 0.09
≈ 4.5 \approx 4.5≈ 4.5
100
—
≈ 0.01 \approx 0.01≈ 0.01
≈ 0.5 \approx 0.5≈ 0.5
从上表可见,牛顿法收敛速度极快,但代价是每步需要计算 O ( n 3 ) O(n^3)O ( n 3 ) 的 Hessian 逆矩阵。对于 n = 10 6 n=10^6n = 1 0 6 规模的深度学习问题,这是不可行的。这就是为什么深度学习训练几乎只使用一阶方法。
算法
原理
收敛速度
适用约束
典型应用
投影梯度法
GD + 可行域投影
线性
简单凸集(盒子、球、单纯形)
LASSO 的 ℓ 1 \ell_1ℓ 1 球投影
拉格朗日法(UL)
乘子 + 梯度上升
线性到超线性
等式约束
PDE 约束优化
增广拉格朗日法
UL + 二次惩罚
超线性
混合约束
ADMM 框架
内点法(IPM)
障碍函数 + 牛顿步
超线性/二次
不等式约束
LP, QP, SDP
序列二次规划(SQP)
局部 QP 近似
超线性
一般非线性约束
工程优化、轨迹规划
交替方向法(ADMM)
分裂 + 增广拉格朗日
线性
可分结构约束
分布式优化、图像处理
SVM 是最经典的将优化理论应用于机器学习的例子。原始问题:
min w , b 1 2 ∥ w ∥ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , … , m \min_{w, b} \frac{1}{2} \|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1, \quad i = 1, \dots, m
w , b min 2 1 ∥ w ∥ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , … , m
拉格朗日函数:
L ( w , b , α ) = 1 2 ∥ w ∥ 2 − ∑ i = 1 m α i [ y i ( w T x i + b ) − 1 ] L(w, b, \alpha) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^m \alpha_i [y_i(w^T x_i + b) - 1]
L ( w , b , α ) = 2 1 ∥ w ∥ 2 − i = 1 ∑ m α i [ y i ( w T x i + b ) − 1 ]
通过 w , b w, bw , b 的稳定性条件:
∂ L ∂ w = w − ∑ i = 1 m α i y i x i = 0 ⇒ w = ∑ i = 1 m α i y i x i \frac{\partial L}{\partial w} = w - \sum_{i=1}^m \alpha_i y_i x_i = 0 \Rightarrow w = \sum_{i=1}^m \alpha_i y_i x_i
∂ w ∂ L = w − i = 1 ∑ m α i y i x i = 0 ⇒ w = i = 1 ∑ m α i y i x i
∂ L ∂ b = ∑ i = 1 m α i y i = 0 \frac{\partial L}{\partial b} = \sum_{i=1}^m \alpha_i y_i = 0
∂ b ∂ L = i = 1 ∑ m α i y i = 0
代回得到对偶问题:
max α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j \max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j x_i^T x_j
α max i = 1 ∑ m α i − 2 1 i = 1 ∑ m j = 1 ∑ m α i α j y i y j x i T x j
其中 α i ≥ 0 \alpha_i \geq 0α i ≥ 0 。这里的对偶变换使得我们可以引入核函数 K ( x i , x j ) = ϕ ( x i ) T ϕ ( x j ) K(x_i, x_j) = \phi(x_i)^T \phi(x_j)K ( x i , x j ) = ϕ ( x i ) T ϕ ( x j ) ,将 SVM 扩展到非线性分类。
随机梯度下降(SGD)是深度学习训练的核心算法。从优化理论角度看:
无约束优化 :深度学习的损失函数通常不显式包含约束(权重衰减可视为 ℓ 2 \ell_2ℓ 2 正则化,等价于带约束优化)
非凸优化 :神经网络的损失函数高度非凸,存在大量鞍点和局部极小值
拉格朗日视角 :正则化项可以看作拉格朗日乘子。例如,ℓ 2 \ell_2ℓ 2 正则化的损失 L = loss + λ ∥ w ∥ 2 L = \text{loss} + \lambda \|w\|^2L = loss + λ ∥ w ∥ 2 等价于约束 ∥ w ∥ 2 ≤ C \|w\|^2 \leq C∥ w ∥ 2 ≤ C
KKT 条件对理解 SGD 的收敛行为也至关重要。例如,在神经网络的训练中,当损失趋于零时,所有样本对应的约束都变得松弛,这对应着模型在训练集上达到了"插值"状态。
flowchart TD
A[问题规模 n?] --> |n < 10⁴| B[尝试牛顿法/L-BFGS]
A --> |n ≥ 10⁴| C[使用一阶方法]
B --> B1[Hessian可计算?] --> |是| N[牛顿法]
B1 --> |否| Q[拟牛顿BFGS]
C --> D[数据量巨大?]
D --> |是| E[使用SGD及其变体]
D --> |否| F[全批量GD足够]
E --> G[需要自适应学习率?]
G --> |是| H[Adam / AdamW]
G --> |否| I[SGD + Momentum]
H --> J[CV任务?]
J --> |是| K[尝试 SGD+Momentum<br/>有时比Adam更好]
J --> |否| L[NLP/Transformer?]
L --> |是| M[AdamW + 余弦退火]
L --> |否| N[Adam 默认]
style A fill:#f9f,stroke:#333
style H fill:#9ff,stroke:#333
style M fill:#9f9,stroke:#333
优化器
MNIST 收敛速度
ImageNet Top-1
显存开销
超参数敏感性
适用场景
SGD + Momentum
慢
76.3%
低
中等
CV(调参良好时表现最佳)
Adam
快
75.1%
低(2倍动量)
低
NLP、通用默认
AdamW
快
76.2%
低(2倍动量)
低
Transformer、LLM 训练
RMSProp
快
74.8%
低
中低
RNN、强化学习
L-BFGS
中等
—
高
高
小批量非深度学习
数据来源:ImageNet top-1 为 ResNet-50 典型报告值。实际性能取决于具体实现和超参数调优。
定义决策变量 :明确需要优化什么,变量是否连续
确定目标函数 :f ( x ) f(x)f ( x ) 的可微性、凸性、计算成本
识别约束条件 :等式、不等式、隐式约束
问题特性分析 :
凸 → 可直接用经典方法求解(内点法、梯度下降)
非凸 → 需要多起始点、全局搜索策略
大规模 → 需要随机化、分布式计算
带特殊结构 → 可利用结构加速(如 ADMM 用于可分问题)
选择求解算法 :根据上表匹配算法
实现与调试 :监视收敛曲线、梯度范数、对偶间隙
陷阱
现象
原因
解决方法
学习率过大
损失震荡或发散
步长超过 Lipschitz 常数
降低学习率,使用学习率调度
学习率过小
收敛极其缓慢
步长太小
学习率 warmup,或使用自适应方法
梯度消失
损失不下降
链式法则导致梯度趋零
残差连接、归一化层、梯度裁剪
梯度爆炸
损失变为 NaN
梯度指数增长
梯度裁剪、降低学习率
鞍点停滞
损失 plateau
梯度为零但非极值
动量法、随机扰动
过拟合
训练好测试差
模型复杂度过高
正则化、早停、数据增强
KKT 不满足
解不是最优
收敛到非最优临界点
检查稳定性条件、尝试不同初始值
概念
对机器学习的意义
凸性
保证全局最优,解释为什么一些模型(如 LR、SVM)训练稳定
拉格朗日对偶
引入核方法(SVM)、推导对偶形式的优化问题
KKT 条件
理解支持向量、正则化的对偶解释、互补松弛的直观
强对偶性
保证对偶问题的解和原始问题的解一致
Lipschitz 光滑
指导学习率选择,影响收敛速度分析
强凸性
保证线性收敛,解释正则化带来的优化稳定性
对偶间隙
衡量非凸问题求解质量的指标
优化理论为机器学习和 AI 提供了坚实的数学基础。凸优化保证了全局最优解的可达性;拉格朗日对偶性提供了处理约束的优雅方法并引入了核技巧;KKT 条件给出了最优解的完整刻画。理解这些核心概念后,再去看随机梯度下降(SGD)、Adam 等优化算法时,就会明白它们背后的理论支撑——每一步更新都是在向满足最优性条件的方向逼近。
在实际研究中,优化理论的工具不仅在训练中使用,还广泛应用于模型分析、正则化设计、超参数调优、神经网络架构搜索等各个领域。掌握优化理论是深入理解机器学习不可或缺的一步。
对于初学者,建议按以下顺序学习优化理论:
基础 :微积分(梯度、Hessian)、线性代数(矩阵、特征值)
核心 :凸集与凸函数 → 无约束优化(梯度下降) → 约束优化(拉格朗日) → KKT 条件
进阶 :对偶理论、内点法、ADMM
应用 :SVM 推导、深度学习优化器、强化学习策略梯度
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization . Cambridge University Press. — 优化理论的标准教科书,免费在线版
Nocedal, J., & Wright, S. (2006). Numerical Optimization . Springer. — 数值优化的权威参考
Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization methods for large-scale machine learning. SIAM Review , 60(2), 223–311.
Kingma, D. P., & Ba, J. (2014). Adam: A Method for Stochastic Optimization. arXiv:1412.6980 .
更多内容:线性代数基础 | 微积分 | 损失函数 | SVM 支持向量机