无约束最优化(四) 步长加速法

作者: 小小何先生 | 来源:发表于2019-12-07 16:57 被阅读0次

步长加速法是由Hooke和Jeeves（1961年）给出的一种直接方法。对于变量数目较少的无约束极小化问题，这是一个程序简单又比较有效的方法。

基本思想

步长加速法主要由交替进行的“探测搜索”和“模式移动”组成。前者是为了寻找当前迭代点的下降方向，而后者则是沿着这个有利的方向寻求新的迭代点。

给出初始点 $x_{0}$ ，以它作为探测搜索的出发点（称为参考点，用 $r$ 表示，即 $r=x_{0}$ )，在其周围寻找比它更好的点 $b$ （称为基点），即 $f(b) < f(r)$ ，以得到下降方向 $b-r$ （称为模式）。然后从 $b$ 出发沿模式 $b-r$ 做直线搜索（称为模式移动）。 $\tilde {r} = b + \alpha (b-r)$ ， $\tilde {r}$ 是从 $b$ 出发，沿方向 $b-r$ 移动 $\alpha$ 个单位而得，其中 $\alpha > 0$ （一般取 $\alpha = 1$ 或用直线搜索技术来确定），以获得新的参考点（新的迭代点）。然后再开始探测搜索，模式移动。交替进行的“探测搜索”和“模式移动”将使得迭代点逐渐地向极小点靠近。

在这里插入图片描述

探测搜索

已知：目标函数 $f(x)$ ，步长向量 $s=\left [ s_{1}, s_{2}, ···，s_{n} \right ]^{T}$ ，参考点 $r=\left [ r_{1}, r_{2}, ···，r_{n} \right ]^{T}$ 。

计算 $f_{r}=f(r)$ ；置 $b=r, f_{b}=f_{r}$ 。
依次沿第 $i=1,2,···，n$ 个坐标轴方向作直线搜索：计算 $f_{1}=f(b+s_{i}e_{i})$ ， $f_{2}=f(b-s_{i}e_{i})$ 。以下三种情况必居其一：

i) 若 $f_{1} < f_{b}$ ，则置 $b=b+s_{i}e_{i}$ ， $f_{b}=f_{1}$ ；

ii) 若 $f_{2} < f_{b} \leq f_{1}$ ，则置 $b=b-s_{i}e_{i}$ ， $f_{b}=f_{2}$ ；

iii) 若 $f_{1} \geqslant f_{b}$ ， $f_{2} \geqslant f_{1}$ ，则置 $b$ 与 $f_{b}$ 不变；

依次对 $i=1,2,···，n$ 计算后，最终的 $b$ 是从 $r$ 出发以 $s$ 为步长向量探测搜索的终点。当 $f(b) < f(r)$ 时，探测搜索称为成功，此时必有 $b \neq r$ ，即得到模式 $b-r$ ；否则，探测搜索称为失败，此时未得到模式。

步长加速法

已知：目标函数 $f(x)$ ，步长收缩系数的终止限 $\varepsilon$ 。

选定初始点 $x_{0}$ ，初始步长量 $s_{0}$ ，置 $r=x_{0}$ ， $b_{0}=x_{0}$ ， $c = 1$ ， $w=0.5$ (或0.1)。
置 $s = c s_{0}$ 。
在点 $r$ 处，以 $s$ 为步长向量按探测搜索算法做探测搜索得 $b$ 。
若 $f_{b} < f(r)$ ，则转5；否则，转8。
做模式移动 $r=2b-b_{0}$ ，并置 $b_{0}=b$ ， $f_{0}=f_{b}$ 。
在点 $r$ 处，以 $s$ 为步长向量按算法按探测搜索算法做探测搜索得 $b$ 。
若 $f(b) < f(b_{0})$ ，则转5；否者，置 $r=b_{0}$ ，转3。
若 $c \leqslant \varepsilon$ 则输出 $r$ ，停止计算；否则，置 $c=wc$ ，转2。