优化理论之一维不精确优化

一维不精确优化

注1：本文讨论需要优化的函数都是单峰函数（或单谷函数）。

精确一维搜索方法往往需要花费很大的时间，特别当迭代点远离问题的解时，精确求解通常不十分有效。另外，实际上很多最优化方法，如牛顿法和拟牛顿法，其收敛速度并不依赖于精确一维搜索过程。因此，只要保证目标函数\(f(x)\)在每一次迭代有满意的下降，可大大节省计算量。

我们在这里再次说明，不做特殊说明下，我们的目标是求函数的极小值。

\[\min_{x ∈ D} f(x)\\ D为n维约束集\]

不精确搜索一般而言主要有两种准则Armijo-Goldstein 准则、Wolfe-Powell 准则，还有基于两大准则的推广，例如强 Wolfe-Powell 准则和简单准则。它们的出发点都是保证搜索步长不太大或不太小。不精确一维搜索方法总体希望收敛快，每一步不要求达到精确最小，速度快，虽然步数增加，则整个收敛过程更快速。

为什么要遵循这些准则？

由于采用了不精确的一维搜索，所以，为了能让算法收敛（即：求得极小值），人们逐渐发现、证明了一些规律，当你遵循这些规律的时候，算法就很有可能收敛。因此，为了达到让算法收敛的目的，我们就要遵循这些准则。如果你不愿意遵循这些已经公认有效的准则，而是要按自己的准则来设计算法，那么恭喜你，如果你能证明你的做法是有效的，未来若干年后，书本里可能也会出现你的名字。

不精确步长搜索基础算法

试探法（Backtracking Approach）

如果备选的步长合适，那么通过试探法，我们可以只用充分下降条件来做终止条件，同时选出一个不错的步长。（因为这时候 α 是从大往小变化，所以不可能变得太小）。其算法的具体步骤如下：

初始化：一般选择\(\gamma∈[0.5,0.8] ,c∈(0,1)\)
依据以下步骤从\(\vec x_{old}\)更新到\(\vec x_{new}\):
Step1：计算后向跟踪步长 \[\begin{aligned}\alpha^\ast&:= \max \gamma^v\\ s.t. \quad & v ∈\{0,1,2,\dots\}\\ &f(\vec x_{old}+\gamma^v\vec d)≤f(x_{old})+c\gamma^v f'(\vec x_{old},\vec d)\end{aligned}\] 其中\(\gamma^v\)是几何序列（等比序列）。
Step2： \(\vec x_{new}=\vec x_{old}+\alpha^\ast\vec d\)

试探法是大多数线性搜索方法的基础。基于这个算法，我们来详细谈谈它的拓展。

充分下降准则(简单准则)

我们要求目标函数的最小值，最重要的就是要让函数有足够的下降。足够这个词，是希望一种发散的下降，而不是会收敛到某一点的下降，举个反例：

\[\min f(x)=(x+1)^2\\ x(k)=5/k,k=1,2,3,\dotsb\] 这个\(x\)序列确实一直让函数值在下降，但是不够充分，每次下降的越来越小，直到收敛到点\((0,1)\)。无穷的收敛性有时候很好，也有时候令人恼怒。因此，我们需要指定一个充分下降条件。当迭代到第\(k\)次时：

\[f(\vec x_k+\alpha\vec d_k)≤f(\vec x_k)+\alpha c\nabla f(\vec x_k)\vec d_k\quad PS:f'(\vec x_k;\vec d_k)=\nabla f(\vec x_k)\vec d_k\]

这个不等式如何保证呢？首先我们需要找到一个严格下降方向\(\vec d\)，其方向导数是负数，即 \[\lim_{\alpha→0}\frac{f(\vec x_{old}+\alpha\vec d)-f({x_{old})}}{\alpha}=f'(x_{old};\vec d)<0\quad \alpha\in(0,\bar \alpha)\] 取一个\(c ∈(0,1)\)，那么 \[\lim_{\alpha→0}\frac{f(\vec x_{old}+\alpha\vec d)-f({x_{old})}}{\alpha}=f'(x_{old};\vec d)<cf'(x_{old};\vec d)<0\\ \Rightarrow f(\vec x_{old}+\alpha\vec d)≤f(x_{old})+\alpha cf'(x_{old};\vec d)\] 一般而言，\(c\)是一个小量\([0.0001,0.1]\)，其作用是放缓曲线，下图举了个例子

充分下降准则.png

如果直接使用\(\nabla f(x)^Td\)则有可能导致没有可行的步长，因此使用一个平缓参数\(c\)。\(c\)一般是一个小数，把直线图像抬起来，有的时候\(c=0.0001\)，那么\(f(x_{old})+\alpha cf'(x_{old};\vec d)\)基本差不多是一条水平线了。但是\(c\)是一个定值，保证了下降过程不会收敛。

此外，如果只满足充分下降准则，也可以称之满足于简单准则。

Wolfe-Powell准则

仅靠充分下降条件并不能保证算法每一步都能有很好的进步（make reasonable progress）。事实上，我们可以发现，当\(α\)充分小时，充分下降条件总是满足的。所以，算法可能会常常产生令人无法接受的小步长。为了避免这种情况，我们引入另一个条件，称为曲率条件，即需要\(α_k\)满足 \[\nabla f(x_k+\alpha_k d_k)^T p_k\ge c_2\nabla f_k^T d_k\] 其中\(c_2∈(0,1)\)为一常数。

因此， Wolfe-Powell准则归结为

1. 充分下降准则
2. 曲率条件

Wolfe条件

Armijo-Goldstein准则

Armijo-Goldstein准则的核心内容有两条：

1. 充分下降准则
2. 搜索的步长不应该太小

\[1:f(\vec x_k+\alpha\vec d_k)≤f(\vec x_k)+\alpha c\nabla f(\vec x_k)\vec d_k\] \[2:f(\vec x_k+\alpha\vec d_k)≥f(\vec x_k)+\alpha (1-c)\nabla f(\vec x_k)\vec d_k\] 其中，\(c ∈ (0,0.5)\)

Armijo-Goldstein

推广：强Wolfe-Powell准则

强Wolfe条件对\(α_k\)的限制为 \[\begin{array}{c}f(x_k+\alpha_k p_k)\le f(x_k)+c_1\alpha_k\nabla f_k^T p_k \\ |\nabla f(x_k+\alpha_k p_k)^T p_k|\le c_2|\nabla f_k^T p_k| \end{array}\] 注意到，这个条件比Wolfe条件只多了绝对值符号。强Wolfe条件实际上限制了\(ϕ′(α_k)\)不能为一个很大的正数，即可行的\(α\)不能离最低点太远。

这个笔记并不完整，一些内容可见，我在这上面花了不少时间，但是不知道是否值得，现在先暂停下。