一维搜索linesearch

一: 精确搜索-区间分割方法
1). 0.618法
对于一个单谷函数想通过迭代不断缩小该区间的长度, 当区间长度充分小时, 可取这个小区间中的一点作为\(\varphi (t)\)的一个近似极小点. 每次迭代时在搜索区间中任取两个点, 然后比较这两个点的函数值定下新的搜索区间. 当我们想在第二迭代开始时每次只搜索一个点, 即要把上一次迭代被抛弃的点利用上, 并且限制住收缩比相同. 则可以推出0.618法.

2). Fibonacci法
问题的提出: 在0.618法中, 经过N-1次迭代后的搜索区间\(\left[ {{a_N},{b_N}} \right]\)的长度为\({b_N}{\rm{ – }}{a_N} = {\tau ^{N – 1}}({b_1} – {a_1})\), 那么, 如果事先给定了搜索算法的迭代次数N, 按那种规则选取试探点可以使给定的搜索区间长度做最快分割呢?
上面的问题可以转化为一个优化问题:
\[\begin{array}{*{20}{c}}
{\min }&{{\tau _1}{\tau _2} \cdots {\tau _{N - 1}}}\\
{s.t.}&{{\tau _{k + 1}}{\tau _k} = 1 - {\tau _k}}\\
{}&{\frac{1}{2} < {\tau _k} < 1}
\end{array}\]
这里第1个约束条件是为了每次迭代只计算一个函数值. 可以证明, 这个优化问题的最优解为\({\tau _k}{\rm{ = }}\frac{{{F_{N – K}}}}{{{F_{N – K + 1}}}}\), 其中\({F_{N – K}}\)为Fibonacci数列, 即\[\left\{ {\begin{array}{*{20}{c}}
{{F_0}{\rm{ = }}{F_1}{\rm{ = }}1}\\
{{F_{i + 1}} = {F_i} + {F_{i - 1}},i = 1,2,...}
\end{array}} \right.\]

3). 二分法
二分法是一种最简单的搜索方法, 并且利用了一阶导数信息. 基本思想是通过计算区间中点的函数导数值来缩减搜索区间. 每次迭代都将区间缩短一半, 故二分法的收敛速度也是线性的, 收敛比为1/2.

二: 精确搜索-插值法
上面讨论的3中方法都属于直接方法, 仅仅是比较了各个探索点的函数值, 而一些非常有用的信息(如高阶导)却没有被利用, 因此所得到算法的收敛速度比较慢. 为了充分利用信息量, 在搜索区不断用低次(通常不超过三次)多项式来近似目标函数. 并逐步用插值多项式的极小点来逼近一维搜索问题的极小点.

1). Newton法, 又称为一点二次插值法.
迭代公式: \({t_{k + 1}}{\rm{ = }}{t_k} – \frac{{\varphi ‘({t_k})}}{{\varphi ”({t_k})}}\)
同样的, 还有二点二次插值法, 三点二次插值法, 二点三次插值法等.

三: 非精确搜索
一维搜索常常用来搜索步长, 如果对步长进行精确一维搜索要付出高昂的代价, 并且从整体观点来看对加速问题变量收敛作用不一定很大, 很多优化算法例如牛顿法和拟牛顿法, 其收敛速度并不依赖于精确一维搜索过程. 因此发展了非精确一维搜索方法. 就是在当前点确定了下降方向后, 只需下一次迭代点使目标函数有满意的下降量即可. 但我们对下降量也是有一定要求的, 一般不希望步长太大以引起大幅度摆动, 也不希望太小致使移步不前. 这就提出了几种准则.
1). Goldstein法:
Goldstein在1967年提出了这个方法: 预先指定两个数\({m_1}\)和\({m_2}\)满足\(0 < {m_1} < {m_2} < 1\), 用以下两个式子限定步长\({t_k}\)不太大也不太小:
\(\varphi ({t_k}) \le \varphi (0) + {m_1}{t_k}\varphi ‘(0)\) (1)式
\(\varphi ({t_k}) \ge \varphi (0) + {m_2}{t_k}\varphi ‘(0)\) (2)式
一般取\({m_1} \in (0,0.5],{m_2} \in (0.5,1]\)

2). Armijo法:
作为Goldstein法的一种变形, Armijo在1969年提出一种方法: 取定\(0 < m < 1 < M\), 用以下两个式子限定\({t_k}\)不太大也不太小:
\[\begin{array}{l}
\varphi ({t_k}) \le \varphi (0) + m{t_k}\varphi '(0)\\
\varphi (M{t_k}) \ge \varphi (0) + mM{t_k}\varphi '(0)
\end{array}\]
通常取\(M \in (5,10)\)

3). Wolfe-Powell准则
从图中也可以看出来, Goldstein-Armijo准则的一个缺点就是有可能把步长因子\(t\)的极小值排除在可接受区域外面. 为此, Wolfe-Powell准则给出了一个更简单的条件代替(2)式
\[\varphi ({t_k}) \le \varphi (0) + {m_1}{t_k}\varphi '(0)\]
\[\varphi '({t_k}) \ge {m_2}\varphi '(0)\]
一般取\({m_1} \in (0,0.5],{m_2} \in (0.5,1]\)
其几何解释是在可接受点处切线的斜率\(\varphi ‘({t_k})\)大于或等于初始斜率\(\varphi ‘(0)\)的\({m_2}\)倍.

Wolfe-Powell另一种更强的条件是, \(\left| {\varphi ‘({t_k})} \right| \le {m_2}\left| {\varphi ‘(0)} \right|\). 与(1)式组成准则条件, 即:
\[\varphi ({t_k}) \le \varphi (0) + {m_1}{t_k}\varphi '(0)\]
\[\left| {\varphi '({t_k})} \right| \le {m_2}\left| {\varphi '(0)} \right|\]
一般取\({m_1} \in (0,0.5],{m_2} \in (0.5,1]\)

4). 简单准则与后退法
在实际中有时仅采用准则(1)式. \(\varphi ({t_k}) \le \varphi (0) + {m_1}{t_k}\varphi ‘(0)\) 这种做法叫做简单准则. 利用简单准则的非精确一维搜索方法称为后退法.
基本思想就是, 开始要求\({t_k}\)不太小, 令\({t_k}{\rm{ = }}1\), 如果不可接受, 则减少\({t_k}\) (后退), 一直到可接受为止.

[参考] 1.袁亚湘院士著.

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>