数值最优化：线搜索技术

www.gaoxiao88.net

对于求解无约束优化模型通常会有下面的一种迭代步：
通过某种搜索方法确定步长因子，使得这实际上是目标函数在规定的一个方向上移动所形成的单变量优化问题，也就是所谓的 “线搜索” 技术，令这样，搜索式等价于求步长使得

精确线搜索的基本思想： 首先确定包含问题最优解的 搜索区间 ，然后采用 某种插值或分割技术缩小区间 ，进行搜索求解。
由于不少精确线搜索算法都是针对单峰函数建立起来的，下面介绍一种确定搜索区间并保证具有 近似单峰性质 的数值算法—— 进退法

算法1：进退法
S1： 给出 , , ;
计算 , ;
S2： 如果则转 S4;
如果则转 S6;
S3： 令 , 如果则转 S3;
如果则转 S6;
, 转 S7;
S4： 令 , 如果则转 S7;
如果则转 S5;
令 , 转S4；
S5： 令 , 如果 , 则令 , 转 S7;
如果 , 则令 , 转 S7;
令 , 转 S5.
S6： 令 , 转 S2;
S7： 令 , 即停。

例1： 利用进退法求解极值区间实例。取初始点，步长，用进退法求函数的极值区间。

黄金分割法又称 0.618 法，其基本思想是通过试探函数值的比较，使得包含极小点的搜索区间不断缩小，直至区间内的值足够接近极小值为止。该方法仅需要计算函数值，适用范围广，使用方便。下面我们来推导 0.618 法的计算公式。
设其中是搜索区间的单峰函数。
假设在第次迭代时搜索区间为 , 为确定下一次迭代区间，我们取两个试探点 , 计算得到和 , 存在两种情况：
（1）若 , 则令 ;
（2）若 , 则令 ;
我们要求两试探点满足如下条件：
（1）与长度相同，即 ;
（2）区间长度的缩短率相同，即 .
从而可得由于两区间长度一致，不妨假设新的迭代区间为为进一步缩小区间，取新的试探点 , 得若令则这样，新的试探点就不用重新计算。得到区间的缩短率为

算法2：黄金分割法（0.618法）
S1： 选定区间及精度 , 令 , 计算试探点

S2： 若 ,则停止计算;
否则，当时转 S3；当时转 S4；
S3： 令 , 转 S5;
S4： 令 , 转 S5;
S5： 令 , 转 S2.

例2： 利用黄金分割法求解极值实例。利用黄金分割法求下面函数的极小值

基本牛顿法是一种是用导数的算法，它每一步的迭代方向都是沿着当前点函数值下降的方向。其基本思想是：用在探索点处的二阶 Taylor 展开式得到的二次函数来近似代替：其中，可以认为是的近似。因此，求函数的极小值点近似于求解的极小值点， 函数应该满足一阶必要条件 ：即上式即为牛顿法的迭代公式，当时，对于区间内的都成立；反之当时，牛顿法可能收敛到极大值点。

算法3：基本牛顿法
S1： 给出精度 , 令 ;
S2： 若 , 停止, 极小值点为；
S3： 令 ;
S4： 令 , 转 S2.

例3： 取初始点，用牛顿法求的任一极小值点。

线搜索技术是求解许多优化文体下降算法的基本组成部分，但精确线搜索往往需要计算很多的函数值和梯度值，从而耗费较多的计算资源。特别是当迭代点远离最优点是，线搜索方法通常不是十分有效和合理的。因此，既能保证目标函数具有可接受的下降量又能使最终新城的迭代序列收敛的非精确线搜索越来越流行。常用的有 Walf 准则与 Armijo 准则 。

牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性，但基本牛顿法初始点需要足够“靠近”极小点，否则有可能导致算法不收敛。这样就引入了 阻尼牛顿法（也称全局牛顿法） ，阻尼牛顿法最核心的一点在于可以修改每次迭代的步长，通过沿着牛顿法确定的方向一维搜索最优的步长，最终选择使得函数值最小的步长。
阻尼牛顿法是 基于 Armijo 准则的搜索 ，满足 Armijo 准则：一般的，可取为或更小的值。由于时下降方向，不等式右边是关于的线性减函数。因此只要不取的太小，不等式可以保证新迭代点的函数值较有一定量的下降。

算法4：阻尼牛顿法（全局牛顿法）
S1： 给出精度 , 令 ;
S2： 计算 , , 若则转 S4;
若则停止;
令初始值 ;
S3： 令 , 如果 , 则转 S3;
令 , , 转 S2；
S4： 令 , 如果 , 则令 , 置 ;
S5： 如果
则转 S6；置；转 S5;
S6： 令 , , 转 S2.

例4： 取初始点，用全局牛顿法求函数的极小值点。

搞笑吧

数值最优化：线搜索技术

相关参考：

相关评论

相关话题