====== 第三章 一维搜索方法 ======

===== 本章导读 =====

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

===== 3.1 一维搜索问题 =====

==== 3.1.1 问题描述 ====

**定义 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.1.2 单峰函数 ====

**定义 3.2**（单峰函数）

设 $\phi(\alpha)$ 在区间 $[a, b]$ 上连续。若存在 $\alpha^* \in [a, b]$ 使得：
  - 当 $\alpha \leq \alpha^*$ 时，$\phi(\alpha)$ 严格单调递减
  - 当 $\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$：
  - 若 $\phi(c) \leq \phi(d)$，则 $\alpha^* \in [a, d]$
  - 若 $\phi(c) > \phi(d)$，则 $\alpha^* \in [c, b]$

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

===== 3.2 黄金分割法 =====

==== 3.2.1 算法思想 ====

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

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

==== 3.2.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.2.3 算法步骤 ====

**算法 3.1**（黄金分割法）

  - **输入**：函数 $\phi(\alpha)$，区间 $[a, b]$，精度 $\varepsilon > 0$
  - **输出**：近似最优解 $\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$
  - $c = 5 - 0.618 \times 5 = 1.91$，$\phi(c) = 1.828$
  - $d = 0 + 0.618 \times 5 = 3.09$，$\phi(d) = 2.088$

迭代过程：
| 迭代 | $a$ | $b$ | $c$ | $d$ | $\phi(c)$ | $\phi(d)$ |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 0 | 0 | 5 | 1.91 | 3.09 | 1.828 | 2.088 |
| 1 | 0 | 3.09 | 1.18 | 1.91 | 1.032 | 1.828 |
| 2 | 0 | 1.91 | 0.73 | 1.18 | 1.073 | 1.032 |
| 3 | 0.73 | 1.91 | 1.18 | 1.46 | 1.032 | 1.212 |
| 4 | 0.73 | 1.46 | 1.01 | 1.18 | 1.000 | 1.032 |
| 5 | 0.73 | 1.18 | - | - | - | - |

区间长度 $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法 =====

==== 3.3.1 Fibonacci数列 ====

**定义 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$（黄金分割比）

==== 3.3.2 算法原理 ====

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

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

==== 3.3.3 算法步骤 ====

**算法 3.2**（Fibonacci法）

  - **输入**：函数 $\phi(\alpha)$，区间 $[a, b]$，迭代次数 $n$
  - **输出**：近似最优解 $\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 黄金分割法**：
  - Fibonacci法在固定迭代次数下最优
  - 黄金分割法是Fibonacci法的极限情况（$n \rightarrow \infty$）
  - 实际中两者效果接近，黄金分割法更简单

===== 3.4 插值法 =====

==== 3.4.1 二次插值法 ====

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

设已知三点 $\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.4.2 二次插值算法 ====

**算法 3.3**（二次插值法）

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

  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$

==== 3.4.3 三次插值法 ====

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

设已知 $\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)}$$

===== 3.5 不精确一维搜索 =====

==== 3.5.1 Wolfe条件 ====

精确一维搜索计算代价高，实际中常用不精确搜索。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.5.2 Armijo回溯法 ====

**算法 3.4**（Armijo回溯线搜索）

  - **输入**：函数 $f$、当前点 $\mathbf{x}$、方向 $\mathbf{d}$、参数 $\bar{\alpha} > 0$，$\rho \in (0, 1)$，$c \in (0, 1)$
  - **输出**：步长 $\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$

===== 3.6 方法比较与选择 =====

| 方法 | 需要信息 | 收敛速度 | 适用范围 |
|:---:|:---:|:---:|:---:|
| 黄金分割法 | 函数值 | 线性 | 单峰函数 |
| Fibonacci法 | 函数值 | 最优（固定次数） | 单峰函数 |
| 二次插值 | 3个函数值 | 超线性 | 光滑函数 |
| 三次插值 | 2点函数值+导数 | 二阶 | 光滑可导函数 |
| 不精确搜索 | 函数值+导数 | - | 多维优化 |

**选择建议**：
  - 函数求值昂贵：用Fibonacci法或插值法
  - 需要导数信息：用三次插值或Wolfe条件
  - 多维优化：用不精确一维搜索

===== 3.7 例题详解 =====

**例 3.2**

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

**解**：

取初始点 $\alpha_1 = 0, \alpha_2 = 1, \alpha_3 = 2$：
  - $\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$。

===== 3.8 习题 =====

**理论题**

1. 证明：若 $\phi(\alpha)$ 在 $[a, b]$ 上单峰，$c < d$，且 $\phi(c) \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函数一维化的效率。

---

*本章完*