一维搜索法

一、迭代法概述

1.迭代法

考虑求解这个无约束优化问题：$\min _{\boldsymbol{x} \in \mathbb{R}^{n}} f(\boldsymbol{x})$

选取初始点 $x^{0} \in \mathbb{R}^{n}$ ，按一定规则（迭代规则）产生点列 $x^{1}, x^{2}, \cdots, x^{k}$ ，记为 ${\boldsymbol{x}^{k}}$ ，使得 $\boldsymbol{x}^{k}$ 恰好是优化问题的一个最优解，或该点列 ${\boldsymbol{x}^{k}}$ 收敛到优化问题的一个最优解。

迭代的定义：
1．在 $x^{k}$ 处确定一个方向 $\boldsymbol{d}^{k}$ ；
2．然后确定沿着射线 $\boldsymbol{x}=\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}(\alpha>0)$ 走多远，即确定一个步长 $\alpha{k}$ ，从而得到新迭代点$\boldsymbol{x}^{k+1}=\boldsymbol{x}^{k}+\alpha{k} \boldsymbol{d}^{k}$ 。

通常希望： $f(\boldsymbol{x}^{k+1}) \leq f(\boldsymbol{x}^{k})$ 。

2.下降方向$\boldsymbol{d}^{k}$的确定

在点 $x^{k}$ 处，若对于方向 $p^{k} \neq 0$ ，存在实数 $\delta>0$ ，使得对任意的 $\alpha \in(0, \delta)$ 有：$f(\boldsymbol{x}^{k}+\alpha \boldsymbol{p}^{k})<f(\boldsymbol{x}^{k})$成立，则称 $\boldsymbol{p}^{k}$ 为函数 $f(\boldsymbol{x})$ 在点 $\boldsymbol{x}^{k}$ 处的一个下降方向。

设函数 $f: \Omega \subseteq \mathbb{R}^{n} \rightarrow \mathbb{R}$ 在点 $\boldsymbol{x}^{k}$ 处一阶可导， $\boldsymbol{p} \in \mathbb{R}^{n}$ 为 $n$ 维非零向量，如果满足$\nabla f(\boldsymbol{x}^{k})^{\mathrm{T}} \boldsymbol{p}<0$，则 $p$ 为函数 $f(x)$ 在点 $x^{k}$ 处的一个下降方向。

3.最优步长$\alpha_{k}$的确定

确定了搜索方向 $\boldsymbol{d}^{k}$ 后，下一步就要确定步长 $\alpha_{k}$ ，常见的方法有 3 种：

1. 固定步长法：将步长 $\alpha{k}$ 固定为一常数（例如令 $\alpha{k}=1$ ）。（固定步长法无法保证目标函数值下降。）
2. 可接受步长法：在能够保证目标函数值下降或整体下降的前提下，步长 $\alpha_{k}$ 可任意选取。
3. （精确）一维搜索或（精确）线搜索：沿搜索方向使目标函数值下降最多，即沿射线 $\boldsymbol{x}=\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}(\alpha>0)$ 求目标函数 $f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k})$ 的极小点。

具体而言，（精确）一维搜索或（精确）线搜索在确定步长 $\alpha{k}$ 时， $\alpha{k}>0$ 通常满足：$f(\boldsymbol{x}^{k}+\alpha{k} \boldsymbol{d}^{k})=\min {\alpha>0} f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k})$ 或 $\alpha{k}=\arg \min {\alpha>0} f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k})$，即选择一个能够使目标函数值下降最多的步长，简称最优步长。这其实就是求单变量函数（一元函数）极小点的问题：$\min {\alpha>0} f(\boldsymbol{x}^{k}+\alpha \boldsymbol{d}^{k}) \Leftrightarrow \min {\alpha>0} f(\alpha)$。

4.迭代法步骤

给定初始点 $\boldsymbol{x}^{0}$ ，令 $k=0$

1. 确定 $\boldsymbol{x}^{k}$ 处的下降方向 $\boldsymbol{d}^{k}$ ；
2. 确定步长 $\alpha{k}>0$ 使得目标函数值下降，也即：$f(\boldsymbol{x}^{k}+\alpha{k} \boldsymbol{d}^{k}) \leq f(\boldsymbol{x}^{k})$；
3. 令 $\boldsymbol{x}^{k+1}=\boldsymbol{x}^{k}+\alpha_{k} \boldsymbol{d}^{k}$ ；
4. 若 $x^{k+1}$ 满足终止准则，停止迭代；否则令 $k=k+1$ ，转 Step 1。

5.迭代算法的评判

收敛性

• 算法收敛：存在正整数 $N$ 满足： $\boldsymbol{x}^{N}=\boldsymbol{x}^{}$ 或 $\lim _{k \rightarrow+\infty} \boldsymbol{x}^{k}=\boldsymbol{x}^{}$ 。
• 局部收敛：存在 $\boldsymbol{x}^{}$ 的某邻域 $N_{\delta}(\boldsymbol{x}^{})$ ，使得仅当 $\boldsymbol{x}^{0} \in N_{\delta}(\boldsymbol{x}^{})$ 时，算法产生的点列 ${x^{k}}$ 才收敛于 $x^{}$ ，称该算法具有局部收敛性质。
• 全局收敛：在定义域内任取初值 $\boldsymbol{x}^{0}$ ，由算法产生的点列 ${\boldsymbol{x}^{k}}$ 都收敛于 $x^{*}$ ，称该算法具有全局收敛性质。

收敛速度

线性收敛：
设 $\boldsymbol{x}^{}$ 为问题 $\min f(\boldsymbol{x})$, $\boldsymbol{x} \in \mathbb{R}^{n}$ 的最优解。由算法 $A$ 产生的序列 ${\boldsymbol{x}^{k}}$ 收敛于 $\boldsymbol{x}^{}$ ，即 $\lim {k \rightarrow+\infty} x^{k}=x^{*}$如果存在一个与 $k$ 无关的常数 $\beta \in(0,1)$ 以及某个正整数 $k{0}$ ，使得当 $k \geq k{0}$ 时，有$|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{*}|{2} \leq \beta|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}|_{2}$成立，则称序列 ${\boldsymbol{x}^{k}}$ 线性收敛，或称算法 $A$ 是线性收敛的。

不失一般性，可以假设上式对于任意 $k \geq 0$ 都成立，于是有：

$$\|x^{k}-x^{*}\|_{2} \leq \beta\|x^{k-1}-x^{*}\|_{2} \leq \beta^{2}\|x^{k-2}-x^{*}\|_{2} \leq \cdots \leq \beta^{k}\|x^{0}-x^{*}\|_{2}$$

即 $\lim {k \rightarrow+\infty}|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}|{2}=0$ 。当 $k \rightarrow \infty$ 时，点 $x^{k}$ 到 $x^{*}$ 的距离，大致以公比为 $\beta$ 的等比序列（几何序列）减小，因此线性收敛速度相当于相应的等比数列的收敛速度。

p 阶收敛：设由算法 $A$ 产生的序列 ${\boldsymbol{x}^{k}}$ 收敛于 $\boldsymbol{x}^{}$ 。如果存在一个与 $k$ 无关的常数 $\beta>0$ 和 $p>1$ ，及某个正整数 $k{0}$ ，使得当 $k \geq k{0}$ 时，$|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{}|{2} \leq \beta|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}|{2}^{p}$成立，则称序列 ${\boldsymbol{x}^{k}}$ 为 p 阶收敛的，或称序列 ${\boldsymbol{x}^{k}}$ 的收敛阶为 p ，或称算法 $A$ 是 p 阶收敛的。

• 当 1<p<2 时，则称序列 ${\boldsymbol{x}^{k}}$ 为超线性收玫的。
• 当 p=2 时，则称序列 ${\boldsymbol{x}^{k}}$ 为二阶收敛的。
• 该定义中，数值解与最优解间的差异性用范数 $|\cdot|{2}$ 来刻画。可将 $|\cdot|{2}$ 理解为数值解与最优解间的距离。

终止准则
假设算法 A 产生的序列 ${\boldsymbol{x}^{k}}$ 收敛于最优解 $\boldsymbol{x}^{*}$ 。那么，算法何时停止迭代？

若算法可以收敛，则当 $|\boldsymbol{x}^{k}-\boldsymbol{x}^{*}|{2}$ 较小时， $|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{k}|{2}$ 也较小。所以终止准则通常取为： $|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{k}|{2} \leq \epsilon{1}$ 或 $|\boldsymbol{x}^{k+1}-\boldsymbol{x}^{k}|{2} \leq \epsilon{1}^{\prime}|\boldsymbol{x}^{k}|{2}$ 。其他终止条件如：$|f(\boldsymbol{x}^{k+1})-f(\boldsymbol{x}^{k})| \leq \epsilon{2}$ 或 $|f(\boldsymbol{x}^{k+1})-f(\boldsymbol{x}^{k})| \leq \epsilon{2}^{\prime}|f(\boldsymbol{x}^{k})|$ 。
另外若函数一阶可导，通常可采取： $|\nabla f(\boldsymbol{x}^{k})|{2} \leq \epsilon_{3}$ 。

二、一维搜索方法（线搜索方法）

1.解析法

若目标函数一维可导，通常采用解析法求解最优步长$\alpha_{k}$，即令$\frac{d f(x)}{d x}=0$。

2.数值法

在进行最优解的计算前，先要进行搜索区间的确定。

搜索区间：设 $f(x)$ 是定义在一元空间上的函数，$x^{}=\arg \min _{x} f(x)$ 。若存在区间 $[a, b]$ 使得 $x^{} \in(a, b)$ ，则称 $[a, b]$ 为一维搜索问题的搜索空间。

单谷函数：若 $x^{}$ 使得 $f(x)$ 在区间 $[a, x^{}]$ 上严格递减，并且在区间 $[x^{*}, b]$ 上严格递增，则称 $f(x)$ 为搜索区间 $[a, b]$ 上的单谷函数。

方法1：
设单谷函数 $f(x)$ 在某定义域内一阶连续可导，则可按如下方法确定初始搜索区间：

1. 任意选一个初始点 $x_{0}$ 以及步长 $\Delta x$ ；
2. 若 $f^{\prime}(x{0})<0$ ，则极小点位于 $x{0}$ 的右侧，那么令 $x{1}=x{0}+\Delta x$ ：
   • 若 $f^{\prime}(x{1})>0$ ，则令 $[a, b]=[x{0}, x_{1}]$ 。
   • 若 $f^{\prime}(x{1})<0$ ，则令 $x{0}=x_{1}$ ，返回 Step 2 。
3. 若 $f^{\prime}(x_{0})>0$ ，则作类似于 Step 2 的情况去讨论。

方法2（进退法）（无需计算导数）：
给定初始点 $x_{1}$ ，初始步长 $\Delta x>0$

1. $x{2}=x{1}+\Delta x$ ，计算 $f(x{1})$ 、 $f(x{2})$ ，若 $f(x{1}) \geq f(x{2})$ ，则转 Step 2；否则，转 Step 3；
2. 令 $\Delta x=2 \Delta x， x{3}=x{2}+\Delta x$ ，计算 $f(x{3})$ 。若 $f(x{2}) \leq f(x{3})$ ，则得区间 $[x{1}, x{3}]$ 为初始区间，停止搜索；若 $f(x{2})>f(x{3})$ ，则令 $x{1}=x{2}， x{2}=x_{3}$ ，转 Step 2。
3. 令 $x{3}=x{2}$，$x{2}=x{1}$，$\Delta x=2 \Delta x$，$x{1}=x{2}-\Delta x$ ，计算 $f(x{1})$ 。若 $f(x{1}) \geq f(x{2})$ ，则取 $[x{1}, x{3}]$ 为初始区间，停止搜索；若 $f(x{1})<f(x_{2})$ ，转 Step 3。

得到初始搜索区间后，可以采用试探法或函数逼近法进一步求解最优步长。

(1)试探法

基本思想：从一个包含极小点的初始区间 $[a, b]$ 开始，按照一定规则往区间内放入试探点，通过比较试探点与区间端点的函数值或导数值，不断缩短包含极小点的搜索区间。当区间长度缩小到一定程度 (达到误差精度要求)，那么区间上任意一点都可以作为极小点的近似。通常取最终区间的中点作为近似极小点。

①二分法

基本思想：
设 $f(x)$ 为单谷函数且在 $[a{k}, b{k}]$ 内一阶连续可导，且 $f^{\prime}(a{k})<0$ ， $f^{\prime}(b{k})>0$ 。
取 $c{k}=\frac{(a{k}+b{k})}{2}$ ，若 $f^{\prime}(c{k})=0$ ，则 $c{k}$ 为极小点；
若 $f^{\prime}(c{k})>0$ ，则令 $a{k+1}=a{k}, b{k+1}=c{k}$ ，
若 $f^{\prime}(c{k})<0$ ，则令 $a{k+1}=c{k}, b{k+1}=b_{k}$ 。
按照上述思想，逐步将初始搜索空间 $[a, b]$ 缩小，当搜索区间的长度充分小时，可将最终区间的中点取做极小点的近似点。

算法步骤：

1. 给定初始区间 $[a{1}, b{1}]$ ，满足 $f^{\prime}(a{1})<0, f^{\prime}(b{1})>0$ ，且允许误差为 $\epsilon>0$ ，令 $k=1$
2. 若 $|b{k}-a{k}| \leq \epsilon$ ，停止运算；否则，取 $c{k}=\frac{a{k}+b_{k}}{2}$ ，转 Step 3。
3. 计算 $f^{\prime}(c{k})$ 。
   若 $f^{\prime}(c{k})=0$ ，则令 $x^{*}=c{k}$ ，停止运算；
   若 $f^{\prime}(c{k})<0$ ，则令 $a_{k+1}=c_{k}, b_{k+1}=b_{k}$ ，转 Step 4； 若 $f^{\prime}(c_{k})>0$ ，则令 $a{k+1}=a{k}, b{k+1}=c{k}$ ，转 Step 4。
4. 令 $k=k+1$ ，返回 Step 2。

适用条件：二分法适用于 $f(x)$ 的导数存在且容易计算的情况下。

优点：

• 每次以搜索区间的中点作为试探点，计算量小，算法简洁易于实现；
• 总能收敛到一个局部极小点。

缺点：

• 要求目标函数至少一阶连续可导；
• 收敛速度很慢。

②黄金分割法

基本思想：
在搜索区间内 $[a{k}, b{k}]$ 取两个试探点 $\lambda{k}$，$\mu{k}$，将区间分成三段。通过比较试探点处的函数值，使搜索区间缩短；不断迭代使得包含极小点的搜索区间不断缩短，最终得到极小点或近似极小点。

算法步骤：

1. 设置初始区间 $[a{1}, b{1}]$ 和允许误差 $\epsilon>0$ ，计算试探点 $\lambda{1}=a{1}+0.382(b{1}-a{1})$， $\mu{1}=a{1}+0.618(b{1}-a{1})$ 及对应的函数值 $f(\lambda{1}), f(\mu{1})$ ，令 $k=1$ ；
2. 若 $|b{k}-a{k}| \leq \epsilon$ ，则停止运算，取 $x^{*}=\frac{a{k}+b{k}}{2}$ ；否则，当 $f(\lambda{k})>f(\mu{k})$ 时，转 Step 3；当 $f(\lambda{k}) \leq f(\mu{k})$ 时，转 Step 4；
3. 令 $[a{k+1}, b{k+1}]=[\lambda{k}, b{k}]$，$\lambda{k+1}=\mu{k}$，$f(\lambda{k+1})=f(\mu{k})$，计算 $\mu{k+1}=a{k+1}+0.618(b{k+1}-a{k+1})$ 及 $f(\mu_{k+1})$ ，转 Step 5；
4. 令 $[a{k+1}, b{k+1}]=[a{k}, \mu{k}]$，$\mu{k+1}=\lambda{k}$，$f(\mu{k+1})=f(\lambda{k})$，计算 $\lambda{k+1}=a{k+1}+0.382(b{k+1}-a{k+1})$ 及 $f(\lambda_{k+1})$ ，转 Step 5；
5. 令 $k=k+1$ ，返回 Step 2。

适用条件：黄金分割法对函数的要求较低，函数可以不连续。因为该算法仅利用函数值而非函数的导数来缩小搜索区间。

优点：

• 对函数要求低，不要求函数可微，只需要计算函数值；
• 新区间里包含原来的试探点，且该试探点在下一步被利用 (即每次只需计算一个试探点)，计算量小；
• 试探点的计算公式一致。

收敛性：
黄金分割法是线性收敛速度。

补充：为什么采用0.618作为分割比？

记当前的搜索区间为 $[a{k}, b{k}]$ ，设试探点为 $\lambda{k}$，$\mu{k}$ ，其中 $\lambda{k}<\mu{k}$ ：
若 $f(\lambda{k}) \leq f(\mu{k})$ ，则 $x^{} \in[a{k}, \mu{k}]$ ；
若 $f(\lambda{k})>f(\mu{k})$ ，则 $x^{} \in[\lambda{k}, b{k}]$ 。
那么下一个搜索区间取为 $[a{k}, \mu{k}]$ 或 $[\lambda{k}, b{k}]$ 。

为了机会均等，我们选取对称的试点，即$\mu{k}-a{k}=b{k}-\lambda{k}$。另外，要求区间缩短率相同，即$b{k+1}-a{k+1}=\rho(b{k}-a{k})$，其中 $0<\rho<1$ 为区间缩短率。

分情况讨论：
若 $f(\lambda{k}) \leq f(\mu{k})$ ，则取 $[a{k+1}, b{k+1}]=[a{k}, \mu{k}]$ ，那么：

$$\begin{aligned} \lambda_{k} & =a_{k}+(1-\rho)(b_{k}-a_{k}), \\ \mu_{k} & =a_{k}+\rho(b_{k}-a_{k}) \end{aligned}$$

同理，当 $f(\lambda{k})>f(\mu{k})$ 时，可证上两式也成立。

可见，一旦 $0<\rho<1$ 确定， $\lambda{k}$， $\mu{k}$ 便可算出。
那么 $\rho$ 应该取多少呢？

类似上一页的做法，再分情况讨论，发现
若 $f(\lambda{k}) \leq f(\mu{k})$ ，那么 $[a{k+1}, b{k+1}]=[a{k}, \mu{k}]$ ，进一步有：$\mu{k+1}=a{k+1}+\rho(b{k+1}-a{k+1})=a{k}+\rho^{2}(b{k}-a{k})$，又注意到 $\lambda{k}=a{k}+(1-\rho)(b{k}-a{k})$ 。因此，当 $\rho^{2}=1-\rho$ 时， $\mu{k+1}=\lambda{k}$ 。此时，第 $k+1$ 步无需计算 $\mu{k+1}$ 。
同理，当 $f(\lambda{k})>f(\mu{k})$ ，那么 $[a{k+1}, b{k+1}]=[\lambda{k}, b{k}]$ ，若 $\rho^{2}=1-\rho$， $\lambda{k+1}=\mu{k}$ ，即第 $k+1$ 步无需计算 $\lambda_{k+1}$ 。

解方程 $\rho^{2}=1-\rho$， $\rho>0$ ，得 $\rho=\frac{\sqrt{5}-1}{2} \approx 0.618$， $\rho=\frac{-\sqrt{5}-1}{2}$ （舍）。于是得到试探点的计算公式：

$$\begin{aligned} \lambda_{k} & =a_{k}+0.382(b_{k}-a_{k}), \\ \mu_{k} & =a_{k}+0.618(b_{k}-a_{k})_{0} \end{aligned}$$

由于区间缩短率 $\rho$ 满足$\frac{\rho}{1}=\frac{1-\rho}{\rho}$，是黄金分割数，故该方法称为黄金分割法或 0.618 法。

（2）函数逼近法（牛顿法）

基本思想：
在极小点附近任取一个初始点，用迭代点处的二阶 Taylor 多项式作为原函数的近似（即用该函数逼近原函数），然后求近似函数的极小点。若所求得的点不是原问题的极小点，便让它作为下一个迭代点；依次迭代下去，直到求得原问题的极小点或近似极小点。

牛顿迭代公式：
设当前迭代点为 $x^{k}$ ，则 $f(x)$ 在 $x^{k}$ 处的二次近似函数为：$g{k}(x)=f(x^{k})+f^{\prime}(x^{k})(x-x^{k})+\frac{1}{2} f^{\prime \prime}(x^{k})(x-x^{k})^{2}$ 。
求该近似函数的极小点，两边对 $x$ 求导，并令 $g{k}^{\prime}(x)=0$ ，则有：$f^{\prime}(x^{k})+f^{\prime \prime}(x^{k})(x-x^{k})=0$。
解之得： $x=x^{k}-\frac{f^{\prime}(x^{k})}{f^{\prime \prime}(x^{k})}$ 。
若该点不是（近似）极小点，则构造迭代格式，令$x^{k+1}=x^{k}-\frac{f^{\prime}(x^{k})}{f^{\prime \prime}(x^{k})}$。即得牛顿法的迭代公式，简称牛顿迭代公式。

算法步骤：

1. 给定初始点 $x^{0} \in \mathbb{R}$ ，允许误差 $0 \leq \epsilon \ll 1$ ，令 $k=0$ ；
2. 计算 $f^{\prime}(x^{k})$ ，如果 $|f^{\prime}(x^{k})| \leq \epsilon$ ，停止运算。否则计算 $f^{\prime \prime}(x^{k})$ ，并令 $x^{k+1}=x^{k}-\frac{f^{\prime}(x^{k})}{f^{\prime \prime}(x^{k})}$。
3. 令 $k=k+1$ ，返回 Step 2。

适用条件：牛顿法适用于二阶连续可导函数求极值问题。

优点：

• 对于严格凸二次函数求极值，一步迭代即可找到最优解；
• 如果初始点距离极小点较近，算法会很快收敛于极小点。

缺点：

• 对初始点要求高，若初始点距离极小点太远，则迭代过程可能不收敛，也可能收敛到极大点，即牛顿法的收敛性依赖于初始点的选择；
• 对函数要求高，牛顿法适用于二阶连续可导函数求极值问题；
• 需计算二阶导数，计算复杂度高。