第三章 一维搜索方法

一维搜索（Line Search）是多维优化算法的基础组成部分。在多维优化中，每次迭代需要确定沿某一方向的步长，这本质上是一个一维优化问题。本章介绍几种经典的一维搜索方法：黄金分割法、Fibonacci法和插值法。

定义 3.1（一维搜索问题）

给定函数 $\phi: \mathbb{R} \rightarrow \mathbb{R}$，求： $$\alpha^* = \arg\min_{\alpha \in [a, b]} \phi(\alpha)$$

或 $$\alpha^* = \arg\min_{\alpha > 0} \phi(\alpha)$$

在实际应用中，一维搜索通常用于确定多维优化算法中的步长： $$\alpha_k = \arg\min_{\alpha > 0} f(\mathbf{x}_k + \alpha \mathbf{d}_k)$$

定义 3.2（单峰函数）

设 $\phi(\alpha)$ 在区间 $[a, b]$ 上连续。若存在 $\alpha^* \in [a, b]$ 使得：

1. 当 $\alpha \leq \alpha^*$ 时，$\phi(\alpha)$ 严格单调递减
2. 当 $\alpha \geq \alpha^*$ 时，$\phi(\alpha)$ 严格单调递增

则称 $\phi(\alpha)$ 在 $[a, b]$ 上是单峰函数。

定理 3.1

若 $\phi(\alpha)$ 在 $[a, b]$ 上单峰，则 $\alpha^*$ 是唯一的全局极小点。

单峰函数的重要性质：

设 $\phi(\alpha)$ 在 $[a, b]$ 上单峰，任取 $c, d \in [a, b]$ 且 $c < d$：

1. 若 $\phi© \leq \phi(d)$，则 $\alpha^* \in [a, d]$
2. 若 $\phi© > \phi(d)$，则 $\alpha^* \in [c, b]$

这一性质是区间消去法的基础。

黄金分割法（Golden Section Search）是一种区间消去法，通过不断缩小包含极小点的区间来逼近最优解。

基本思想： 1. 在区间 $[a, b]$ 内选取两个对称点 $c$ 和 $d$ 2. 比较 $\phi©$ 和 $\phi(d)$，利用单峰函数性质消去一部分区间 3. 重复上述过程直到区间足够小

为了提高效率，我们希望每次迭代：

1. 只计算一个新点的函数值
2. 区间缩小比例相同

设区间 $[a, b]$ 长度为 $L$，取点 $c, d$ 使得 $ac = db = \tau L$，$cd = (1-2\tau)L$。

消去区间后，新区间长度为 $(1-\tau)L$。为使缩小比例恒定，要求： $$\frac{\tau}{1-\tau} = 1-\tau$$

解得：$\tau^2 - 3\tau + 1 = 0$，即 $\tau = \frac{3 - \sqrt{5}}{2} \approx 0.382$。

黄金分割比：$r = \frac{\sqrt{5}-1}{2} \approx 0.618$（即 $1-\tau$）

算法 3.1（黄金分割法）

1. 输入：函数 $\phi(\alpha)$，区间 $[a, b]$，精度 $\varepsilon > 0$
2. 输出：近似最优解 $\alpha^*$

1. 计算 $r = \frac{\sqrt{5}-1}{2} \approx 0.618$
2. 令 $c = b - r(b-a)$，$d = a + r(b-a)$
3. 计算 $\phi_c = \phi(c)$，$\phi_d = \phi(d)$
4. **while** $b - a > \varepsilon$ **do**
   - **if** $\phi_c \leq \phi_d$ **then**
     - $b = d$，$d = c$，$\phi_d = \phi_c$
     - $c = b - r(b-a)$，$\phi_c = \phi(c)$
   - **else**
     - $a = c$，$c = d$，$\phi_c = \phi_d$
     - $d = a + r(b-a)$，$\phi_d = \phi(d)$
5. **return** $\frac{a+b}{2}$

例 3.1

用黄金分割法求 $\phi(\alpha) = \alpha^2 - 4\alpha + 5$ 在 $[0, 5]$ 上的极小点，精度 $\varepsilon = 0.1$。

解：

初始：$a = 0, b = 5, r = 0.618$

1. $c = 5 - 0.618 \times 5 = 1.91$，$\phi© = 1.828$
2. $d = 0 + 0.618 \times 5 = 3.09$，$\phi(d) = 2.088$

迭代过程：

区间长度 $0.45 < \varepsilon$，停止。近似解 $\alpha^* \approx \frac{0.73+1.18}{2} = 0.955$。

真解 $\alpha^* = 2$，但由于 $\phi(\alpha) = (\alpha-2)^2 + 1$，在 $[0,5]$ 边界处取最小。实际上 $a \rightarrow 0$ 时最优。

定理 3.2（收敛性）

黄金分割法产生的区间序列 $\{[a_k, b_k]\}$ 满足： $$b_k - a_k = r^{k-1}(b_1 - a_1)$$

其中 $r = \frac{\sqrt{5}-1}{2} \approx 0.618$。

经过 $n$ 次迭代后，区间长度缩小为初始的 $r^{n-1}$ 倍。

定义 3.3（Fibonacci数列）

Fibonacci数列 $\{F_n\}$ 定义为： $$F_0 = F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}, \quad n \geq 2$$

数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

性质：$\lim_{n \rightarrow \infty} \frac{F_{n-1}}{F_n} = \frac{\sqrt{5}-1}{2} = r$（黄金分割比）

Fibonacci法也是区间消去法，但每步的缩小区间比例不同，基于Fibonacci数列。

对于 $n$ 次函数求值，最优的区间缩小策略使得： $$\frac{\text{最终区间长度}}{\text{初始区间长度}} = \frac{1}{F_n}$$

算法 3.2（Fibonacci法）

1. 输入：函数 $\phi(\alpha)$，区间 $[a, b]$，迭代次数 $n$
2. 输出：近似最优解 $\alpha^*$

1. 计算Fibonacci数列 $F_0, F_1, \ldots, F_n$
2. 令 $k = n$，$\rho = 1 - \frac{F_{k-1}}{F_k}$
3. $c = a + \rho(b-a)$，$d = b - \rho(b-a)$
4. 计算 $\phi_c = \phi(c)$，$\phi_d = \phi(d)$
5. **for** $k = n-1, n-2, \ldots, 2$ **do**
   - **if** $\phi_c \leq \phi_d$ **then**
     - $b = d$，$d = c$，$\phi_d = \phi_c$
     - $\rho = 1 - \frac{F_{k-1}}{F_k}$
     - $c = a + \rho(b-a)$，$\phi_c = \phi(c)$
   - **else**
     - $a = c$，$c = d$，$\phi_c = \phi_d$
     - $\rho = 1 - \frac{F_{k-1}}{F_k}$
     - $d = b - \rho(b-a)$，$\phi_d = \phi(d)$
6. **return** $\frac{a+b}{2}$

注：最后一步通常令 $c = d = \frac{a+b}{2}$ 以充分利用最后一次函数求值。

定理 3.3

Fibonacci法在 $n$ 次函数求值后，区间长度缩小为初始的 $\frac{1}{F_n}$。

Fibonacci法 vs 黄金分割法：

1. Fibonacci法在固定迭代次数下最优
2. 黄金分割法是Fibonacci法的极限情况（$n \rightarrow \infty$）
3. 实际中两者效果接近，黄金分割法更简单

基本思想：用二次多项式近似目标函数，求二次函数的极小点作为新的迭代点。

设已知三点 $\alpha_1 < \alpha_2 < \alpha_3$，对应的函数值 $\phi_1, \phi_2, \phi_3$。

过这三点的二次插值多项式为： $$p(\alpha) = a\alpha^2 + b\alpha + c$$

由插值条件 $p(\alpha_i) = \phi_i$，$i = 1, 2, 3$，解得： $$p(\alpha) = \phi_1 \frac{(\alpha-\alpha_2)(\alpha-\alpha_3)}{(\alpha_1-\alpha_2)(\alpha_1-\alpha_3)} + \phi_2 \frac{(\alpha-\alpha_1)(\alpha-\alpha_3)}{(\alpha_2-\alpha_1)(\alpha_2-\alpha_3)} + \phi_3 \frac{(\alpha-\alpha_1)(\alpha-\alpha_2)}{(\alpha_3-\alpha_1)(\alpha_3-\alpha_2)}$$

$p(\alpha)$ 的极小点为： $$\alpha^* = \frac{1}{2} \frac{\phi_1(\alpha_2^2-\alpha_3^2) + \phi_2(\alpha_3^2-\alpha_1^2) + \phi_3(\alpha_1^2-\alpha_2^2)}{\phi_1(\alpha_2-\alpha_3) + \phi_2(\alpha_3-\alpha_1) + \phi_3(\alpha_1-\alpha_2)}$$

或用差商表示： $$\alpha^* = \alpha_2 - \frac{1}{2} \frac{(\alpha_2-\alpha_1)^2(\phi_2-\phi_3) - (\alpha_2-\alpha_3)^2(\phi_2-\phi_1)}{(\alpha_2-\alpha_1)(\phi_2-\phi_3) - (\alpha_2-\alpha_3)(\phi_2-\phi_1)}$$

算法 3.3（二次插值法）

1. 输入：函数 $\phi(\alpha)$，初始三点 $\alpha_1, \alpha_2, \alpha_3$，精度 $\varepsilon$
2. 输出：近似最优解

1. 计算 $\phi_i = \phi(\alpha_i)$，$i = 1, 2, 3$
2. **while** $|\alpha_3 - \alpha_1| > \varepsilon$ **do**
   - 计算插值点 $\alpha^*$ 的公式
   - 计算 $\phi^* = \phi(\alpha^*)$
   - **if** $\alpha^* < \alpha_2$ **then**
     - **if** $\phi^* < \phi_2$ **then** $(\alpha_3, \phi_3) = (\alpha_2, \phi_2)$，$(\alpha_2, \phi_2) = (\alpha^*, \phi^*)$
     - **else** $(\alpha_1, \phi_1) = (\alpha^*, \phi^*)$
   - **else**
     - **if** $\phi^* < \phi_2$ **then** $(\alpha_1, \phi_1) = (\alpha_2, \phi_2)$，$(\alpha_2, \phi_2) = (\alpha^*, \phi^*)$
     - **else** $(\alpha_3, \phi_3) = (\alpha^*, \phi^*)$
3. **return** $\alpha_2$

若函数可导，可用两点及其导数值构造三次插值多项式，收敛更快。

设已知 $\alpha_1, \alpha_2$ 及 $\phi(\alpha_1), \phi'(\alpha_1), \phi(\alpha_2), \phi'(\alpha_2)$。

三次Hermite插值多项式的极小点： $$\alpha^* = \alpha_1 + (\alpha_2-\alpha_1)\left(1 - \frac{\phi'(\alpha_2) + w - z}{\phi'(\alpha_2) - \phi'(\alpha_1) + 2w}\right)$$

其中： $$s = \frac{3(\phi(\alpha_2)-\phi(\alpha_1))}{\alpha_2-\alpha_1}, \quad z = s - \phi'(\alpha_1) - \phi'(\alpha_2), \quad w = \sqrt{z^2 - \phi'(\alpha_1)\phi'(\alpha_2)}$$

精确一维搜索计算代价高，实际中常用不精确搜索。Wolfe条件是最常用的准则。

Armijo条件（充分下降条件）： $$\phi(\alpha) \leq \phi(0) + c_1 \alpha \phi'(0), \quad c_1 \in (0, 1)$$

曲率条件： $$\phi'(\alpha) \geq c_2 \phi'(0), \quad c_2 \in (c_1, 1)$$

强Wolfe条件： $$|\phi'(\alpha)| \leq c_2 |\phi'(0)|$$

定理 3.4

若 $\phi$ 有下界且 $0 < c_1 < c_2 < 1$，则存在满足Wolfe条件的步长。

算法 3.4（Armijo回溯线搜索）

1. 输入：函数 $f$、当前点 $\mathbf{x}$、方向 $\mathbf{d}$、参数 $\bar{\alpha} > 0$，$\rho \in (0, 1)$，$c \in (0, 1)$
2. 输出：步长 $\alpha$

1. $\alpha = \bar{\alpha}$
2. **while** $f(\mathbf{x} + \alpha \mathbf{d}) > f(\mathbf{x}) + c \alpha \nabla f(\mathbf{x})^T \mathbf{d}$ **do**
   - $\alpha = \rho \alpha$
3. **return** $\alpha$

选择建议：

1. 函数求值昂贵：用Fibonacci法或插值法
2. 需要导数信息：用三次插值或Wolfe条件
3. 多维优化：用不精确一维搜索

例 3.2

用二次插值法求 $\phi(\alpha) = \alpha^3 - 2\alpha + 1$ 在 $[0, 2]$ 上的极小点。

解：

取初始点 $\alpha_1 = 0, \alpha_2 = 1, \alpha_3 = 2$：

1. $\phi(0) = 1$，$\phi(1) = 0$，$\phi(2) = 5$

计算插值点： $$\alpha^* = \frac{1}{2} \frac{1(1-4) + 0(4-0) + 5(0-1)}{1(1-2) + 0(2-0) + 5(0-1)} = \frac{1}{2} \frac{-3 - 5}{-1 - 5} = \frac{2}{3}$$

$\phi(2/3) = -0.185$，是最小的。更新点集，继续迭代收敛到 $\alpha^* = \sqrt{2/3} \approx 0.816$。

理论题

1. 证明：若 $\phi(\alpha)$ 在 $[a, b]$ 上单峰，$c < d$，且 $\phi© \leq \phi(d)$，则极小点 $\alpha^* \in [a, d]$。

2. 证明Fibonacci数列满足：$\lim_{n \rightarrow \infty} \frac{F_{n-1}}{F_n} = \frac{\sqrt{5}-1}{2}$。

3. 解释为什么黄金分割法每次迭代只需计算一个新点的函数值。

4. 证明：若 $\phi$ 是凸函数，则二次插值多项式的极小点在三点构成的区间内。

计算题

5. 用黄金分割法求 $\phi(\alpha) = (\alpha-3)^2$ 在 $[0, 5]$ 上的极小点，精度 $\varepsilon = 0.01$。

6. 用Fibonacci法（$n=6$）求 $\phi(\alpha) = e^{-\alpha} + \alpha^2$ 在 $[0, 2]$ 上的极小点。

7. 用二次插值法求 $\phi(\alpha) = \alpha^4 - 4\alpha^2 + 4$ 在 $[0, 3]$ 上的极小点。

应用题

8. 设 $f(x, y) = x^2 + 2y^2$，当前点 $(1, 1)$，下降方向 $(-1, -2)$。用精确一维搜索求最优步长。

9. 编写程序实现黄金分割法和二次插值法，比较它们求解Rosenbrock函数一维化的效率。

—

*本章完*