最优化

线性代数给出的是运算规则，概率论与统计推断给出的是判断依据，两者共同确定了模型的形式与目标。要把这些目标落到具体数值上，还需要第三样东西：一套从初始猜测出发、逐步逼近最优解的方法。这一部分讨论最优化（optimization）。

优化的语言在机器学习中出现得非常频繁。训练一个模型就是在最小化经验风险，正则化是在目标函数中加惩罚项，最大似然估计与最大后验估计都是优化问题，变分推断在最大化证据下界，强化学习在最大化累积回报的期望。这些问题的形式各异，处理它们的思路却高度一致：先判断问题属于哪一类，再根据结构选择算法，最后用收敛性分析判断需要多少计算量。

本章共 9 节，按问题设定 → 凸性工具 → 无约束算法 → 有约束与对偶 → 非凸 → 无梯度方法的顺序推进。3.1 建立优化的语言与分类体系；3.2 讨论凸集与凸函数，这是后面所有理论结论的基础工具；3.3 与 3.4 处理无约束问题，前者给出最优性条件、线搜索与梯度法的基础，后者介绍动量、加速、随机梯度、自适应步长与分布式训练这些实际系统中使用的算法；3.5 讨论二阶方法与拟牛顿法；3.6 处理约束问题与对偶理论；3.7 讨论近端方法与稀疏优化，它们是非光滑问题的主要工具；3.8 回到机器学习，讨论非凸优化的图景与深度学习训练中的现象；3.9 处理目标函数没有梯度信息或计算代价极高时的无梯度方法与贝叶斯优化。

结构

节	主题
3.1 优化问题的语言与分类	决策变量与目标函数、最优解概念、问题分类、凸性的地位、优化在机器学习中的位置
3.2 凸集与凸函数	凸集与凸组合、分离定理、凸函数判定、保凸运算、共轭函数与次梯度、光滑性与强凸性
3.3 无约束优化的最优性条件与梯度法	一二阶最优性条件、线搜索与步长、下降引理、收敛速率、条件数的影响、有限差分与自动微分
3.4 一阶方法的进展	动量法与重球法、Nesterov 加速、随机梯度下降、方差缩减、自适应步长、大批量训练、本地 SGD 与联邦学习
3.5 二阶方法与拟牛顿法	牛顿法与收敛性、拟牛顿与 BFGS、L-BFGS、高斯-牛顿、信赖域、共轭梯度
3.6 约束优化与对偶理论	拉格朗日函数、KKT 条件、对偶问题、强弱对偶、Slater 条件、罚函数与增广拉格朗日、内点法、锥规划
3.7 近端方法与稀疏优化	近端算子与 Moreau 包络、近端梯度与 ISTA/FISTA、算子分裂、ADMM、Frank-Wolfe、Lasso 的求解
3.8 非凸优化与机器学习	鞍点与逃逸、损失景观、过参数化与插值、双下降、隐式正则、平坦极小值、深度学习优化实践
3.9 无梯度优化与贝叶斯优化	网格与随机搜索、Nelder-Mead 与模式搜索、进化策略与 CMA-ES、贝叶斯优化与采集函数、超参数调优

学习路径

3.1 与 3.2 是工具箱，读完后应当能够判断一个优化问题属于哪一类，并识别目标函数的凸性与光滑性。3.3 到 3.5 是无约束优化的算法主线，三节的结论都以 3.2 节的二次上界与强凸性为基础：梯度法的收敛速率由条件数决定，动量与加速方法改善的是对条件数的依赖，牛顿法与拟牛顿法利用二阶信息把依赖进一步削弱。3.6 处理约束，对偶理论把有约束问题转化为无约束问题，KKT 条件给出可验证的最优性判据，这一节与 3.7 的近端方法共享同一套工具：近端算子可以看作对偶视角下的投影。3.8 与 3.9 处理两类不在主线上的问题：前者面对非凸性与深度学习训练中的实际现象，后者面对没有梯度信息的目标函数。

本章与前后内容的关系是双向的。前一章的极大似然、最小二乘、正则化估计与变分推断在这里获得算法层面的处理；下一章的信息论给出了另一类目标函数（交叉熵、KL 散度），它们在优化上的性质与本章讨论的凸性、光滑性直接相关。深度学习中的实际训练依赖本章 3.4 节的随机一阶方法，而理论解释依赖 3.8 节的内容。