研究生课程 · 最优化方法
最优化方法
从"求解方程"到"寻找最好"：凸优化保证局部最优即全局最优；梯度下降是机器学习的发动机；KKT 条件统一了约束问题的最优性；单纯形沿着多面体的顶点跳到最优。Navier-Stokes 之外，这里是人类决策的数学。
1 凸集与凸函数
概念为什么"凸"如此重要
凸集：∀x,y ∈ C，tx+(1−t)y ∈ C（连线上任意点都在集合内——"没有凹陷"）。
凸函数：f(tx+(1−t)y) ≤ tf(x)+(1−t)f(y)；二阶条件：Hessian 半正定（一元：f″ ≥ 0）。
黄金性质：凸函数在凸集上的局部极小 = 全局极小——这让贪心的下降算法"下到谷底就是全球谷底"。保持凸性的运算：非负加权和、取最大、仿射复合。
凸函数：f(tx+(1−t)y) ≤ tf(x)+(1−t)f(y)；二阶条件：Hessian 半正定（一元：f″ ≥ 0）。
黄金性质：凸函数在凸集上的局部极小 = 全局极小——这让贪心的下降算法"下到谷底就是全球谷底"。保持凸性的运算：非负加权和、取最大、仿射复合。
非凸的代价：局部极小可能不是全局（神经网络损失面），算法只能保证收敛到驻点。判定 NP 难的情形（如某些整数规划）需要分支定界等全局方法。
2 无约束优化：梯度下降与牛顿法
定理一阶贪心与二阶精准
梯度下降：xₖ₊₁ = xₖ − η∇f(xₖ)。凸光滑情形收敛 O(1/k)；强凸 + 合适步长线性收敛。步长过大 → 震荡发散（下方实验室直接演示）。
收敛率：光滑凸 O(1/k)；强凸线性 O(ρᵏ)；Nesterov 加速把 O(1/k) 提到 O(1/k²)。
牛顿法：xₖ₊₁ = xₖ − H⁻¹∇f——用曲率信息，局部二次收敛；代价是每步 O(n³) 解方程 + 要求 Hessian 正定（拟牛顿 BFGS 用近似 H）。
Rosenbrock 函数 f = (1−x)² + 100(y−x²)²："香蕉谷"——经典算法试金石，谷底平坦导致梯度极小。
收敛率：光滑凸 O(1/k)；强凸线性 O(ρᵏ)；Nesterov 加速把 O(1/k) 提到 O(1/k²)。
牛顿法：xₖ₊₁ = xₖ − H⁻¹∇f——用曲率信息，局部二次收敛；代价是每步 O(n³) 解方程 + 要求 Hessian 正定（拟牛顿 BFGS 用近似 H）。
Rosenbrock 函数 f = (1−x)² + 100(y−x²)²："香蕉谷"——经典算法试金石，谷底平坦导致梯度极小。
随堂检测凸性与梯度法
3 约束优化与 KKT 条件
定理最优解的"身份证"
问题：min f(x) s.t. gᵢ(x) ≤ 0, hⱼ(x) = 0。拉格朗日函数 L = f + Σλᵢgᵢ + Σνⱼhⱼ。
KKT 条件（凸问题下充要）：① 平稳性 ∇f + Σλᵢ∇gᵢ + Σνⱼ∇hⱼ = 0；② 原始可行；③ 对偶可行 λ ≥ 0；④ 互补松弛 λᵢgᵢ = 0（约束不起作用时 λ=0；λ>0 时约束"绷紧"）。
对偶：max_λ min_x L ≤ 原问题（弱对偶）；凸 + Slater 条件 ⇒ 等号（强对偶）。对偶间隙为零时解对偶问题即得原解——SVM 的整个推导就是解对偶。
KKT 条件（凸问题下充要）：① 平稳性 ∇f + Σλᵢ∇gᵢ + Σνⱼ∇hⱼ = 0；② 原始可行；③ 对偶可行 λ ≥ 0；④ 互补松弛 λᵢgᵢ = 0（约束不起作用时 λ=0；λ>0 时约束"绷紧"）。
对偶：max_λ min_x L ≤ 原问题（弱对偶）；凸 + Slater 条件 ⇒ 等号（强对偶）。对偶间隙为零时解对偶问题即得原解——SVM 的整个推导就是解对偶。
4 线性规划与单纯形法
定理顶点定理与算法
LP：min cᵀx s.t. Ax ≤ b, x ≥ 0。顶点定理：若最优解存在，必在可行域（多面体）的顶点处取得。
单纯形法：从一个顶点出发，沿"让目标下降最快"的棱跳到相邻顶点，直至无更优邻居——实践中极快（指数最坏情形，Karmarkar 内点法多项式）。
对偶 LP：max bᵀy s.t. Aᵀy ≤ c, y≥0；强对偶成立，影子价格 = 对偶变量。
单纯形法：从一个顶点出发，沿"让目标下降最快"的棱跳到相邻顶点，直至无更优邻居——实践中极快（指数最坏情形，Karmarkar 内点法多项式）。
对偶 LP：max bᵀy s.t. Aᵀy ≤ c, y≥0；强对偶成立，影子价格 = 对偶变量。
随堂检测KKT 与 LP
5 更快的方法：拟牛顿、罚函数与信赖域
概念工程化的三大武器
拟牛顿（BFGS / L-BFGS）：不用显式 Hessian，用历史梯度差迭代修正近似 H⁻¹；L-BFGS 只存最近 m 步（O(mn) 内存）——大规模机器学习标配。
罚函数 / 增广拉格朗日：把约束塞进目标（f + μ·max(0,g)²），μ→∞ 逼向可行；ADMM 是其分布式升级版。
信赖域：先定"这一步最多走多远"（半径 Δ），在球内解子问题；效果好时扩域，失败则缩域——比线搜索更稳健。随机梯度下降（SGD）：minibatch 噪声版 GD，深度学习的默认选择。
罚函数 / 增广拉格朗日：把约束塞进目标（f + μ·max(0,g)²），μ→∞ 逼向可行；ADMM 是其分布式升级版。
信赖域：先定"这一步最多走多远"（半径 Δ），在球内解子问题；效果好时扩域，失败则缩域——比线搜索更稳健。随机梯度下降（SGD）：minibatch 噪声版 GD，深度学习的默认选择。