优化 II · 无约束优化：从梯度下降到 Newton 法
无约束问题 \(\min_x f(x)\) 的算法全景。主线三问：往哪走（下降方向）、走多远（步长）、多快到（收敛速率）。收敛速率一节是本页核心——"条件数决定一切"的定量版本，也是理解深度学习各种优化器为何存在的理论底座。
1. 最优性条件（回收数分 V）
一阶必要：\(\nabla f(x^*) = 0\)；二阶充分：\(\nabla f = 0\) 且 \(\nabla^2 f(x^*) \succ 0\) ⇒ 严格局部极小。凸问题中一阶条件即充要（优化 I）。算法的目标因此明确：找驻点（凸时即终点；非凸时接受"够好的"驻点——深度学习的现实立场）。
2. 下降法框架
步长 \(\alpha_k\) 的选法：精确线搜索（\(\min_\alpha f(x_k + \alpha d_k)\)，理论用）；Armijo 回溯（实用标准：从大步长起，不满足"充分下降" \(f(x_k + \alpha d) \leq f(x_k) + c\,\alpha \nabla f^\top d\) 就减半）；固定步长（深度学习的常态，代价是要调参——"学习率"之名由此而来）。
3. 梯度下降及其收敛速率（本页核心）
\(d_k = -\nabla f(x_k)\)（数分 V：最速下降方向）。收敛速率取决于函数的"弯曲程度"假设：
假设语言：\(L\)-光滑（梯度 Lipschitz：\(\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|\)，曲率上界）；\(\mu\)-强凸（曲率下界，优化 I）。条件数 \(\kappa = L/\mu\)。
| 函数类 | 固定步长 \(\alpha = 1/L\) 的速率 | 达到 \(\varepsilon\) 精度需要 |
|---|---|---|
| \(L\)-光滑 + 凸 | \(f(x_k) - f^* \leq \dfrac{L\|x_0 - x^*\|^2}{2k}\) | \(O(1/\varepsilon)\) 步（次线性） |
| \(L\)-光滑 + \(\mu\)-强凸 | \(\|x_k - x^*\|^2 \leq \Big(1 - \dfrac{\mu}{L}\Big)^k \|x_0 - x^*\|^2\) | \(O(\kappa \ln\frac1\varepsilon)\) 步（线性收敛） |
强凸情形的证明骨架（两行）：由 \(L\)-光滑的下降引理 \(f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f\|^2\)，再用强凸的 PL 不等式 \(\|\nabla f\|^2 \geq 2\mu(f - f^*)\)，代入得 \(f(x_{k+1}) - f^* \leq (1 - \frac{\mu}{L})(f(x_k) - f^*)\)。
几何读法（比公式重要）：等高线是圆（\(\kappa = 1\)）时一步到底；等高线是细长椭圆（\(\kappa\) 大）时梯度方向偏离圆心方向，轨迹锯齿形震荡，每步只前进一点——收敛步数正比于条件数。病态曲率是一切一阶方法的公敌。
🔗 AI 衔接：这张表是理解深度学习优化器动物园的钥匙——momentum 把 \(\kappa\) 依赖改善到 \(\sqrt\kappa\)（Nesterov 加速的成果）；Adam/RMSProp 用逐坐标缩放近似"预条件"来压 \(\kappa\)；BatchNorm 的平滑作用也常用"改善条件数"解释（ai 课 05 讲）。SGD 则是本节的随机化版本：噪声梯度换取每步 \(1/n\) 的成本（ai 课 04 讲）。
4. Newton 法：用曲率导航
对二阶 Taylor（数分 V）\(f(x_k + d) \approx f + \nabla f^\top d + \frac12 d^\top H d\) 求极小，得
优点：二次收敛（好起点附近误差平方级坍缩：\(\|x_{k+1} - x^*\| \leq C\|x_k - x^*\|^2\)，有效数字每步翻倍）；仿射不变（不怕病态坐标——它自带"把椭圆变回圆"的预条件，\(\kappa\) 对它不构成障碍）。
代价：每步要 Hessian（\(O(n^2)\) 存储）并解线性方程组（\(O(n^3)\)）——\(n\) 上百万（深度学习）时不可行；非凸区域 \(H\) 不正定时方向可能不下降（需修正）。
拟 Newton（BFGS）：不算 Hessian，用相邻两步的梯度差逐步拼出它的近似 \(B_k\)（割线条件 \(B_{k+1}(x_{k+1} - x_k) = \nabla f_{k+1} - \nabla f_k\)——一维割线法的多维版），秩二修正保正定。L-BFGS（只存最近 \(m\) 步、\(O(mn)\) 内存）是经典机器学习（逻辑回归、CRF）时代的主力优化器，至今仍是中等规模光滑问题的首选。
共轭梯度（CG）一嘴：专解二次型/线性方程组 \(Ax = b\) 的迭代法，\(n\) 步理论精确、每步只需矩阵乘向量——大规模稀疏问题之王（🔗 数值分析页详述；Newton 法内层的方程组常用它解，得"截断 Newton"）。
5. 方法选型速查
| 规模与性质 | 首选 |
|---|---|
| 小规模、光滑、要高精度 | Newton（或信赖域版本） |
| 中等规模、光滑 | L-BFGS |
| 大规模、目标是和式 \(\sum_i f_i\)（机器学习） | SGD 系（Adam 起手） |
| 不可微（L1、hinge） | 次梯度法 / 近端梯度（略超本科，知其名） |
6. 典型例题
例 1（条件数体感） \(f = \frac12(x_1^2 + 100 x_2^2)\)（\(\kappa = 100\)），从 \((100, 1)\) 出发做精确线搜索梯度下降：迭代点在两条"谷壁"间锯齿弹跳，误差每步乘 \(\big(\frac{\kappa-1}{\kappa+1}\big)^2 \approx 0.96\)——要 100+ 步；Newton 法一步到 \((0,0)\)（二次函数的 Hessian 恒定，一步精确）。这个 \(2\) 维小例子浓缩了本页全部要义，值得手算一轮。
例 2（求解全流程） \(\min f = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_2\)。 解：\(\nabla f = (2x_1 - 2x_2,\ 4x_2 - 2x_1 - 4)^\top = 0\) ⇒ \(x^* = (2, 2)\)；Hessian \(\begin{pmatrix} 2 & -2 \\ -2 & 4\end{pmatrix}\) 顺序主子式 \(2, 4 > 0\) 正定 ⇒ 全局极小（凸 + 驻点）。
例 3（Armijo 的必要性） \(f(x) = x^2\)，固定步长 \(\alpha = 1.1 > 2/L = 1\)：\(x_{k+1} = x_k(1 - 2.2) = -1.2 x_k\)——发散震荡。步长上限 \(2/L\) 不是装饰；"学习率过大导致损失爆炸"的最小数学模型就是它。\(\blacksquare\)
下一页：给优化加上约束——Lagrange 对偶与 KKT 条件，SVM 对偶的老家。