最优化 (Optimization)是数学中的一个核心分支,研究如何在给定的约束条件下,从所有可行方案中找到使某个目标函数取极值(极大值或极小值)的最优解。最优化理论与算法广泛存在于工程设计、经济决策、机器学习、运筹管理、信号处理等几乎所有科学技术领域中。
一个标准的最优化问题可以表述为:
min x ∈ D f ( x ) s.t. g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p \begin{aligned}
\min_{x \in \mathcal{D}} \quad & f(x) \\
\text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, \dots, m \\
& h_j(x) = 0, \quad j = 1, \dots, p
\end{aligned}
x ∈ D min s.t. f ( x ) g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p
其中 x xx 是决策变量(向量),f ( x ) f(x)f ( x ) 是目标函数,g i ( x ) ≤ 0 g_i(x) \le 0g i ( x ) ≤ 0 是不等式约束,h j ( x ) = 0 h_j(x) = 0h j ( x ) = 0 是等式约束,D \mathcal{D}D 是定义域。若 D = R n \mathcal{D} = \mathbb{R}^nD = R n 且没有任何约束,则称为无约束优化 。
根据目标函数和约束的性质,最优化可以划分为多个重要子领域。
最优化思想的萌芽可以追溯到古希腊时代。欧几里得的几何原本中已经包含了等周问题——在给定周长的所有平面图形中,圆面积最大。17 世纪,费马提出了无约束极值的必要条件(费马定理),为微分法求解优化问题奠定了基础。
近代最优化理论的发展里程碑包括:
时期
代表人物
贡献
17 世纪
费马、牛顿、莱布尼茨
微分法求解极值
18-19 世纪
拉格朗日、柯西
拉格朗日乘子法、最速下降法
20 世纪初
Karush、Kuhn、Tucker
KKT 必要条件
1940s
Dantzig
单纯形法(线性规划求解)
1950s
Bellman
动态规划
1950s
Pontryagin
最大值原理(最优控制)
1950s
Zoutendijk
可行方向法
1980s
Karmarkar
内点法(多项式时间 LP 求解)
1990s
Boyd, Vandenberghe
凸优化系统化
2000s-今
多位学者
分布式优化、随机优化、深度学习优化
Dantzig 于 1947 年提出的单纯形法被认为是运筹学的诞生标志。单纯形法虽然最坏情况是指数时间,但实践中性能优异,至今仍是线性规划的主力算法。1984 年,Karmarkar 提出的内点法首次证明了线性规划可以在多项式时间内求解,引发了优化算法理论的革命。
timeline
title 最优化发展时间线
17世纪 : 费马提出极值必要条件
: 牛顿发明牛顿法
18世纪 : 拉格朗日乘子法
19世纪 : 柯西最速下降法
1940s : Dantzig提出单纯形法
: 线性规划诞生
1950s : Bellman动态规划
: Pontryagin最大值原理
1980s : Karmarkar内点法
1990s : 凸优化系统化
2000s : 分布式与随机优化兴起
线性规划 (Linear Programming, LP)是目标函数和约束条件均为仿射函数(线性函数 + 常数项)的最优化问题。它是运筹学中最成熟、应用最广泛的分支之一。
标准形式如下:
min x c T x s.t. A x = b , x ≥ 0 \min_{x} \quad c^T x \quad \text{s.t.} \quad Ax = b, \; x \ge 0
x min c T x s.t. A x = b , x ≥ 0
其中 c ∈ R n c \in \mathbb{R}^nc ∈ R n 是成本向量,A ∈ R m × n A \in \mathbb{R}^{m \times n}A ∈ R m × n 是约束矩阵,b ∈ R m b \in \mathbb{R}^mb ∈ R m 是右端向量。
数值例子 :一家工厂生产产品 A 和 B。产品 A 每件利润 40 元,产品 B 每件利润 30 元。生产 A 需要 2 小时机器工时和 1 小时人工,生产 B 需要 1 小时机器工时和 2 小时人工。每天可用机器工时为 100 小时,人工为 80 小时。问如何安排生产使利润最大?
该问题的 LP 模型为:
max 40 x 1 + 30 x 2 s.t. 2 x 1 + x 2 ≤ 100 , x 1 + 2 x 2 ≤ 80 , x 1 , x 2 ≥ 0 \max 40x_1 + 30x_2 \\
\text{s.t.} \quad 2x_1 + x_2 \le 100, \; x_1 + 2x_2 \le 80, \; x_1, x_2 \ge 0
max 40 x 1 + 30 x 2 s.t. 2 x 1 + x 2 ≤ 100 , x 1 + 2 x 2 ≤ 80 , x 1 , x 2 ≥ 0
最优解为 x 1 = 40 , x 2 = 20 x_1 = 40, x_2 = 20x 1 = 40 , x 2 = 20 ,最大利润为 40 × 40 + 30 × 20 = 2200 40 \times 40 + 30 \times 20 = 220040 × 40 + 30 × 20 = 2200 元。这个问题的两个约束在最优解处都是紧约束(等号成立),所以机器和人工的产能都被充分利用。
每个线性规划问题都有一个对应的对偶问题 。原始问题和对偶问题之间有密切的联系:
若原始问题是极小化问题,则对偶问题是极大化问题
弱对偶定理 :对偶问题的目标值 ≤ \le≤ 原始问题的目标值
强对偶定理 :若原始问题有最优解,则对偶问题也有最优解,且目标值相等
互补松弛条件 :原始变量和对偶变量不能同时为正,除非对应的约束是紧的
对偶理论在线性规划的敏感性分析、分解算法中发挥着重要作用。对偶变量的经济解释是"影子价格"——它度量了放宽一个单位约束资源所带来的边际收益。
补充说明 :在上述生产问题中,若对两个约束(机器工时和人工)分别引入对偶变量 y 1 , y 2 y_1, y_2y 1 , y 2 ,则对偶问题为:
min 100 y 1 + 80 y 2 s.t. 2 y 1 + y 2 ≥ 40 , y 1 + 2 y 2 ≥ 30 , y 1 , y 2 ≥ 0 \min 100y_1 + 80y_2 \\
\text{s.t.} \quad 2y_1 + y_2 \ge 40, \; y_1 + 2y_2 \ge 30, \; y_1, y_2 \ge 0
min 100 y 1 + 80 y 2 s.t. 2 y 1 + y 2 ≥ 40 , y 1 + 2 y 2 ≥ 30 , y 1 , y 2 ≥ 0
最优对偶解为 y 1 = 16.67 , y 2 = 6.67 y_1 = 16.67, y_2 = 6.67y 1 = 16.67 , y 2 = 6.67 ,这意味着额外增加 1 小时机器工时可产生 16.67 元利润增量,增加 1 小时人工可产生 6.67 元利润增量——这对资源投资决策至关重要。
算法
最坏情况复杂度
平均/实践复杂度
适用场景
单纯形法 (Simplex)
O ( 2 n ) O(2^n)O ( 2 n )
多项式(约 O ( m + n ) O(m+n)O ( m + n ) 次迭代)
中小规模,稀疏矩阵,极度稳健
内点法 (Interior Point)
O ( n 3 log ( 1 / ε ) ) O(n^3 \log(1/\varepsilon))O ( n 3 log ( 1/ ε ))
O ( n 3 log ( 1 / ε ) ) O(n^3 \log(1/\varepsilon))O ( n 3 log ( 1/ ε ))
大规模问题(>10000 变量)
椭球法 (Ellipsoid)
O ( n 4 L ) O(n^4 L)O ( n 4 L )
O ( n 4 L ) O(n^4 L)O ( n 4 L )
理论重要,实际效率低
网络单纯形法
多项式
线性
网络流问题(运输、分配)
生产计划与资源调度 :石油炼制厂的原油混合方案,不同等级的原油按不同比例调和,满足产品质量指标的同时最小化成本
运输与物流路径优化 :沃尔玛的配送中心选址和车辆调度,每天优化数千辆卡车的路线
资产组合配置 :Markowitz 均值-方差模型,在给定风险水平下最大化预期收益
企业供应链管理 :库存水平与订单量的协同优化
广告投放预算分配 :在多个渠道中分配预算,使总转化率最大
在实际工程中使用 LP,大部分情况并不需要自己实现求解器。推荐使用成熟的求解器库:
商用求解器 :Gurobi、CPLEX(学术免费,性能极强)
开源求解器 :HiGHS、GLPK、SCIP
Python 接口 :scipy.optimize.linprog(内点法 + 单纯形法可选)、PuLP(建模语言式)
一个常见坑点:原始-对偶严格可行内点法的收敛性很大程度取决于问题的数值条件。当约束矩阵 A AA 近似奇异时,Cholesky 分解中的主元可能接近零,导致求解失败。此时需要做预处理 ——消去冗余约束、对列做尺度归一化。
graph TD
A[实际问题] --> B[建立LP模型]
B --> C{问题规模}
C -->|小型| D[单纯形法]
C -->|中型| E[单纯形法或内点法]
C -->|大型| F[内点法]
D --> G[检查对偶间隙]
E --> G
F --> G
G -->|可接受| H[输出最优解]
G -->|过大| I[检查模型/预处理]
I --> C
style A fill:#e1f5fe
style H fill:#c8e6c9
style G fill:#fff9c4
凸优化 (Convex Optimization)是目标函数为凸函数、可行集为凸集的最优化问题。凸优化的核心魅力在于:任何局部最优解都是全局最优解 。这一性质使得凸优化在理论上优雅、在实践中高效。
凸集 :对于集合 C CC 中任意两点 x , y x, yx , y 和 θ ∈ [ 0 , 1 ] \theta \in [0, 1]θ ∈ [ 0 , 1 ] ,有 θ x + ( 1 − θ ) y ∈ C \theta x + (1 - \theta) y \in Cθ x + ( 1 − θ ) y ∈ C 。
直观理解:凸集就像没有凹陷的形状。圆、三角形、多边形都是凸集,而星形、新月形不是凸集。
凸函数 :对于凸集定义域内的任意 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) \le \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 ) f(y) \ge f(x) + \nabla f(x)^T (y - x)f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) ,即切线永远是函数的下界。
数值例子 :函数 f ( x ) = x 2 f(x) = x^2f ( x ) = x 2 是凸函数。取 x = − 2 , y = 2 , θ = 0.5 x = -2, y = 2, \theta = 0.5x = − 2 , y = 2 , θ = 0.5 :
左端 f ( 0.5 × ( − 2 ) + 0.5 × 2 ) = f ( 0 ) = 0 f(0.5 \times (-2) + 0.5 \times 2) = f(0) = 0f ( 0.5 × ( − 2 ) + 0.5 × 2 ) = f ( 0 ) = 0
右端 0.5 × f ( − 2 ) + 0.5 × f ( 2 ) = 0.5 × 4 + 0.5 × 4 = 4 0.5 \times f(-2) + 0.5 \times f(2) = 0.5 \times 4 + 0.5 \times 4 = 40.5 × f ( − 2 ) + 0.5 × f ( 2 ) = 0.5 × 4 + 0.5 × 4 = 4
由于 0 ≤ 4 0 \le 40 ≤ 4 ,凸函数定义成立。而 f ( x ) = sin x f(x) = \sin xf ( x ) = sin x 不是凸函数,例如取 x = 0 , y = π , θ = 0.5 x = 0, y = \pi, \theta = 0.5x = 0 , y = π , θ = 0.5 ,左端为 0 00 ,右端也为 0 00 ,但取 x = π / 2 , y = 3 π / 2 , θ = 0.5 x = \pi/2, y = 3\pi/2, \theta = 0.5x = π /2 , y = 3 π /2 , θ = 0.5 就会违反凸性。
graph TD
subgraph 凸优化
direction TB
A[凸优化问题]
A --> B[LP 线性规划]
A --> C[QP 二次规划]
A --> D[SOCP 二阶锥规划]
A --> E[SDP 半定规划]
A --> F[GP 几何规划]
B --> B1[单纯形法]
B --> B2[内点法]
C --> C1[有效集法]
C --> C2[内点法]
D --> D1[锥求解器 ECOS/SCS]
E --> E1[内点法 MOSEK/SeDuMi]
F --> F2[转换为凸形式]
end
style A fill:#e3f2fd,stroke:#1565c0
Karush–Kuhn–Tucker(KKT)条件是最优性条件的推广。对于凸优化问题,KKT 条件是充分必要条件:
稳定性 :∇ f ( x ∗ ) + ∑ i λ i ∇ g i ( x ∗ ) + ∑ j ν j ∇ h j ( x ∗ ) = 0 \nabla f(x^*) + \sum_i \lambda_i \nabla g_i(x^*) + \sum_j \nu_j \nabla h_j(x^*) = 0∇ f ( x ∗ ) + ∑ i λ i ∇ g i ( x ∗ ) + ∑ j ν j ∇ h j ( x ∗ ) = 0
原始可行 :g i ( x ∗ ) ≤ 0 , h j ( x ∗ ) = 0 g_i(x^*) \le 0, \; h_j(x^*) = 0g i ( x ∗ ) ≤ 0 , h j ( x ∗ ) = 0
对偶可行 :λ i ≥ 0 \lambda_i \ge 0λ i ≥ 0
互补松弛 :λ i g i ( x ∗ ) = 0 , ∀ i \lambda_i g_i(x^*) = 0, \; \forall iλ i g i ( x ∗ ) = 0 , ∀ i
辅助理解 :KKT 条件可以视为拉格朗日乘子法在不等式约束下的推广。互补松弛条件意味着:如果一个不等式约束在最优解处不是紧的(即 g i ( x ∗ ) < 0 g_i(x^*) < 0g i ( x ∗ ) < 0 ),那么它的对偶乘子 λ i \lambda_iλ i 必须为零——这条约束没有成本。
SVM 的训练过程本质上是求解一个凸二次规划:
min w , b 1 2 ∥ w ∥ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , … , n \min_{w, b} \frac{1}{2} \|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \ge 1, \; i=1,\dots,n
w , b min 2 1 ∥ w ∥ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , … , n
这是一个标准的 QP 问题。使用对偶方法后,所有计算仅涉及样本间的内积,因而可以引入核函数进行非线性分类。
min β 1 2 ∥ y − X β ∥ 2 2 + λ ∥ β ∥ 1 \min_{\beta} \frac{1}{2} \|y - X\beta\|_2^2 + \lambda \|\beta\|_1
β min 2 1 ∥ y − X β ∥ 2 2 + λ ∥ β ∥ 1
LASSO 的目标函数中,ℓ 1 \ell_1ℓ 1 正则项使某些 β \betaβ 分量为零,实现特征选择。这个问题可以通过坐标下降法(Coordinate Descent)高效求解——每次固定其他变量,优化一个变量的闭式解。LARS 算法甚至可以沿着正则化路径计算整个解序列。
信号恢复问题:从 m ≪ n m \ll nm ≪ n 次线性测量中恢复稀疏信号 x ∈ R n x \in \mathbb{R}^nx ∈ R n :
min ∥ x ∥ 1 s.t. A x = b \min \|x\|_1 \quad \text{s.t.} \quad Ax = b
min ∥ x ∥ 1 s.t. A x = b
这是一个线性规划(虽然使用了 ℓ 1 \ell_1ℓ 1 范数)。ℓ 1 \ell_1ℓ 1 最小化是 ℓ 0 \ell_0ℓ 0 问题的凸松弛,在一定条件下(如 RIP 性质)可以精确恢复原始稀疏信号。
CVX / CVXPY :高层次凸优化建模语言,自动转换为标准锥规划
ECOS / SCS :高效的锥求解器
MOSEK :商用求解器,对 SDP 和 SOCP 支持极好
Hugo 的经验:CVXPY 写问题非常方便,但要注意其默认求解器(ECOS)对某些病态问题收敛慢。遇到求解失败时,切换为 SCS 求解器(一阶方法,对大规模问题更稳定)或 MOSEK 往往能解决问题。此外,将问题转化为等价的锥形式 (如将 ℓ 1 \ell_1ℓ 1 范数约束转化为 SOCP)能显著提高求解效率。
非线性规划 (Nonlinear Programming, NLP)指目标函数或约束条件中存在非线性函数(且不一定是凸的)的最优化问题。其复杂度远高于凸优化。
特性
说明
举例
多极值
存在多个局部最优解
f ( x ) = − e − x 2 sin ( 5 x ) f(x) = -e^{-x^2} \sin(5x)f ( x ) = − e − x 2 sin ( 5 x ) 有无限多个局部极小点
鞍点
梯度为零但既非极大也非极小
f ( x , y ) = x 2 − y 2 f(x, y) = x^2 - y^2f ( x , y ) = x 2 − y 2 在 ( 0 , 0 ) (0,0)( 0 , 0 ) 处
不可微
目标函数可能非光滑
f ( x ) = ∥ x ∥ 1 + log ( 1 + e − x ) f(x) = \|x\|_1 + \log(1+e^{-x})f ( x ) = ∥ x ∥ 1 + log ( 1 + e − x ) 在 x = 0 x=0x = 0 处
病态条件
Hessian 矩阵特征值差异大
Rosenbrock 函数:κ ( ∇ 2 f ) ≈ 2500 \kappa(\nabla^2 f) \approx 2500κ ( ∇ 2 f ) ≈ 2500
x k + 1 = x k − α k ∇ f ( x k ) x_{k+1} = x_k - \alpha_k \nabla f(x_k)
x k + 1 = x k − α k ∇ f ( x k )
数值例子 :考虑 f ( x ) = x 2 + 10 sin ( x ) f(x) = x^2 + 10 \sin(x)f ( x ) = x 2 + 10 sin ( x ) ,初始点 x 0 = 3 x_0 = 3x 0 = 3 ,步长 α = 0.1 \alpha = 0.1α = 0.1 。
∇ f ( x ) = 2 x + 10 cos ( x ) \nabla f(x) = 2x + 10 \cos(x)∇ f ( x ) = 2 x + 10 cos ( x )
x 1 = 3 − 0.1 × ( 6 + 10 × cos ( 3 ) ) = 3 − 0.1 × ( 6 − 9.9 ) = 3 + 0.39 = 3.39 x_1 = 3 - 0.1 \times (6 + 10 \times \cos(3)) = 3 - 0.1 \times (6 - 9.9) = 3 + 0.39 = 3.39x 1 = 3 − 0.1 × ( 6 + 10 × cos ( 3 )) = 3 − 0.1 × ( 6 − 9.9 ) = 3 + 0.39 = 3.39
f ( 3.39 ) = 3.39 2 + 10 × sin ( 3.39 ) = 11.49 − 2.92 = 8.57 f(3.39) = 3.39^2 + 10 \times \sin(3.39) = 11.49 - 2.92 = 8.57f ( 3.39 ) = 3.3 9 2 + 10 × sin ( 3.39 ) = 11.49 − 2.92 = 8.57
经过 20 次迭代后收敛到局部极小点 x ≈ 4.10 x \approx 4.10x ≈ 4.10
一阶方法,对病态条件收敛慢。动量加速(Momentum)和 Nesterov 加速可显著改善。
x k + 1 = x k − [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k ) x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)
x k + 1 = x k − [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k )
对于 f ( x ) = x 2 − 4 x + 4 f(x) = x^2 - 4x + 4f ( x ) = x 2 − 4 x + 4 ,初始点 x 0 = 0 x_0 = 0x 0 = 0 ,牛顿法一步就能到达最优解 x ∗ = 2 x^* = 2x ∗ = 2 ,因为二次函数的一步牛顿法等价于直接求极值点。对比之下,梯度下降需要约 20 步(取决于步长选择)才能达到同样精度。
BFGS、L-BFGS 算法用梯度差分近似 Hessian 矩阵的逆
L-BFGS 只需要存储最近 m mm 步的梯度信息(通常 m = 10 m=10m = 10 ),在大规模优化中极为常用
适合场景对比 :
方法
每次迭代成本
收敛速度
适用问题规模
梯度下降
O ( n ) O(n)O ( n )
线性
百万级变量
牛顿法
O ( n 3 ) O(n^3)O ( n 3 )
二次
< 1000 变量
拟牛顿法(BFGS)
O ( n 2 ) O(n^2)O ( n 2 )
超线性
< 10000 变量
L-BFGS
O ( n ) O(n)O ( n )
近似超线性
百万级变量
存储量低,适合大规模问题。在求解线性方程组 A x = b Ax = bA x = b 时,CG 法最多 n nn 步收敛(精确算术下),实践中常截断为更少步数。
在每一步迭代中求解一个 QP 子问题,是业界最成功的 NLP 算法之一。其核心思想是在当前点对原问题进行二次近似:
min d 1 2 d T ∇ x x 2 L ( x k , λ k ) d + ∇ f ( x k ) T d s.t. ∇ g i ( x k ) T d + g i ( x k ) ≤ 0 , ∇ h j ( x k ) T d + h j ( x k ) = 0 \min_d \frac{1}{2} d^T \nabla^2_{xx} L(x_k, \lambda_k) d + \nabla f(x_k)^T d \\
\text{s.t.} \quad \nabla g_i(x_k)^T d + g_i(x_k) \le 0, \; \nabla h_j(x_k)^T d + h_j(x_k) = 0
d min 2 1 d T ∇ xx 2 L ( x k , λ k ) d + ∇ f ( x k ) T d s.t. ∇ g i ( x k ) T d + g i ( x k ) ≤ 0 , ∇ h j ( x k ) T d + h j ( x k ) = 0
将约束作为惩罚项加入目标函数:
外罚法 :F ( x ) = f ( x ) + ρ ∑ i max ( 0 , g i ( x ) ) 2 F(x) = f(x) + \rho \sum_i \max(0, g_i(x))^2F ( x ) = f ( x ) + ρ ∑ i max ( 0 , g i ( x ) ) 2
内点罚函数法 (Barrier Method):F ( x ) = f ( x ) − μ ∑ i log ( − g i ( x ) ) F(x) = f(x) - \mu \sum_i \log(-g_i(x))F ( x ) = f ( x ) − μ ∑ i log ( − g i ( x ))
随着 ρ → ∞ \rho \to \inftyρ → ∞ (或 μ → 0 \mu \to 0μ → 0 ),罚函数的最优解趋近于原问题的最优解。
SciPy :scipy.optimize.minimize 集成了多种算法:Nelder-Mead、BFGS、L-BFGS-B、SLSQP、trust-constr
NLopt :轻量级 NLP 库,支持多种局部和全局算法
IPOPT :基于内点法的大规模 NLP 求解器
SNOPT :基于 SQP 的稀疏 NLP 求解器
Hugo 踩坑记录:
使用 scipy.optimize.minimize 时,不要贪心选择 method='trust-constr' 做所有问题 。它对大规模约束问题非常慢,并且容易在约束边界处震荡。对于约束较少的问题,SLSQP 是更稳定的选择。
梯度的数值精度 :当手动提供梯度但 Hessian 未提供时,数值 Hessian 近似可能引入误差。建议总是做一次有限差分梯度校验(scipy.optimize.check_grad)。
某些非线性约束会导致可行域为空,但求解器可能不会显式告诉你,而是返回一个不可行点。务必检查 result.success 和约束违反量。
现实中的许多优化问题存在不确定性——目标函数可能受到随机噪声影响,约束条件的参数可能是随机变量,或者数据是以流式方式逐步到达的。这类问题需要随机优化 的方法。
对于经验风险最小化问题 min x 1 n ∑ i = 1 n f i ( x ) \min_x \frac{1}{n} \sum_{i=1}^n f_i(x)min x n 1 ∑ i = 1 n f i ( x ) ,SGD 的每次迭代只使用一个样本(或一个小批量)的梯度:
x k + 1 = x k − α k ∇ f i k ( x k ) x_{k+1} = x_k - \alpha_k \nabla f_{i_k}(x_k)
x k + 1 = x k − α k ∇ f i k ( x k )
对于一个简单线性回归问题 f ( x ) = 1 n ∑ ( y i − x T z i ) 2 f(x) = \frac{1}{n} \sum (y_i - x^T z_i)^2f ( x ) = n 1 ∑ ( y i − x T z i ) 2 ,全梯度下降每次迭代需要 O ( n p ) O(np)O ( n p ) 的计算量(n nn 为样本数,p pp 为特征数),而 SGD 只需 O ( p ) O(p)O ( p ) 。当 n = 10 6 , p = 10 3 n = 10^6, p = 10^3n = 1 0 6 , p = 1 0 3 时,SGD 每步快 100 万倍。虽然 SGD 需要更多步数才能收敛,但总体时间仍远少于全梯度下降。
方法
特点
适用场景
SGD
方差大,需要递减步长
深度学习、在线学习
SGD with Momentum
减少震荡,加速收敛
神经网络训练
Adam
自适应学习率 + 动量
深度学习事实标准
AdaGrad
自适应学习率,稀疏梯度好
NLP、推荐系统
SVRG
方差缩减,线性收敛率
中等规模凸优化
SAGA
方差缩减,无约束凸优化
逻辑回归、线性 SVM
当问题参数是随机变量时,两阶段随机规划的标准形式为:
min x c T x + E ξ [ Q ( x , ξ ) ] s.t. A x = b , x ≥ 0 \min_x c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t.} \quad Ax = b, \; x \ge 0
x min c T x + E ξ [ Q ( x , ξ )] s.t. A x = b , x ≥ 0
其中 Q ( x , ξ ) Q(x, \xi)Q ( x , ξ ) 是第二阶段问题的目标值(观察到随机变量实现后的补救成本)。数值求解通常使用样本均值近似(SAA)或随机分解方法。
在线凸优化(Online Convex Optimization, OCO)的框架是:在每轮 t tt ,决策者选择一个动作 x t ∈ K x_t \in Kx t ∈ K ,然后观察到凸损失函数 f t f_tf t ,产生损失 f t ( x t ) f_t(x_t)f t ( x t ) 。目标是使遗憾 (Regret)最小化:
Regret T = ∑ t = 1 T f t ( x t ) − min x ∈ K ∑ t = 1 T f t ( x ) \text{Regret}_T = \sum_{t=1}^T f_t(x_t) - \min_{x \in K} \sum_{t=1}^T f_t(x)
Regret T = t = 1 ∑ T f t ( x t ) − x ∈ K min t = 1 ∑ T f t ( x )
数值例子 :假设一个投资者每天在两种资产间分配资金。使用在线梯度下降,若市场表现出对对手(adversarial)特性——即使市场波动剧烈,投资策略的累计收益与最优固定分配策略的差距也以 O ( T ) O(\sqrt{T})O ( T ) 增长。这保证了长期平均性能趋近于最优静态策略。
变分法 (Calculus of Variations)是最优化的函数空间推广:决策变量是函数而非有限维向量。它研究如何找到使泛函 J [ y ] = ∫ a b L ( x , y , y ′ ) d x J[y] = \int_a^b L(x, y, y') dxJ [ y ] = ∫ a b L ( x , y , y ′ ) d x 取极值的函数 y ( x ) y(x)y ( x ) 。
泛函极值的必要条件由 Euler–Lagrange 方程给出:
∂ L ∂ y − d d x ( ∂ L ∂ y ′ ) = 0 \frac{\partial L}{\partial y} - \frac{d}{dx}\left( \frac{\partial L}{\partial y'} \right) = 0
∂ y ∂ L − d x d ( ∂ y ′ ∂ L ) = 0
数值例子 :最速降线问题(Brachistochrone Problem)是变分法的经典案例。1696 年,约翰·伯努利提出挑战:在两点之间(不是垂直方向),小球沿什么曲线下降最快?当时牛顿用一晚上就解决了这个问题。结果表明,沿摆线(Cycloid)下降的时间最短。对于两点 ( 0 , 0 ) (0,0)( 0 , 0 ) 和 ( 1 , 1 ) (1,1)( 1 , 1 ) ,直线路径需要约 0.637 秒(假设 g = 9.8 g=9.8g = 9.8 ),而摆线路径只需要约 0.592 秒——节省了约 7% 的时间。这个问题的数学建模和求解充分展示了变分法的威力。
最优控制研究的是随时间变化的控制信号 u ( t ) u(t)u ( t ) ,使得系统状态 x ( t ) x(t)x ( t ) 按动力学演化并最小化某个性能指标。
Pontryagin 最大值原理 给出了最优控制的必要条件:
u ∗ ( t ) = arg min u H ( x , u , λ , t ) u^*(t) = \arg\min_{u} \mathcal{H}(x, u, \lambda, t)
u ∗ ( t ) = arg u min H ( x , u , λ , t )
其中 H \mathcal{H}H 是哈密顿函数,λ \lambdaλ 是协态变量。
数值例子 :考虑简单的一维动力学系统 x ˙ = u \dot{x} = ux ˙ = u ,初始状态 x ( 0 ) = 0 x(0) = 0x ( 0 ) = 0 ,目标是最小化 J = ∫ 0 1 ( x 2 + u 2 ) d t J = \int_0^1 (x^2 + u^2) dtJ = ∫ 0 1 ( x 2 + u 2 ) d t ,终端状态自由。由最大值原理可得最优控制为 u ∗ ( t ) = λ ( t ) u^*(t) = \lambda(t)u ∗ ( t ) = λ ( t ) ,协态满足 λ ˙ = 2 x \dot{\lambda} = 2xλ ˙ = 2 x ,边界条件 λ ( 1 ) = 0 \lambda(1) = 0λ ( 1 ) = 0 。求解两边界值问题得到 x ∗ ( t ) = e t − e − t e 2 − e − 2 ⋅ ( e − e − 1 ) x^*(t) = \frac{e^t - e^{-t}}{e^2 - e^{-2}} \cdot (e - e^{-1})x ∗ ( t ) = e 2 − e − 2 e t − e − t ⋅ ( e − e − 1 ) 。这就是线性二次型调节器(LQR)的最简形式。
动态规划 (Dynamic Programming)和 Bellman 方程 是另一条路径。在连续时间下的 Hamilton-Jacobi-Bellman(HJB)方程为:
− ∂ V ∂ t = min u [ L ( x , u ) + ∇ V ⋅ f ( x , u ) ] -\frac{\partial V}{\partial t} = \min_u \left[ L(x, u) + \nabla V \cdot f(x, u) \right]
− ∂ t ∂ V = u min [ L ( x , u ) + ∇ V ⋅ f ( x , u ) ]
HJB 方程是充分条件,但通常难以解析求解(高维 PDE)。实践中常用近似动态规划(ADP)或深度强化学习来处理高维问题。
机器人轨迹规划 :Boston Dynamics 的 Atlas 机器人使用模型预测控制(MPC)实时规划跳跃和翻转动作
火箭发射与轨道转移 :阿波罗登月计划的月球着陆轨迹是最优控制的实际壮举
自动驾驶汽车 :路径跟踪与避障控制
经济中的最优增长模型 :Ramsey-Cass-Koopmans 模型
最优实验设计 :在化学或生物实验中最小化实验次数同时最大化信息量
方法
优点
缺点
典型工具
打靶法
精度高,变量少
对初值敏感,稳定性差
MATLAB bvp5c
直接配点法
稳定,处理路径约束容易
变量多,需要 NLP 求解器
GPOPS, CasADi
DDP / iLQR
处理高维系统(>100 状态)
只适用无约束或简单约束
Crocoddyl
MPC
滚动时域,鲁棒性强
每步需在线求解
acados, osqp
Hugo 的经验:实际工程中最优控制问题大多用直接法 求解——打靶法对初始猜测极其敏感,而且协态的初值选择是门玄学。直接配点法配合 IPOPT 或 SNOPT 做 NLP 求解是业界标配。CasADi 是一个非常好用的工具,它支持自动微分和直接法最优控制建模。
当目标函数存在多个局部极值时,全局优化需要找到全局最优解。这是一类更难的问题——最坏情况下非凸全局优化是 NP 难的。
graph TD
A[全局优化方法] --> B[确定性方法]
A --> C[随机性/启发式方法]
B --> D[分支定界法]
B --> E[凸松弛法]
B --> F[区间方法]
C --> G[模拟退火]
C --> H[遗传算法]
C --> I[粒子群优化]
C --> J[差分进化]
C --> K[贝叶斯优化]
D --> L[数学保证最优性]
E --> L
G --> M[无保证]
H --> M
K --> M
style L fill:#c8e6c9
style M fill:#ffcdd2
模拟退火(Simulated Annealing) :借鉴金属退火过程,以一定概率接受更差的解来跳出局部最优。降温速率是关键参数——降温太快容易陷入局部最优(淬火),降温太慢计算成本高。理论要求降温速率满足 T k = T 0 / log ( k + 1 ) T_k = T_0 / \log(k+1)T k = T 0 / log ( k + 1 ) 才能保证收敛到全局最优。
遗传算法(Genetic Algorithm) :模拟自然选择。一个标准的遗传算法流程包含选择(Selection)、交叉(Crossover)、变异(Mutation)。数值例子 :求解 f ( x ) = x sin ( 10 π x ) + 1 f(x) = x \sin(10\pi x) + 1f ( x ) = x sin ( 10 π x ) + 1 在 [ − 1 , 2 ] [-1, 2][ − 1 , 2 ] 上的最大值。种群规模 50,编码为 20 位二进制,经过约 60 代进化即可稳定找到全局最优点 x ≈ 1.85 x \approx 1.85x ≈ 1.85 (f ≈ 2.85 f \approx 2.85f ≈ 2.85 ),而梯度下降法从随机的初始点出发约 60% 的概率会陷入局部最优。
粒子群优化(PSO) :群体智能算法,每个粒子同时追踪个体最优和全局最优。对比 GA,PSO 的参数更少(惯性权重 w ww 、认知系数 c 1 c_1c 1 、社会系数 c 2 c_2c 2 ),调参更简单,但处理离散变量不如 GA 自然。
贝叶斯优化(Bayesian Optimization) :基于高斯过程代理模型,使用 EI(Expected Improvement)或 UCB(Upper Confidence Bound)等采集函数选择下一个采样点。
应用
评估成本
维度
使用贝叶斯优化的理由
深度学习超参数调优
高(一次训练数小时)
<20
样本效率极高
A/B 测试设计
中(一次测试数天)
<10
结合业务约束
化学反应条件优化
高(一次实验数天)
<10
实验材料成本高
药物分子设计
极高(一次合成数周)
可达 100+
概率代理缓解降维困难
分支定界法(Branch and Bound) :用于混合整数规划(MIP),理论保证最优性。Gurobi 和 CPLEX 对 MILP 的求解效率在过去 20 年提升了超过 2000 倍(主要是预求解、切割平面、启发式的改进)。
scipy.optimize.differential_evolution:差分进化全局优化
Optuna / Hyperopt :超参数调优,支持贝叶斯方法
CMA-ES :协方差自适应进化策略,连续优化效果好
Gurobi / CPLEX :对混合整数线性规划(MILP)和混合整数二次规划(MIQP)支持极好
Hugo 的看法:全局优化不是万能的。很多人一上来就丢给遗传算法,实际上如果问题规模中等且结构良好,用凸松弛 + 分支定界 比纯启发式方法有更好的理论保证。贝叶斯优化在深度学习超参数搜索中很流行,但对于低维度(<20 维)效果最好,高维时高斯过程核函数的选择很关键。
许多实际优化问题涉及多个相互冲突的目标。例如设计一辆汽车需要同时最小化成本、最大化燃油效率和最小化排放。
多目标优化问题的标准形式为:
min x ∈ D [ f 1 ( x ) , f 2 ( x ) , … , f k ( x ) ] T \min_{x \in \mathcal{D}} \quad [f_1(x), f_2(x), \dots, f_k(x)]^T
x ∈ D min [ f 1 ( x ) , f 2 ( x ) , … , f k ( x ) ] T
由于各目标通常无法同时被极小化,多目标优化的核心概念是帕累托最优 (Pareto Optimality):
解 x ∗ x^*x ∗ 被称为帕累托最优,如果不存在另一个可行解 x xx 使得对所有 i ii 有 f i ( x ) ≤ f i ( x ∗ ) f_i(x) \le f_i(x^*)f i ( x ) ≤ f i ( x ∗ ) ,且至少有一个严格不等式成立。
所有帕累托最优解在目标空间中的像称为帕累托前沿 (Pareto Frontier)。
方法
原理
适用场景
加权求和法
F ( x ) = ∑ w i f i ( x ) F(x) = \sum w_i f_i(x)F ( x ) = ∑ w i f i ( x )
权重已知,凸帕累托前沿
ε \varepsilonε -约束法
优化一个目标,其余作为约束
探索帕累托前沿形状
NSGA-II
非支配排序遗传算法
任意问题,无权重假设
MOEA/D
基于分解的多目标进化算法
高维多目标(>3 个目标)
数值例子 :假设我们设计一个梁,需要最小化质量 f 1 f_1f 1 和最大挠度 f 2 f_2f 2 。通常更轻的梁挠度更大。帕累托前沿由一系列点构成——最小质量点挠度最大,最小挠度点质量最大。在帕累托前沿上选择哪个解取决于工程要求的权衡。
现代数据科学中的优化问题规模巨大——训练 GPT-4 涉及数百亿参数,优化变量数量超过 10 11 10^{11}1 0 11 。单机求解不再可行,需要分布式方法。
ADMM(交替方向乘子法) :将全局优化问题分解为多个可并行求解的子问题:
x k + 1 = arg min x f ( x ) + ρ 2 ∥ A x + B z k − c + u k ∥ 2 2 z k + 1 = arg min z g ( z ) + ρ 2 ∥ A x k + 1 + B z − c + u k ∥ 2 2 u k + 1 = u k + ρ ( A x k + 1 + B z k + 1 − c ) x^{k+1} = \arg\min_x f(x) + \frac{\rho}{2} \|Ax + Bz^k - c + u^k\|_2^2 \\
z^{k+1} = \arg\min_z g(z) + \frac{\rho}{2} \|Ax^{k+1} + Bz - c + u^k\|_2^2 \\
u^{k+1} = u^k + \rho(Ax^{k+1} + Bz^{k+1} - c)
x k + 1 = arg x min f ( x ) + 2 ρ ∥ A x + B z k − c + u k ∥ 2 2 z k + 1 = arg z min g ( z ) + 2 ρ ∥ A x k + 1 + B z − c + u k ∥ 2 2 u k + 1 = u k + ρ ( A x k + 1 + B z k + 1 − c )
ADMM 在大规模分布式学习、图像重建、网络优化中应用广泛。
联邦学习(Federated Learning)是一种分布式优化框架:多个客户端在本地计算梯度,中央服务器聚合更新。FedAvg 算法(McMahan et al., 2017)每轮选择一部分客户端,在本地执行多次 SGD 更新,然后上传模型参数进行平均。该算法在不收集原始数据的情况下训练模型,兼顾隐私保护和模型质量。
方法
通信成本
对异质性容忍
收敛率
分布式 SGD
O ( n d ) O(nd)O ( n d ) /轮
低
O ( 1 / T ) O(1/\sqrt{T})O ( 1/ T )
ADMM
O ( n d ) O(nd)O ( n d ) /轮
高
O ( 1 / T ) O(1/T)O ( 1/ T ) (强凸)
FedAvg
O ( d ) O(d)O ( d ) /轮
中
O ( 1 / T ) O(1/\sqrt{T})O ( 1/ T )
CoCoA
O ( d ) O(d)O ( d ) /轮
高
O ( 1 / T ) O(1/T)O ( 1/ T ) (强凸)
机器学习本质上是大量的优化问题:
问题类型
损失函数
优化方法
典型复杂度
线性回归
MSE(凸二次)
闭式解 / SGD
O ( n p 2 ) O(np^2)O ( n p 2 )
岭回归
MSE + ℓ 2 \ell_2ℓ 2 正则
闭式解
O ( p 3 ) O(p^3)O ( p 3 )
LASSO
MSE + ℓ 1 \ell_1ℓ 1 正则
坐标下降 / FISTA
O ( n p k ) O(npk)O ( n p k )
逻辑回归
Log Loss(凸)
IRLS / SGD
O ( n p ) O(np)O ( n p ) /迭代
支持向量机
Hinge Loss(凸)
SMO / QP
O ( n 2 p ) O(n^2 p)O ( n 2 p )
神经网络
高度非凸
SGD / Adam / RMSProp
O ( m b ) O(mb)O ( mb ) /迭代
决策树
信息增益(非平滑)
贪心分裂
O ( n p log n ) O(n p \log n)O ( n p log n )
深度学习中,SGD 和 Adam 是事实标准。虽然损失函数高度非凸,但实践中 SGD 总能找到泛化能力很好的解,这至今仍是一个开放的理论问题。
graph LR
A[机器学习问题] --> B[经验风险最小化]
B --> C[凸优化]
B --> D[非凸优化]
C --> E[全局最优解]
C --> F[对偶性分析]
D --> G[局部最优/鞍点]
D --> H[随机梯度方法]
E --> I[SVM/逻辑回归/LASSO]
F --> I
G --> J[深度学习/神经网络]
H --> J
style B fill:#fff9c4
style C fill:#e3f2fd
style D fill:#fce4ec
看清问题结构 :是凸的还是非凸的?有没有特殊结构(可分性、稀疏性)?
选对算法 :凸问题用内点法或一阶方法,非凸问题根据规模和精度要求选局部法或全局法
关注数值稳定性 :尺度归一化、梯度校验、约束违反量检查
重视预处理 :消除冗余约束、合并变量、对约束矩阵做条件数改善
增量调试 :从简单版本开始(先解无约束,再加约束),逐步增加复杂度
问题转换 :很多问题可以通过变量替换或松弛转化为更易求解的形式(如 ℓ 0 → ℓ 1 \ell_0 \to \ell_1ℓ 0 → ℓ 1 松弛)
利用结构 :稀疏性、低秩性、可分性——选择能利用这些结构的求解器
问题类型
推荐求解器
语言接口
许可
LP / MILP
Gurobi
Python, C++, Java, MATLAB
学术免费,商业付费
LP / MIP
HiGHS
Python, C, C#
开源 (MIT)
凸 SDP/SOCP
MOSEK
Python, C, MATLAB
学术免费,商业付费
凸锥优化
ECOS / SCS
Python (CVXPY)
开源
大规模 NLP
IPOPT
C++, Python (pyomo)
开源
稀疏 NLP
SNOPT
C, Python
商业
最优控制
CasADi + IPOPT
Python, MATLAB
开源 (LGPL)
超参数调优
Optuna
Python
开源 (MIT)
通用优化
SciPy optimize
Python
开源 (BSD)
在工程应用中,我的经验是:
不要浪费时间去实现自己的 LP/QP 求解器 ——这是 PhD 论文级别的工作。直接用 Gurobi 或 HiGHS。
检查对偶间隙 ——如果求解器支持,务必检查对偶信息。对偶间隙大说明问题可能是非凸的或者求解还没收敛。
敏感性分析很重要 ——不仅有最优解,还要知道解对参数变化的敏感度。对偶变量(影子价格)提供了这些信息。
鲁棒优化 ——当模型参数本身有不确定性时,考虑用鲁棒优化(Robust Optimization)或分布鲁棒优化(Distributionally Robust Optimization)来得到对数据误差不敏感的解。
矩阵结构利用 ——如果 Hessian 或约束矩阵是稀疏的、分块对角的、或带结构的(如 Toeplitz),选择能利用这些结构的求解器可以快几个数量级。
工具
类型
适用场景
Gurobi
商用求解器
LP/QP/MIP/MIQP,性能最强
HiGHS
开源求解器
LP/QP/MIP,性能接近商用
CVXPY
建模语言
凸优化快速原型
CasADi
NLP + 最优控制
最优控制、动力学优化
Optuna
超参数调优
机器学习超参数搜索
SciPy optimize
综合工具包
Python 环境下的通用优化
此页面为数学知识库 的一部分。