第 02 章 无约束优化基础

学习目标

读完本章，你应当能够：

1. 区分全局极小点、局部极小点、严格局部极小点和孤立局部极小点，并举出说明它们差别的例子。
2. 熟练使用 Taylor 定理的三种形式，陈述并证明一阶必要条件、二阶必要条件、二阶充分条件，以及"凸函数的驻点是全局极小点"。
3. 说清线搜索与信赖域两大算法框架的区别，写出最速下降、牛顿、拟牛顿（割线方程、SR1、BFGS）和非线性共轭梯度四类搜索方向。
4. 理解尺度（scaling）问题：为什么最速下降对变量单位敏感而牛顿法不敏感，以及如何用对角尺度化补救。
5. 判断一个序列是 Q-线性、Q-超线性还是 Q-二次收敛，理解 R-收敛与 Q-收敛的区别。
6. 在组合优化和参数估计中用最优性条件检验求解结果。

读前导读

这一章在解决什么问题

用 Excel Solver 求完均值–方差组合，它会弹出"Solver 找到一个解，可满足所有约束及最优状况"。这句话里的"最优状况"到底指什么？Solver 凭什么说它找到了？本章回答的就是这件事：一个点满足什么条件才算极小点，以及算法怎样一步步走到这样的点。

先说结论。在极小点上，往任何方向挪一小步，函数值都不会下降。用数学语言说：梯度（各方向的斜率）为零，Hessian（各方向的弯曲程度）半正定。你在 CFA 里推导"最小方差组合"时，对权重求导令其等于零，用的就是第一个条件；本章把它说严格，再补上第二个条件，告诉你它在什么时候不够用。

本章的第二部分是算法地图。所有迭代算法都在回答两个问题：往哪走（方向），走多远（步长）。最速下降法只看斜率，像只看久期估价格变化；牛顿法同时看斜率和弯曲，像用久期加凸性；拟牛顿法则不直接算弯曲程度，而是从最近两步的斜率变化里估出来。第三部分讲"收敛速度"，用来比较这些算法快慢，这决定了你的程序是跑 5 步还是 5 万步。

需要先想起来的数学

• 泰勒展开：一元时 \(f(x+h)\approx f(x)+f'(x)h+\tfrac12 f''(x)h^2\)。你最熟悉的例子就是债券：\(\Delta P/P\approx -D\,\Delta y+\tfrac12 C\,(\Delta y)^2\)，久期 \(D\) 对应一阶项，凸性 \(C\) 对应二阶项。本章的定理 2.1 是它的多元、精确版本。见 第 00 册第 02 章 导数与泰勒展开。
• 梯度 \(\nabla f\) 与 Hessian \(\nabla^2 f\)：\(\nabla\) 读作 nabla 或 del。\(\nabla f(x)\) 是 \(n\) 个偏导数排成的列向量，指向函数上升最快的方向；\(\nabla^2 f(x)\) 是 \(n\times n\) 的二阶偏导数矩阵，第 \((i,j)\) 元是 \(\partial^2 f/\partial x_i\partial x_j\)。例：\(f=x_1^2+3x_1x_2\)，\(\nabla f=(2x_1+3x_2,\ 3x_1)^T\)，\(\nabla^2 f=\begin{bmatrix}2&3\\3&0\end{bmatrix}\)。\(\nabla f(x)^Tp\) 是"沿方向 \(p\) 的斜率"（方向导数）。见 第 00 册第 05 章 多元微积分与优化。
• 正定、半正定与特征值：对称矩阵 \(B\) 正定（记作 \(B\succ 0\)）等价于所有特征值 \(>0\)；半正定（\(B\succeq 0\)）等价于所有特征值 \(\ge 0\)。特征值有正有负叫"不定"。条件数 \(\kappa=\lambda_{\max}/\lambda_{\min}\) 衡量"最陡方向与最平方向的弯曲程度之比"。见 第 00 册第 06 章 线性代数速成。
• 范数与大 O 小 o：\(\|p\|\) 是向量长度 \(\sqrt{p_1^2+\cdots+p_n^2}\)。\(O(\epsilon^2)\) 表示"大小不超过常数乘 \(\epsilon^2\)"，\(o(\|p\|)\) 表示"比 \(\|p\|\) 更快地趋于 0"。例：\(\epsilon=0.01\) 时 \(O(\epsilon^2)\) 约是 \(10^{-4}\) 量级，远小于一阶项。见 第 00 册第 07 章 概率中的分析工具。
• 反证法：定理 2.2–2.5 的证明都是"假设结论不成立，推出矛盾"。见 第 00 册第 08 章 读懂数学证明与符号。

怎么读这一章

核心必读是 2.2.3 的四个定理（尤其是陈述，证明可以第二遍再看）和 2.3.2 的搜索方向中最速下降与牛顿两段。2.2.2 的 Taylor 定理先看懂 (2.6) 一个式子即可，(2.4)(2.5) 用到时再回来。拟牛顿的 SR1/BFGS 公式第一次只需记住"割线方程"的意思，公式本身第 8 章会细讲。2.3.5 收敛速度建议对着量化实战的输出读，比读定义直观。2.2.4 非光滑和 R-收敛可以跳过。

2.1 问题与一个引例

无约束优化问题是

其中 \(f:\mathbb{R}^n\to\mathbb{R}\) 是光滑函数。本书说"光滑"，通常指二阶导数存在且连续。

要先建立一个基本认识：我们通常对 \(f\) 没有全局的了解。算法只知道在一系列点 \(x_0,x_1,x_2,\dots\) 上的函数值（也许还有导数），而这些点由算法自己选择。函数求值往往很昂贵，所以好算法应该"不浪费求值"，用尽量少的信息可靠地找到解。

例 2.1（非线性最小二乘数据拟合）　在时刻 \(t_1,\dots,t_m\) 测得信号 \(y_1,\dots,y_m\)，想用模型

拟合数据。定义残差（residual）\(r_j(x)=y_j-\phi(t_j;x)\)，求解

这是一个非线性最小二乘（nonlinear least-squares）问题。变量只有 6 个，但如果 \(m\) 很大（比如 \(10^5\)），每算一次 \(f\) 都要遍历全部数据，代价不小。原书设想求得的解约为 \(x^*\approx(1.1,0.01,1.2,1.5,2.0,1.5)\)，\(f(x^*)=0.34\)——目标值不为零，说明模型不能精确复现所有数据。

这个结构在量化中非常普遍：用 Nelson–Siegel 模型拟合收益率曲线、用 SVI 参数化拟合隐含波动率微笑、做 GARCH 的极大似然估计，都是"参数少、数据多、每次求值要扫一遍样本"。那么问题来了：怎样确认求出来的 \(x^*\) 确实是极小点？ 这就需要先说清楚什么叫"解"。

2.2 什么是解

2.2.1 几种极小点

• 全局极小点（global minimizer）：\(f(x^*)\le f(x)\) 对所有 \(x\) 成立。
• 局部极小点（local minimizer）：存在 \(x^*\) 的邻域 \(\mathcal{N}\)（包含 \(x^*\) 的开集），使 \(f(x^*)\le f(x)\) 对所有 \(x\in\mathcal{N}\) 成立。也称弱局部极小点。
• 严格局部极小点（strict local minimizer）：存在邻域使 \(f(x^*)<f(x)\) 对所有 \(x\in\mathcal{N},\ x\ne x^*\) 成立。
• 孤立局部极小点（isolated local minimizer）：存在邻域使 \(x^*\) 是其中唯一的局部极小点。

全局极小点难找，根本原因是算法只掌握局部信息：它永远无法确定没采样过的区域里没有一个更深的"坑"。原书图 2.2 画了一个有许多局部极小的函数，算法很容易被"困"在其中一个里；分子构象问题的势能函数可能有上百万个局部极小。

几个例子帮助区分这些概念：

• 常函数 \(f(x)=2\)：每一点都是（弱）局部极小点，但没有一个是严格的。
• \(f(x)=(x-2)^4\)：\(x=2\) 是严格局部极小点。
• \(f(x)=x^4\cos(1/x)+2x^4\)，\(f(0)=0\)：它二阶连续可微，\(x^*=0\) 是严格局部极小点，但在 0 附近有一列严格局部极小点 \(x_n\to 0\)，所以 0 不是孤立的。

结论：孤立 ⇒ 严格，反之不成立（练习 3）。

2.2.2 Taylor 定理

识别极小点的工具是 Taylor 定理，它是全书分析的基础。

定理 2.1（Taylor 定理）　设 \(f:\mathbb{R}^n\to\mathbb{R}\) 连续可微，\(p\in\mathbb{R}^n\)，则存在 \(t\in(0,1)\) 使

若 \(f\) 二阶连续可微，则

且存在 \(t\in(0,1)\) 使

(2.4) 是多元中值定理；(2.6) 是带拉格朗日余项的二阶展开；(2.5) 是梯度的积分形式，后面分析牛顿法和拟牛顿法时反复使用。

推导拆解：先看一元版本。(2.6) 在 \(n=1\) 时就是 \(f(x+p)=f(x)+f'(x)p+\tfrac12 f''(x+tp)p^2\)，和久期–凸性近似是同一个式子，区别只在二阶导数取在 \(x\) 与 \(x+p\) 之间的某个点 \(x+tp\) 上。这样写换来的是等号而不是"约等于"：误差被精确地装进了这个未知的 \(t\) 里。证明里只需要知道"那一点的 Hessian 是正定还是负定"，不需要知道 \(t\) 具体是多少。 多元时，\(\nabla f(x)^Tp=\sum_i \frac{\partial f}{\partial x_i}p_i\)，是"每个变量的斜率乘该变量的变动，再加总"，就像组合的久期是各债券久期按头寸加权；\(p^T\nabla^2 f\,p=\sum_{i,j}\frac{\partial^2 f}{\partial x_i\partial x_j}p_ip_j\) 是二阶项，形式上和组合方差 \(w^T\Sigma w\) 一模一样。 (2.5) 是微积分基本定理"终点值 = 起点值 + 导数沿路径的积分"，只不过被积的"导数"是梯度的导数，即 Hessian：沿着从 \(x\) 到 \(x+p\) 的线段，把每一点的 Hessian 乘 \(p\) 累加起来，就得到梯度的总变化。

2.2.3 最优性条件

定理 2.2（一阶必要条件）　若 \(x^*\) 是局部极小点，且 \(f\) 在 \(x^*\) 的某个开邻域内连续可微，则 \(\nabla f(x^*)=0\)。

证明（反证）：设 \(\nabla f(x^*)\ne 0\)，取 \(p=-\nabla f(x^*)\)，则 \(p^T\nabla f(x^*)=-\|\nabla f(x^*)\|^2<0\)。由梯度的连续性，存在 \(T>0\) 使 \(p^T\nabla f(x^*+tp)<0\) 对所有 \(t\in[0,T]\) 成立。由 (2.4)，对任意 \(\bar t\in(0,T]\)，

即沿 \(p\) 方向函数值严格下降，与 \(x^*\) 是局部极小点矛盾。\(\square\)

推导拆解：证明的思路一句话：梯度不为零，就沿负梯度走一小步，函数一定下降，所以不可能是极小点。逐步看： 第 1 步，\(p=-\nabla f(x^*)\)，于是 \(p^T\nabla f(x^*)=-\|\nabla f(x^*)\|^2\)，一个非零向量长度的平方取负，严格小于 0。 第 2 步，"由梯度的连续性"：在 \(x^*\) 处这个内积是负数，梯度连续，所以在 \(x^*\) 附近一小段（\(t\in[0,T]\)）它仍然是负数。 第 3 步，用中值形式 (2.4)：\(f(x^*+\bar tp)-f(x^*)=\bar t\cdot p^T\nabla f(\text{中间某点})\)，\(\bar t>0\) 乘一个负数，所以差为负。 第 4 步，\(\bar t\) 可以任意小，即离 \(x^*\) 任意近处都有更低的函数值，和"局部极小"的定义矛盾。 \(\square\) 是"证明完毕"的符号。 满足 \(\nabla f(x^*)=0\) 的点称为驻点（stationary point）。回忆：矩阵 \(B\) 正定指 \(p^TBp>0\) 对所有 \(p\ne0\) 成立；半正定指 \(p^TBp\ge 0\) 对所有 \(p\) 成立。

定理 2.3（二阶必要条件）　若 \(x^*\) 是局部极小点，且 \(\nabla^2 f\) 在 \(x^*\) 的开邻域内连续，则 \(\nabla f(x^*)=0\) 且 \(\nabla^2 f(x^*)\) 半正定。

证明：一阶条件已知。反设存在 \(p\) 使 \(p^T\nabla^2f(x^*)p<0\)，由连续性它在 \(t\in[0,T]\) 上保持为负。由 (2.6) 和 \(\nabla f(x^*)=0\)，

矛盾。\(\square\)

定理 2.4（二阶充分条件）　设 \(\nabla^2 f\) 在 \(x^*\) 的开邻域内连续，\(\nabla f(x^*)=0\) 且 \(\nabla^2 f(x^*)\) 正定，则 \(x^*\) 是 \(f\) 的严格局部极小点。

证明：由连续性，存在半径 \(r>0\)，使 \(\nabla^2 f\) 在球 \(\mathcal{D}=\{z:\|z-x^*\|<r\}\) 内处处正定。对任意 \(0<\|p\|<r\)，\(z=x^*+tp\in\mathcal{D}\)，由 (2.6)

注意三个条件的逻辑关系：充分条件比必要条件强（它保证的是严格极小），但它不是必要的。反例：\(f(x)=x^4\) 在 \(x^*=0\) 处是严格局部极小点，但 \(f''(0)=0\)，Hessian 不正定。

白话解释：三个条件的关系可以这样记。梯度为零只说明"这里是平地"，可能是谷底、山顶或马鞍。Hessian 告诉你平地周围往各方向是向上弯还是向下弯：正定 = 各方向都向上弯 = 谷底（充分）；有一个方向向下弯 = 不是极小（必要条件排除了它）；某个方向弯曲为零 = 二阶信息看不出来，要看更高阶（如 \(x^4\) 和 \(x^3\) 在 0 处 \(f''\) 都是 0，前者是极小，后者不是）。 数值例子：练习 4 的 \(f=8x_1+12x_2+x_1^2-2x_2^2\) 在驻点 \((-4,3)\) 的 Hessian 是 \(\mathrm{diag}(2,-4)\)（对角线为 2、−4 的对角矩阵）。沿 \(x_1\) 方向向上弯，沿 \(x_2\) 方向向下弯，是马鞍点。

金融直觉：对一个债券多头，价格–收益率曲线凸性为正，意味着收益率往任一方向变动，二阶项都对你有利。Hessian 正定是"所有方向上凸性都为正"的多元版本。如果优化器停在一个 Hessian 有负特征值的点，就相当于存在某个调仓方向，沿它走"凸性为负"，函数还能再降——这个点不是最优。 定理 2.5（凸函数）　若 \(f\) 是凸函数，则任何局部极小点都是全局极小点。若 \(f\) 还可微，则任何驻点都是全局极小点。

证明：(1) 反设 \(x^*\) 是局部极小点但存在 \(z\) 使 \(f(z)<f(x^*)\)。考虑线段 \(x=\lambda z+(1-\lambda)x^*\)，\(\lambda\in(0,1]\)，由凸性

\(x^*\) 的任何邻域都包含这条线段的一小段，与局部极小矛盾。

(2) 同样取这样的 \(z\)，则

所以 \(\nabla f(x^*)\ne0\)，\(x^*\) 不是驻点。\(\square\)

小结：所有无约束优化算法，本质上都是在寻找 \(\nabla f(\cdot)=0\) 的点。对一般函数，找到驻点后还需检查 Hessian 才能确认是极小点；对凸函数，驻点就是答案。

量化中的例子　无约束均值–方差问题 \(\min_w f(w)=\frac\gamma2 w^T\Sigma w-\mu^Tw\) 的梯度为 \(\gamma\Sigma w-\mu\)，一阶条件给出 \(w^*=\gamma^{-1}\Sigma^{-1}\mu\)。Hessian \(\gamma\Sigma\)：若 \(\Sigma\) 正定，由定理 2.4 和 2.5，\(w^*\) 是唯一的全局最优解。但如果股票数 \(n\) 大于样本期数 \(T\)，样本协方差矩阵秩不足，Hessian 只是半正定：此时 \(\mu\) 若不在 \(\Sigma\) 的值域内，目标无下界（可以沿零空间方向无风险地"套利"）；即使有解也不唯一。这就是为什么高维组合优化必须对协方差做收缩估计或加正则项。

推导拆解：一阶条件 \(\gamma\Sigma w-\mu=0\) 是一个线性方程组，两边左乘 \(\Sigma^{-1}\) 再除以 \(\gamma\) 就得到 \(w^*=\gamma^{-1}\Sigma^{-1}\mu\)。一元时就是 \(w^*=\mu/(\gamma\sigma^2)\)：期望超额收益除以"风险厌恶 × 方差"，和 CFA 里最优风险资产配置比例 \(y^*=E(R_p-r_f)/(A\sigma_p^2)\) 完全相同。 "零空间"（null space）是满足 \(\Sigma v=0\) 的方向 \(v\) 组成的集合。沿这样的 \(v\) 调仓，组合方差变化 \(v^T\Sigma v=0\)，即零风险。若 \(\mu^Tv\ne 0\)，沿 \(v\)（或 \(-v\)）无限加仓就能无风险地无限增加期望收益，目标 \(\to-\infty\)。在真实市场里这是不可能的，它只是样本协方差"数据不够、低估了某些组合风险"的产物。

2.2.4 非光滑问题

本书主要处理光滑函数。对非光滑函数：

• 若 \(f\) 不连续，一般无法确定极小点；如果它由少数几个光滑片段拼成，可以分别对每片求极小。
• 若 \(f\) 连续但在某些点不可微，可借助次梯度（subgradient）来刻画解。原书图 2.3 中极小点恰好位于一个"折点"（kink）上，一阶导数在那里有跳跃，从一个点的信息无法推断邻近点的行为。
• 特殊非光滑函数如 \(f(x)=\|r(x)\|_1\)、\(f(x)=\|r(x)\|_\infty\) 有专门算法，常可转化为线性规划。

量化中的非光滑目标很多：\(\ell_1\) 交易成本 \(\sum_i|w_i-w_i^0|\)、最大回撤、CVaR、Lasso 惩罚。处理办法通常是引入辅助变量转化为 LP/QP（见本册第 13–16 章），或使用坐标下降、近端梯度等专门方法。

2.3 算法概览

所有无约束算法都需要用户给一个初始点 \(x_0\)。熟悉应用的人能给出合理估计（比如用上期的组合权重、用矩估计作为 MLE 的初值），否则就任意选取。算法生成迭代序列 \(\{x_k\}\)，用 \(x_k\)（可能还有历史点）的信息找一个函数值更低的 \(x_{k+1}\)，直到无法继续改进或已足够精确。

有些非单调（nonmonotone）算法不要求每一步都下降，只要求每 \(m\) 步下降一次：\(f(x_k)<f(x_{k-m})\)。

2.3.1 两种策略：线搜索与信赖域

线搜索（line search）先选一个方向 \(p_k\)，再沿这个方向近似求解一维问题

得到步长 \(\alpha\)。精确求解这个一维问题既昂贵又不必要，实际只试有限个步长，直到大致接近极小（第 3 章）。

信赖域（trust region）则先在 \(x_k\) 附近构造一个与 \(f\) 相似的模型函数 \(m_k\)，再在 \(x_k\) 周围的一个区域内极小化模型：

如果候选步不能充分降低 \(f\)，说明区域太大，缩小后重解。信赖域通常是球 \(\|p\|_2\le\Delta\)，\(\Delta>0\) 称为信赖域半径；也可以是椭球或盒子。模型通常取二次函数

其中 \(f_k=f(x_k)\)，\(\nabla f_k=\nabla f(x_k)\)，\(B_k\) 是 Hessian 或其近似。

例　\(f(x)=10(x_2-x_1^2)^2+(1-x_1)^2\) 在 \(x_k=(0,1)\) 处，\(\nabla f_k=(-2,20)^T\)，\(\nabla^2f_k=\mathrm{diag}(-38,20)\)——Hessian 不定，二次模型没有无约束极小点。但限制在信赖域内，模型极小总是存在的。原书图 2.4 画了两个不同半径下的模型极小点：半径缩小后，新的候选步不仅更短，方向通常也改变了。这是信赖域与线搜索（方向固定、只调长度）的本质区别。

一句话概括：线搜索先定方向，再定距离；信赖域先定最大距离，再同时选方向和步长。

2.3.2 线搜索的搜索方向

最速下降方向（steepest descent direction）\(-\nabla f_k\)。由 Taylor 展开

沿方向 \(p\) 的变化率是 \(p^T\nabla f_k=\|p\|\|\nabla f_k\|\cos\theta\)。在单位向量中，\(\cos\theta=-1\) 时下降最快，即 \(p=-\nabla f_k/\|\nabla f_k\|\)，它与等高线正交。优点是只需要梯度；缺点是在困难问题上可能极其缓慢（第 3 章定量分析）。

下降方向（descent direction）指与 \(-\nabla f_k\) 夹角严格小于 \(\pi/2\) 的方向，即 \(p_k^T\nabla f_k<0\)。由 \(f(x_k+\epsilon p_k)=f(x_k)+\epsilon p_k^T\nabla f_k+O(\epsilon^2)\)，沿下降方向走足够小的正步长必定使 \(f\) 下降。

牛顿方向（Newton direction），原书称它"也许是最重要的方向"。用二阶 Taylor 模型

当 \(\nabla^2 f_k\) 正定时，令 \(\nabla m_k(p)=0\) 得

推导拆解：对 \(m_k(p)\) 关于 \(p\) 求梯度：常数 \(f_k\) 求导为 0；\(p^T\nabla f_k\) 是线性项，梯度是 \(\nabla f_k\)；\(\tfrac12p^T\nabla^2f_kp\) 用"\(x^TAx\) 的梯度是 \(2Ax\)"（练习 2），得 \(\nabla^2f_kp\)。令总和为零：\(\nabla f_k+\nabla^2f_kp=0\)，解出 (2.14)。 一元时它就是 \(p=-f'(x)/f''(x)\)：斜率除以弯曲程度。数值例：\(f(x)=(x-3)^2\)，在 \(x=0\) 处 \(f'=-6\)，\(f''=2\)，\(p=3\)，一步正好到达极小点 3。对二次函数，牛顿法总是一步到位，因为二次模型就是函数本身。 实际计算时并不求逆矩阵，而是解线性方程组 \(\nabla^2 f_k\,p=-\nabla f_k\)，这样更快也更稳定（代码里的 np.linalg.solve 正是如此）。 它的几个特点：

• 模型可靠：(2.13) 与精确展开 (2.6) 的差别只在于用 \(\nabla^2f(x_k)\) 代替了 \(\nabla^2f(x_k+tp)\)；若 Hessian Lipschitz 连续，误差只有 \(O(\|p\|^3)\)。
• 是下降方向（Hessian 正定时）：\(\nabla f_k^Tp_k^N=-(p_k^N)^T\nabla^2f_kp_k^N<0\)。
• 自带步长 1：多数实现优先尝试单位步长，只在下降不充分时才调整。
• 局部收敛快，通常是二次收敛（第 3 章定理 3.7）。
• 缺点：Hessian 非正定时牛顿方向可能不存在或不是下降方向，需要修正（第 6 章）；而且要显式计算 Hessian，繁琐、易错、昂贵（第 7 章讨论如何自动计算）。

拟牛顿方向（quasi-Newton direction）用一个近似矩阵 \(B_k\) 代替真实 Hessian，并在每一步用新信息更新它，同样能达到超线性收敛。思路来自 (2.5)：

积分项是 \(o(\|p\|)\)。取 \(x=x_k\)、\(p=x_{k+1}-x_k\)，在解附近有

于是要求新近似 \(B_{k+1}\) 满足割线方程（secant equation）：

白话解释：割线方程的一元版本是 \(B_{k+1}=\dfrac{f'(x_{k+1})-f'(x_k)}{x_{k+1}-x_k}\)，就是"用两点斜率之差除以两点距离"来估计二阶导数——和用有限差分估计凸性是一回事：你在两个收益率上分别算出久期，就能估出凸性，不必再推解析公式。多元时，一个方程 \(B_{k+1}s_k=y_k\) 只约束了 Hessian 在 \(s_k\) 这一个方向上的作用，确定不了整个矩阵，所以还要加"对称"和"尽量少改动"（低秩修正）两个要求。"秩一"指修正项形如 \(uu^T\)（一个列向量乘它的转置），"秩二"指两个这样的项之和。

此外还要求 \(B_{k+1}\) 对称、\(B_{k+1}-B_k\) 是低秩矩阵。最常用的两个公式是

• SR1（对称秩一）：
  \[B_{k+1}=B_k+\frac{(y_k-B_ks_k)(y_k-B_ks_k)^T}{(y_k-B_ks_k)^Ts_k}.\tag{2.17}\]
• BFGS（以 Broyden、Fletcher、Goldfarb、Shanno 命名）：
  \[B_{k+1}=B_k-\frac{B_ks_ks_k^TB_k}{s_k^TB_ks_k}+\frac{y_ky_k^T}{y_k^Ts_k}.\tag{2.18}\]

两者都满足割线方程并保持对称。SR1 是秩一修正，BFGS 是秩二修正。若 \(B_0\) 正定且 \(s_k^Ty_k>0\)，BFGS 产生的 \(B_k\) 始终正定。搜索方向为 \(p_k=-B_k^{-1}\nabla f_k\)。

为了避免每步都分解 \(B_k\)，实际实现常直接更新它的逆 \(H_k=B_k^{-1}\)。BFGS 的逆形式为

这样 \(p_k=-H_k\nabla f_k\) 只需一次矩阵–向量乘法。拟牛顿法的系统讨论在本册第 8 章，大规模版本（L-BFGS 等）在第 9 章。

非线性共轭梯度方向（nonlinear conjugate gradient direction）：

其中标量 \(\beta_k\) 使 \(p_k\) 与 \(p_{k-1}\)"共轭"。共轭梯度法原本是求解对称正定线性方程组 \(Ax=b\) 的方法，等价于极小化凸二次函数 \(\phi(x)=\frac12x^TAx-b^Tx\)。非线性 CG 比最速下降有效得多，计算几乎一样简单，虽不如牛顿/拟牛顿快，但不需要存储矩阵（第 5 章）。

以上方向都可以直接用于线搜索框架；除 CG 外，它们都有信赖域版本。

2.3.3 信赖域的模型

• 取 \(B_k=0\)、欧氏范数信赖域：子问题 \(\min_p f_k+p^T\nabla f_k\) s.t. \(\|p\|_2\le\Delta_k\) 的解是 \(p_k=-\Delta_k\nabla f_k/\|\nabla f_k\|\)，即"步长由半径决定的最速下降"。
• 取 \(B_k=\nabla^2f_k\)：由于有半径约束，即使 Hessian 不定，子问题也总有解——信赖域牛顿法在实践中非常有效（第 4、6 章）。
• 取 \(B_k\) 为拟牛顿近似：得到信赖域拟牛顿法。

2.3.4 尺度

如果 \(x\) 沿某个方向变化引起的 \(f\) 变化远大于沿另一个方向，就说问题病态尺度（poorly scaled）。典型例子：\(f(x)=10^9x_1^2+x_2^2\)。

原书举了化学反应速率常数估计的例子：各变量的粗略量级为 \(x_1\approx10^{-10}\)、\(x_2\approx x_3\approx1\)、\(x_4\approx10^5\)。令 \(x=\mathrm{diag}(10^{-10},1,1,10^5)z\) 并以 \(z\) 为变量，最优 \(z\) 的各分量都在 1 的一个数量级内。这叫对角尺度化（diagonal scaling）。改变变量单位（米换成毫米）本身就是在做尺度变换，有时是无意的。

关键结论（原书图 2.7）：

• 最速下降对尺度敏感：等高线是拉长的椭圆时，最速下降方向几乎不能降低 \(f\)；等高线是圆时表现很好。
• 牛顿法不受尺度影响：对变量做线性变换 \(x=Sz\)，梯度变为 \(S^T\nabla f\)，Hessian 变为 \(S^T\nabla^2fS\)，牛顿步变换前后描述的是同一个点（练习 6）。
• 设计算法时应尽量让线搜索/信赖域策略和收敛检验具有尺度不变性（scale invariance）；一般说来，线搜索比信赖域更容易做到这一点（信赖域需要椭球形状来补偿，见第 4 章）。

在量化里，同时优化以"元"计的头寸和以"比例"计的权重，或者因子暴露量级相差几个数量级时，梯度法会慢得惊人。先把因子标准化（z-score），或者用波动率给头寸做尺度化（以"风险单位"计量头寸），正是对角尺度化。

2.3.5 收敛速度

设 \(x_k\to x^*\)。

• Q-线性（Q-linear）：存在 \(r\in(0,1)\)，使对充分大的 \(k\)，
  \[\frac{\|x_{k+1}-x^*\|}{\|x_k-x^*\|}\le r.\tag{2.21}\]
  例：\(x_k=1+(0.5)^k\)。Q 代表 quotient（商）。
• Q-超线性（Q-superlinear）：
  \[\lim_{k\to\infty}\frac{\|x_{k+1}-x^*\|}{\|x_k-x^*\|}=0.\]
  例：\(x_k=1+k^{-k}\)。
• Q-二次（Q-quadratic）：存在 \(M>0\)（不必小于 1），使对充分大的 \(k\)，
  \[\frac{\|x_{k+1}-x^*\|}{\|x_k-x^*\|^2}\le M.\]
  例：\(x_k=1+(0.5)^{2^k}\)。
• 一般的 Q-阶 \(p>1\)：\(\|x_{k+1}-x^*\|/\|x_k-x^*\|^p\le M\)。

收敛快慢主要取决于 \(r\)（对二次收敛则较弱地依赖 \(M\)）。无论常数如何，二次收敛序列最终总比线性收敛序列快。蕴含关系：二次 ⇒ 超线性 ⇒ 线性。典型情形：最速下降是线性收敛，病态时 \(r\) 接近 1；拟牛顿法是超线性收敛；牛顿法是二次收敛。 后文通常省略前缀 "Q"。

二次收敛的直观含义是：每迭代一步，正确的有效数字位数大约翻倍。线性收敛则是每步增加固定位数的有效数字，\(r=0.9\) 时大约每 22 步才增加一位。

白话解释：把误差 \(e_k=\|x_k-x^*\|\) 列出来就一目了然。从 \(e_0=0.1\) 出发： 线性（\(r=0.5\)）：\(0.1,\ 0.05,\ 0.025,\ 0.0125,\dots\)，每步误差打对折，像固定比例的摊销。 二次（\(M=1\)）：\(0.1,\ 0.01,\ 10^{-4},\ 10^{-8},\ 10^{-16}\)，4 步就到机器精度。 超线性介于两者之间：比值 \(e_{k+1}/e_k\) 本身越来越小。 "\(r=0.9\) 每 22 步一位"的算法：要让误差缩小 10 倍，需要 \(0.9^k=0.1\)，\(k=\ln 0.1/\ln 0.9\approx 21.9\)。这和"按 10% 年利率翻倍需要约 7 年"是同一种对数计算。 R-收敛（R 代表 root）：如果存在非负序列 \(\{\nu_k\}\) 使 \(\|x_k-x^*\|\le\nu_k\) 且 \(\nu_k\) Q-线性收敛到 0，就称 \(\{x_k\}\) R-线性收敛——误差被一个 Q-线性序列"控制"（dominated）。类似定义 R-超线性、R-二次。原书例 (2.22)：

它 R-线性收敛到 1，但不是 Q-线性的（奇数步误差为 0，下一步误差又变正，商无定义或无界）。R-收敛允许误差在某些步增大，Q-收敛则要求充分大 \(k\) 后每步都减小。多数收敛分析关注 Q-收敛。

2.4 量化实战：用最优性条件检验解，用实验观察收敛速度

场景一：Kelly 组合　Kelly（对数增长最优）组合求解 \(\max_w \mathbb{E}[\log(1+R^Tw)]\)，其中 \(R\) 是超额收益向量。用 \(T\) 个情景近似期望，问题变为无约束凸优化

Hessian 是正项加权的外积和，半正定，故 \(f\) 凸；由定理 2.5，驻点即全局最优。

推导拆解：梯度和 Hessian 都只用链式法则。设 \(g_t(w)=1+R_t^Tw\)，它对 \(w\) 的梯度是 \(R_t\)。外层 \(\log\) 的导数是 \(1/g_t\)，所以 \(\nabla\log g_t=R_t/(1+R_t^Tw)\)，取平均再加负号就是 \(\nabla f\)。再求一次导：\(R_t/g_t\) 中只有分母依赖 \(w\)，\((1/g)'=-1/g^2\)，乘上内层梯度 \(R_t^T\)，得 \(-R_tR_t^T/g_t^2\)，前面的负号抵消，就是 \(\nabla^2 f\)。 "外积" \(R_tR_t^T\) 是 \(n\times n\) 矩阵，对任意 \(v\) 有 \(v^TR_tR_t^Tv=(R_t^Tv)^2\ge 0\)，所以每一项都半正定，正系数加权求和后仍半正定。我们用牛顿法和固定步长梯度法分别求解，检验一阶、二阶条件，并实测收敛速度。

场景二：尺度　同时配置货币基金、债券、信用、股票、商品、加密资产，年化波动率从 0.5% 到 60%，协方差矩阵条件数巨大。比较最速下降在原始权重和"风险单位"尺度化变量上的表现。

import numpy as np
rng = np.random.default_rng(1)

# ---------- Part 1: Kelly（对数增长最优）组合：牛顿法 vs 固定步长梯度法 ----------
T, n = 600, 4                                    # 600 个月度情景，4 个资产（超额收益）
mu_true = np.array([0.006, 0.008, 0.004, 0.010])
vol = np.array([0.04, 0.06, 0.03, 0.08])
corr = 0.3 + 0.7 * np.eye(n)
L = np.linalg.cholesky(corr * np.outer(vol, vol))
R = mu_true + rng.standard_normal((T, n)) @ L.T  # 情景收益矩阵

def f(w):    return -np.mean(np.log1p(R @ w))
def grad(w): return -(R / (1 + R @ w)[:, None]).mean(0)
def hess(w):
    s = 1 / (1 + R @ w) ** 2
    return (R * s[:, None]).T @ R / T

# 先用牛顿法把解算到机器精度，作为 x*
w = np.zeros(n)
for _ in range(30):
    w = w - np.linalg.solve(hess(w), grad(w))
w_star = w
print("Kelly 权重 w* =", np.round(w_star, 3))
print("一阶条件 ||grad f(w*)|| = %.1e" % np.linalg.norm(grad(w_star)))
print("二阶条件 Hessian 特征值 =", np.round(np.linalg.eigvalsh(hess(w_star)), 5))

# 牛顿法：观察 e_{k+1}/e_k^2 是否有界（Q-二次）
w, e_prev = np.zeros(n), None
print("\n牛顿法  k   ||w_k - w*||     e_k/e_{k-1}^2")
for k in range(4):
    e = np.linalg.norm(w - w_star)
    print("      %2d   %.3e   %s" % (k, e, "" if e_prev is None else "%.2f" % (e / e_prev**2)))
    if e < 1e-14: break
    e_prev = e
    w = w - np.linalg.solve(hess(w), grad(w))

# 梯度法（固定步长 1/λ_max(H*)）：观察 e_{k+1}/e_k 是否趋于常数（Q-线性）
H = hess(w_star); lam = np.linalg.eigvalsh(H)
alpha = 1 / lam[-1]
print("\nHessian 条件数 κ = %.1f，理论线性收敛因子 1-1/κ = %.4f" % (lam[-1] / lam[0], 1 - lam[0] / lam[-1]))
w = np.zeros(n); errs = []
for k in range(2001):
    errs.append(np.linalg.norm(w - w_star))
    w = w - alpha * grad(w)
for k in [10, 50, 100, 200, 300]:
    print("梯度法 k=%4d  e_k = %.3e  e_k/e_{k-1} = %.4f" % (k, errs[k], errs[k] / errs[k - 1]))

# ---------- Part 2: 尺度问题 —— 不同资产类别的波动率差异造成病态 ----------
vols = np.array([0.005, 0.03, 0.08, 0.20, 0.25, 0.60])   # 货基、债券、信用、股票、商品、加密
C = 0.2 + 0.8 * np.eye(6)
Sigma = C * np.outer(vols, vols); mu = 0.5 * vols**2 + 0.01
def steepest_descent_exact(Q, b, tol=1e-10, maxit=200000):
    """f = 1/2 x'Qx - b'x，精确线搜索最速下降，返回迭代次数"""
    x = np.zeros(len(b))
    for k in range(maxit):
        g = Q @ x - b
        if np.linalg.norm(g) < tol * np.linalg.norm(b): return k
        x = x - (g @ g) / (g @ Q @ g) * g
    return maxit
print("\n原变量 w:        κ(Σ) = %.0f，最速下降迭代 %d 次" %
      (np.linalg.cond(Sigma), steepest_descent_exact(Sigma, mu)))
D = np.diag(vols)                  # 对角尺度化 w = D^{-1} z，即以“风险单位”计量头寸
Sz = np.linalg.inv(D) @ Sigma @ np.linalg.inv(D)   # = 相关系数矩阵
print("尺度化变量 z:    κ = %.1f，最速下降迭代 %d 次" %
      (np.linalg.cond(Sz), steepest_descent_exact(Sz, np.linalg.inv(D) @ mu)))
print("牛顿法：二次函数上 1 步到达极小点（与尺度无关）")

运行输出：

Kelly 权重 w* = [3.37  1.529 0.11  0.192]
一阶条件 ||grad f(w*)|| = 8.1e-19
二阶条件 Hessian 特征值 = [0.0008  0.00134 0.00297 0.00937]

牛顿法  k   ||w_k - w*||     e_k/e_{k-1}^2
       0   3.707e+00   
       1   1.074e-01   0.01
       2   2.382e-04   0.02
       3   2.176e-09   0.04

Hessian 条件数 κ = 11.6，理论线性收敛因子 1-1/κ = 0.9141
梯度法 k=  10  e_k = 7.079e-01  e_k/e_{k-1} = 0.8724
梯度法 k=  50  e_k = 1.068e-02  e_k/e_{k-1} = 0.9133
梯度法 k= 100  e_k = 1.191e-04  e_k/e_{k-1} = 0.9141
梯度法 k= 200  e_k = 1.501e-08  e_k/e_{k-1} = 0.9141
梯度法 k= 300  e_k = 1.891e-12  e_k/e_{k-1} = 0.9141

原变量 w:        κ(Σ) = 16442，最速下降迭代 123325 次
尺度化变量 z:    κ = 2.5，最速下降迭代 27 次
牛顿法：二次函数上 1 步到达极小点（与尺度无关）

解读

• 检验解：梯度范数 \(8\times10^{-19}\)（一阶条件），Hessian 特征值全正（二阶充分条件），且 \(f\) 凸——三重证据说明 \(w^*\) 是全局最优。实务中，任何优化器返回的结果都应做这一检查，尤其是返回 "success" 但梯度范数仍然不小的情况。（Kelly 权重总杠杆约 5 倍，这正是全 Kelly 在实践中通常要打折使用的原因，与本章主题无关，不展开。）
• 二次收敛：牛顿法误差 \(3.7\to0.11\to2.4\times10^{-4}\to2.2\times10^{-9}\)，\(e_k/e_{k-1}^2\) 保持在 0.01–0.04 之间，有效数字每步大约翻倍。
• 线性收敛：固定步长梯度法的误差比稳定在 \(0.9141\)，正好等于理论值 \(1-1/\kappa\)，大约 27 步才增加一位有效数字。即使条件数只有 11.6，达到 \(10^{-12}\) 也要 300 步。
• 尺度：多资产类别的协方差矩阵条件数达 16442，精确线搜索最速下降要 12 万步；以波动率做对角尺度化后条件数降到 2.5，只需 27 步。而牛顿法在二次函数上一步到位，完全不受尺度影响。

本章小结

无约束优化的"解"有全局、局部、严格、孤立之分，算法只能利用局部信息，所以一般只保证找到局部解。Taylor 定理导出了识别极小点的工具：一阶必要条件 \(\nabla f=0\)、二阶必要条件（Hessian 半正定）、二阶充分条件（Hessian 正定 ⇒ 严格局部极小）；对凸函数，驻点即全局极小。算法分线搜索和信赖域两大框架，搜索方向有最速下降、牛顿、拟牛顿和非线性共轭梯度四类。最速下降简单但对尺度敏感、线性收敛；牛顿法尺度不变、二次收敛但需要 Hessian；拟牛顿法用割线方程近似 Hessian，超线性收敛。

练习

基础

1. （原书 2.1）对 Rosenbrock 函数 \(f(x)=100(x_2-x_1^2)^2+(1-x_1)^2\) 求梯度和 Hessian，证明 \(x^*=(1,1)^T\) 是唯一的局部极小点，且该点 Hessian 正定。 提示：\(\nabla f=(-400x_1(x_2-x_1^2)-2(1-x_1),\ 200(x_2-x_1^2))^T\)；令其为零得 \(x_2=x_1^2\)、\(x_1=1\)；\(\nabla^2f(x^*)=\begin{bmatrix}802&-400\\-400&200\end{bmatrix}\)，行列式 \(400>0\)。
2. （原书 2.3）设 \(a\in\mathbb{R}^n\)，\(A\) 为 \(n\times n\) 对称矩阵。求 \(f_1(x)=a^Tx\) 和 \(f_2(x)=x^TAx\) 的梯度与 Hessian。由此写出 \(\frac\gamma2w^T\Sigma w-\mu^Tw\) 的梯度与 Hessian。 提示：\(\nabla f_1=a\)，\(\nabla^2f_1=0\)；\(\nabla f_2=2Ax\)，\(\nabla^2f_2=2A\)。
3. （原书 2.6）证明孤立局部极小点一定是严格局部极小点。 提示：若不严格，邻域内存在 \(\hat x\ne x^*\) 使 \(f(\hat x)=f(x^*)\)……注意需要说明 \(\hat x\) 本身也是局部极小点，再与孤立性矛盾。
4. （原书 2.2）证明 \(f(x)=8x_1+12x_2+x_1^2-2x_2^2\) 只有一个驻点，并且它既不是极大点也不是极小点。 提示：驻点 \((-4,3)\)，Hessian \(\mathrm{diag}(2,-4)\) 不定，是鞍点。
5. 判断下列序列的收敛阶：(a) \(x_k=1/k\)；(b) \(x_k=1+(0.5)^{2^k}\)；(c) \(x_k=1/k!\)。 提示：(a) 次线性（比值 \(\to1\)）；(b) Q-二次；(c) Q-超线性但不是 Q-二次（\(\frac{1/(k+1)!}{(1/k!)^2}=\frac{k!}{k+1}\to\infty\)）。

进阶

6. （原书 2.9）设 \(x=Sz+s\)，\(S\) 非奇异，\(\tilde f(z)=f(Sz+s)\)。证明 \(\nabla\tilde f(z)=S^T\nabla f(x)\)，\(\nabla^2\tilde f(z)=S^T\nabla^2f(x)S\)。进一步证明：在 \(z\) 空间算出的牛顿步 \(\tilde p\) 满足 \(S\tilde p=p^N\)（牛顿法尺度不变），而最速下降步不满足。
7. （原书 2.5）设 \(f(x)=\|x\|^2\)，\(x_k=(1+2^{-k})(\cos k,\sin k)^T\)。证明 \(f(x_k)\) 单调下降，但单位圆上每一点都是 \(\{x_k\}\) 的极限点。这说明了什么？ 提示：函数值下降不等于迭代点收敛；收敛理论通常只保证梯度或函数值的性质。
8. 设样本协方差矩阵 \(\Sigma\) 奇异（\(n>T\)），\(\mu\) 属于 \(\Sigma\) 的值域。证明无约束均值–方差问题的解集是一个仿射子空间 \(w^*+\mathrm{null}(\Sigma)\)，并说明为什么所有解的期望收益与方差都相同。 提示：利用 \(\mu\in\mathrm{range}(\Sigma)\) 时 \(\mu\perp\mathrm{null}(\Sigma)\)（对称矩阵）。
9. （原书 2.10）证明：若 \(B_0\) 取适当的形式，SR1 和 BFGS 更新在仿射变量变换下保持不变（即在 \(z\) 空间迭代与在 \(x\) 空间迭代产生对应的点）。 提示：在 \(z\) 空间有 \(\tilde s=S^{-1}s\)，\(\tilde y=S^Ty\)；验证若 \(\tilde B_k=S^TB_kS\) 则 \(\tilde B_{k+1}=S^TB_{k+1}S\)。
10. 修改本章量化实战代码，把梯度法的步长从 \(1/\lambda_{\max}\) 改为 \(2/(\lambda_{\min}+\lambda_{\max})\)，观察收敛因子是否变成 \((\kappa-1)/(\kappa+1)\)。

原书推荐习题：2.1（Rosenbrock 函数，后续数值实验的标准测试函数）、2.3（二次型的梯度与 Hessian）、2.5（下降≠收敛）、2.9 与 2.10（变量变换与尺度不变性）、2.12–2.15（区分 Q-收敛与 R-收敛）。

原书对照

页码换算：原书正文页码约等于 PDF 页码减 21。