一维搜索方法¶
本页讨论一元函数 \(f: \mathbb{R} \to \mathbb{R}\) 极小化的迭代求解方法（统称一维搜索或线搜索）。它的意义是双重的：既是最简单的优化问题，又是多维算法的子程序——梯度方法、牛顿法每一步沿搜索方向确定步长，本质上都在解一个一维问题。
核心结论速览
| 方法 | 使用的信息 | 需要的初始条件 | 区间压缩比 / 收敛特点 |
|---|---|---|---|
| 黄金分割法 | 仅函数值 \(f\) | 单峰 + 初始区间 | 每步 \(0.618\)，\(N\) 步共 \(0.618^N\) |
| 斐波那契数列法 | 仅函数值 \(f\) | 单峰 + 初始区间 | \(N\) 步共 \(\dfrac{1 + 2\varepsilon}{F_{N+1}}\)，同评估次数下最优 |
| 二分法 | 一阶导数 \(f'\) | 单峰、\(f \in \mathcal{C}^1\) + 初始区间 | 每步 \(1/2\)，\(N\) 步共 \((1/2)^N\) |
| 牛顿法 | \(f'\) 和 \(f''\) | 一个初始点（须离极小点足够近，\(f'' > 0\)） | 收敛快（二阶），但可能失效 |
| 割线法 | 仅 \(f'\) | 两个初始点 | 用差商代替 \(f''\) 的牛顿法 |
| 划界法 | 仅函数值 \(f\) | — | 为上述区间法寻找初始区间 |
多维算法中的步长通常不精确求解，用 Armijo / Goldstein / Wolfe 条件保证"步长不太大也不太小"即可。
问题与方法总览¶
一维搜索从初始点（或初始区间）出发，产生迭代序列 \(x^{(1)}, x^{(2)}, \dots\) 逼近极小点。按每步用到的信息分类：只用函数值（黄金分割、斐波那契）、用一阶导数（二分、割线）、用一二阶导数（牛顿）。
区间压缩类方法的共同前提是 \(f\) 在初始区间 \([a_0, b_0]\) 上单峰：存在唯一的局部极小点。单峰性保证"比较两个内点的函数值"足以判断极小点落在哪一侧。
黄金分割法¶
思想：在当前区间 \([a_k, b_k]\) 内对称地取两个试探点
比较函数值：若 \(f(a_{k+1}) < f(b_{k+1})\)，极小点必在 \([a_k, b_{k+1}]\) 内；反之在 \([a_{k+1}, b_k]\) 内。每步把区间压缩为原来的 \(1 - \rho\) 倍。
\(\rho\) 的取值从何而来：希望压缩后"旧试探点恰好可以充当新区间的一个试探点"，这样每步只需新算一次函数值。设区间长为 1，该复用条件为 \(\rho(1 - \rho) = 1 - 2\rho\)，即
此时 \(\dfrac{\rho}{1 - \rho} = \dfrac{1 - \rho}{1}\)——短段与长段之比等于长段与全长之比，正是黄金分割。
算法步骤（黄金分割法）
给定单峰区间 \([a_0, b_0]\) 与精度要求：
- 由 \(0.618^N (b_0 - a_0) \le\) 目标长度，确定迭代次数 \(N\)；
- 每步取试探点 \(a' = a + 0.382\,(b - a)\)，\(b' = b - 0.382\,(b - a)\)（其中一个继承自上一步，只需新算一个）；
- \(f(a') < f(b')\) → 新区间 \([a, b']\)；否则 → 新区间 \([a', b]\)；
- 重复 \(N\) 次，输出最终区间。
例：黄金分割法压缩区间
用黄金分割法求 \(f(x) = x^4 - 14x^3 + 60x^2 - 70x\) 在 \([0, 2]\) 上的极小点所在区间，要求长度压缩到 \(0.3\) 之内。
解答
确定迭代次数：\(2 \times 0.618^N \le 0.3 \Rightarrow N \ge 3.94\)，取 \(N = 4\)。
| \(k\) | 当前区间 | 试探点与函数值 | 比较 | 新区间 |
|---|---|---|---|---|
| 1 | \([0, 2]\) | \(a_1 = 0.764,\ f = -24.36\)；\(b_1 = 1.236,\ f = -18.96\) | \(f(a_1) < f(b_1)\) | \([0, 1.236]\) |
| 2 | \([0, 1.236]\) | 新点 \(a_2 = 0.472,\ f = -21.10\)；复用 \(b_2 = a_1 = 0.764\) | \(f(a_2) > f(b_2)\) | \([0.472, 1.236]\) |
| 3 | \([0.472, 1.236]\) | 复用 \(a_3 = 0.764\)；新点 \(b_3 = 0.944,\ f = -23.59\) | \(f(a_3) < f(b_3)\) | \([0.472, 0.944]\) |
| 4 | \([0.472, 0.944]\) | 新点 \(a_4 = 0.652,\ f = -23.84\)；复用 \(b_4 = 0.764\) | \(f(a_4) > f(b_4)\) | \([0.652, 0.944]\) |
最终区间长度 \(0.292 < 0.3\)，满足要求（第 1 步算两次函数值，之后每步只算一次）。
斐波那契数列法¶
黄金分割法每步用同一个 \(\rho\)；若允许每步使用不同的 \(\rho_k\)，复用条件变为
\(N\) 步后的总压缩比为 \((1 - \rho_1)(1 - \rho_2) \cdots (1 - \rho_N)\)。把"总压缩比最小"本身当成一个优化问题求解，最优参数序列由斐波那契数列（\(F_{-1} = F_0 = 1\)，\(F_{k+1} = F_k + F_{k-1}\)，即 \(1, 1, 2, 3, 5, 8, 13, 21, \dots\)）给出：
在"只比较函数值"的方法中这是理论最优，优于黄金分割法的 \(0.618^N\)。
最后一步的小修正
\(\rho_N = 1 - F_1 / F_2 = 1/2\) 会使两个试探点重合、无法压缩。实操中取 \(\rho_N = \frac{1}{2} - \varepsilon\)（\(\varepsilon\) 为很小的正数），总压缩比相应变为 \(\dfrac{1 + 2\varepsilon}{F_{N+1}}\)。
例：斐波那契数列法压缩区间
同前例：\(f(x) = x^4 - 14x^3 + 60x^2 - 70x\)，\([0, 2]\)，目标长度 \(0.3\)。
解答
确定迭代次数：\(\dfrac{1 + 2\varepsilon}{F_{N+1}} \le \dfrac{0.3}{2} = 0.15\)，取 \(\varepsilon < 0.1\) 时 \(F_{N+1} \ge 8\)，即 \(N = 4\)。参数序列：
| \(k\) | \(\rho_k\) | 当前区间 | 新试探点与函数值 | 新区间 |
|---|---|---|---|---|
| 1 | 0.375 | \([0, 2]\) | \(a_1 = 0.75\ (f = -24.34)\)，\(b_1 = 1.25\ (f = -18.65)\) | \([0, 1.25]\) |
| 2 | 0.4 | \([0, 1.25]\) | \(a_2 = 0.5\ (f = -21.69)\)，复用 \(b_2 = 0.75\) | \([0.5, 1.25]\) |
| 3 | 0.333 | \([0.5, 1.25]\) | 复用 \(a_3 = 0.75\)，\(b_3 = 1\ (f = -23)\) | \([0.5, 1]\) |
| 4 | 0.45 | \([0.5, 1]\) | \(a_4 = 0.725\ (f = -24.27)\)，复用 \(b_4 = 0.75\ (f = -24.34)\) | \([0.725, 1]\) |
最终区间长度 \(0.275 < 0.3\)。
二分法¶
若 \(f\) 还是连续可微的（\(f \in \mathcal{C}^1\)），可以利用导数符号压缩区间：取中点 \(x^{(k)} = \frac{1}{2}(a_{k-1} + b_{k-1})\)，
- \(f'(x^{(k)}) > 0\)：函数在上升，极小点在左侧，新区间 \([a_{k-1}, x^{(k)}]\)；
- \(f'(x^{(k)}) < 0\)：极小点在右侧，新区间 \([x^{(k)}, b_{k-1}]\)；
- \(f'(x^{(k)}) = 0\)：\(x^{(k)}\) 即为极小点，停止。
每步压缩一半，\(N\) 步总压缩比 \((1/2)^N\)——比黄金分割和斐波那契压得更快，代价是每步要算一次导数而非函数值。
例：二分法压缩区间
同前例函数与区间，目标长度 \(0.3\)。
解答
\(f'(x) = 4x^3 - 42x^2 + 120x - 70\)。
| \(k\) | 中点 \(x^{(k)}\) | \(f'(x^{(k)})\) | 新区间 |
|---|---|---|---|
| 1 | \(1\) | \(12 > 0\) | \([0, 1]\) |
| 2 | \(0.5\) | \(-20 < 0\) | \([0.5, 1]\) |
| 3 | \(0.75\) | \(-1.94 < 0\) | \([0.75, 1]\) |
3 步后区间长度 \(0.25 < 0.3\)（黄金分割需要 4 步）。
牛顿法（一维）¶
设 \(f \in \mathcal{C}^2\)。在当前点 \(x^{(k)}\) 处用二阶泰勒展开构造二次拟合函数
它与 \(f\) 在 \(x^{(k)}\) 处函数值、一二阶导数全部相同。用 \(q\) 的极小点（驻点）作为下一个迭代点：令 \(q'(x) = 0\) 得
例：牛顿法求极小点
用牛顿法求 \(f(x) = \frac{1}{2} x^2 - \sin x\) 的极小点，初始点 \(x^{(0)} = 0.5\)，停止条件 \(|x^{(k+1)} - x^{(k)}| < \varepsilon = 10^{-5}\)。
解答
\(f'(x) = x - \cos x\)，\(f''(x) = 1 + \sin x\)。迭代：
| \(k\) | \(x^{(k)}\) | \(\lvert x^{(k)} - x^{(k-1)} \rvert\) |
|---|---|---|
| 1 | \(0.7552\) | \(0.2552\) |
| 2 | \(0.7391\) | \(0.0161\) |
| 3 | \(0.7390\) | \(10^{-4}\) |
| 4 | \(0.7390\) | \(< 10^{-5}\)，停止 |
校验：\(f'(x^{(4)}) \approx -8.6 \times 10^{-6} \approx 0\)，\(f''(x^{(4)}) = 1.673 > 0\)，满足二阶充分条件，\(x^* \approx 0.739\) 是严格局部极小点。仅 4 步就达到 \(10^{-5}\) 精度——远快于区间压缩类方法。
与方程求根的关系：牛顿法本质是不断把 \(f'\) 逼向零。令 \(g(x) = f'(x)\)，迭代式变为求解方程 \(g(x) = 0\) 的牛顿切线法：
即"求 \(f\) 的极小点"等价于"求 \(f' = 0\) 的根"。课件例 7.5 用它求三次方程 \(x^3 - 12.2x^2 + 7.45x + 42 = 0\) 的根，从 \(x^{(0)} = 12\) 出发 4 步收敛到 \(11.2\)。
易错点：牛顿法的失效情形
- \(f''(x) < 0\) 时方向出错：二次拟合开口朝下，驻点是拟合函数的极大点，迭代会朝极大点/远处跑。牛顿法正常工作的前提是所考虑区间内 \(f'' > 0\)；
- 初始点必须足够好：若 \(g(x^{(0)}) / g'(x^{(0)})\) 不够小（初始点离根太远），牛顿切线法可能发散。一维搜索中常先用划界法 + 区间法粗定位，再用牛顿法精化。
割线法¶
牛顿法需要二阶导数。若 \(f''\) 不可得，用相邻两点的一阶导数差商近似：
代入牛顿迭代式得割线法（需要两个初始点 \(x^{(-1)}, x^{(0)}\)）：
几何上，牛顿切线法用切线与横轴的交点更新，割线法用过两点的割线与横轴的交点更新。求根版本（\(g = f'\)）同理。课件例 7.6 用割线法解同一个三次方程，从 \(x^{(-1)} = 13\)、\(x^{(0)} = 12\) 出发 5 步收敛到 \(11.2\)，比牛顿法多一步左右，但每步省掉了二阶导数。
二次拟合视角的统一：三种方法都在"用二次函数拟合 \(f\)，取拟合函数的驻点"——
| 方法 | 拟合条件 | 初始点数 | 每步信息 |
|---|---|---|---|
| 牛顿法 | 与 \(f\) 在 \(x^{(k)}\) 处的 \(f', f''\) 相同 | 1 | \(f', f''\) |
| 割线法 | 与 \(f\) 在 \(x^{(k-1)}, x^{(k)}\) 处的 \(f'\) 相同 | 2 | \(f'\) |
| 逆抛物线插值法 | 与 \(f\) 在 \(x^{(k-2)}, x^{(k-1)}, x^{(k)}\) 处的函数值相同 | 3 | 仅 \(f\) |
划界法¶
区间压缩类方法需要先有一个含极小点的初始区间，找区间的方法称为划界法。原理：对单峰函数，只要找到三点 \(a < c < b\) 满足
极小点必在 \([a, b]\) 内（中间低、两头高，谷底被"框"住了）。
做法：任取 \(x_0 < x_1 < x_2\)。若 \(f(x_1)\) 已是三者最小，完成；若 \(f(x_0) > f(x_1) > f(x_2)\)（一路下坡），向右取新点 \(x_3 > x_2\) 继续探，直到函数值回升；一路上坡则反向搜索。新点与前一点的距离应逐步放大（例如倍增）以快速圈住谷底。
衔接技巧：若后续用黄金分割法，划界时按扩展倍数 \(2 - \rho \approx 1.618\) 取新点，即 \(x_k = x_{k-1} + (2 - \rho)(x_{k-1} - x_{k-2})\)，则划界结束时中间点恰好就是黄金分割的一个试探点，可省去一次函数值计算。
多维优化中的一维搜索（步长选择）¶
多维迭代算法的通用格式为
\(\boldsymbol{d}^{(k)}\) 是搜索方向，步长 \(\alpha_k \ge 0\) 通过极小化一元函数
确定。由链式法则（本章所有方法都可直接套用）：
精确搜索不划算：精确极小化 \(\phi_k\) 计算量大（极小值甚至可能不存在），实践经验是把计算资源留给外层多维算法，步长只需"足够好"——核心是不太大也不太小。
非精确步长条件（Armijo / Goldstein / Wolfe）
取常数 \(\varepsilon \in (0, 1)\)，\(\gamma > 1\)，\(\eta \in (\varepsilon, 1)\)。注意下降方向上 \(\phi_k'(0) < 0\)：
| 条件 | 不等式 | 作用 |
|---|---|---|
| Armijo ① | \(\phi_k(\alpha_k) \le \phi_k(0) + \varepsilon \alpha_k \phi_k'(0)\) | 充分下降，防 \(\alpha_k\) 太大 |
| Armijo ② | \(\phi_k(\gamma \alpha_k) \ge \phi_k(0) + \varepsilon \gamma \alpha_k \phi_k'(0)\) | 放大 \(\gamma\) 倍就不达标，防 \(\alpha_k\) 太小 |
| Goldstein（替代②） | \(\phi_k(\alpha_k) \ge \phi_k(0) + \eta \alpha_k \phi_k'(0)\) | 防太小；①+③合称 Armijo–Goldstein 条件 |
| Wolfe（曲率条件） | \(\phi_k'(\alpha_k) \ge \eta\, \phi_k'(0)\) | 用导数防太小（走到坡度足够平缓处） |
| 强 Wolfe | \(\lvert \phi_k'(\alpha_k) \rvert \le \eta\, \lvert \phi_k'(0) \rvert\) | 进一步排除冲过头的点 |
算法步骤（Armijo 回溯法，最常用的实现）
- 选定初始步长候选 \(\alpha^{(0)}\)、缩小系数 \(\tau \in (0, 1)\)（通常 \(\tau = 0.5\)）；
- 检验 Armijo 条件①：满足则接受当前步长，停止；
- 不满足则令 \(\alpha \leftarrow \tau \alpha\)，回到第 2 步。\(m\) 次回溯后步长为 \(\alpha_k = \tau^m \alpha^{(0)}\)。
从较大候选值开始只缩不放，天然防止步长太小，因此实践中常只检验条件①。
速查表¶
方法对比：
| 方法 | 前提 | 每步计算 | \(N\) 步压缩比 / 特点 |
|---|---|---|---|
| 黄金分割法 | 单峰 | 1 次 \(f\) | \(0.618^N\)，实现最简单 |
| 斐波那契数列法 | 单峰 | 1 次 \(f\) | \((1 + 2\varepsilon)/F_{N+1}\)，函数值类最优 |
| 二分法 | 单峰、\(\mathcal{C}^1\) | 1 次 \(f'\) | \((1/2)^N\)，压缩最快的区间法 |
| 牛顿法 | \(\mathcal{C}^2\)、\(f'' > 0\)、初值近 | \(f'\) 与 \(f''\) 各 1 次 | 点迭代，收敛极快但可能失效 |
| 割线法 | \(\mathcal{C}^1\)、两个初值 | 1 次 \(f'\) | 免二阶导数的牛顿法 |
| 划界法 | 单峰 | 若干次 \(f\) | 不求解，只负责圈出初始区间 |
易错点：
- 区间压缩类方法的全部理论建立在单峰之上；多峰函数上得到的只是某个局部极小点所在区间；
- 黄金分割的 \(\rho \approx 0.382\) 是试探点离端点的比例，每步留下的长度是 \(1 - \rho \approx 0.618\)，两者不要记混；
- 斐波那契法最后一步必须做 \(\rho_N = \frac{1}{2} - \varepsilon\) 修正，否则两试探点重合；
- 牛顿法迭代式分母是 \(f''\)：在 \(f'' < 0\) 区域它会朝极大点走，失效不是"慢"而是"方向错"；
- Armijo 条件中 \(\phi_k'(0) = \boldsymbol{d}^\top \nabla f < 0\)（下降方向），所以右端的"下降配额"是负的——步长越大要求降得越多。