专栏首页罗西的思考[笔记整理] 一维搜索

[笔记整理] 一维搜索

[笔记整理] 一维搜索

0x00 摘要

本文是阅读Alink源码期间在网上查找资料做的笔记整理,把找到的算法实现加了一些注解。

0x01 概念

1.1 一维搜索

一维搜索是用来求步长的。

Line Search顾名思义就是沿着一个线寻找下一个x_{k+1},

一维搜索的理论是建立在整个最优化理论之下的。如果要理解什么一维搜索,就要理解最优化的目标与形式。

最优化目标: min(f(x)),一般而言f(x)是凸的。

在大多数多变量函数的最优化中,迭代格式为:

\[\begin{aligned}&x_{k+1} = x_k + \alpha_kd_k \\\\&x_k 是已经搜索到的点 \\&搜索方向(变量变化的方向): d_k \\&步长因子(变量变化的大小,也被称为学习率): \alpha_k \\&即 \\&1. 求取下降方向 d_k, 使d_k < 0\\&2. 求取步长 \alpha, 使f(x+\alpha d ) < f(x) \\&3. 反复迭代直至收敛 \\\end{aligned} \]

其中最为关键的就是往哪走的搜索方向 d_k 和走多少的步长因子 alpha_k,如果确定了搜索方向,那么求解步长因子 alpha_k 的问题就是一维优化问题,不妨设:

\[\begin{aligned}&\Phi(\alpha) = f(x_k + \alpha_kd_k ) \\ \\&则从x_k出发,沿搜索方向d_k,确定步长因子 \alpha_k,使得\Phi(\alpha) < \Phi(0)的问题就是关于步长因子 \alpha 的一维搜索问题\end{aligned} \]

所谓一维搜索指的就是步骤2 "求取步长"。

为了进行一维搜索,我们首先需要缩小变量所在的变化范围,然后再用其他方法去求极值。

一维搜索主要结构可作如下概括:

  • 首先确定包含问题最优解的搜索区间。
  • 然后采用某种分割技术或者插值方法缩小这个区间,进行搜索求解。

一维搜索一般有如下方法,解析法和数值解法。解析法即是按照数学公式求导数求极值。但是一般实际问题中,往往不知道损失函数的数学表达式、或者导数比较难求,这种方法一般应用于科学计算。数值类方法有分为两类,试探法和插值法。

一维搜索分为两种:

  • 非精确一维搜索,就是找到一个 alpha 满足一定条件即可,好比Wolfe-Powell,Armijo条件。
  • 精确一维搜索,就是找到一个参数 alpha,使得min(f(x))最小,有插值法,黄金分割法,直接法等等。

1.2 不精确一维搜索

  • 精确一维搜索往往需要花费很大的时间。
    • 当迭代点远离问题的解时,精确求解通常不十分有效。
    • 很多最优化方法,如牛顿法和拟牛顿法,其收敛速度并不依赖于精确一维搜索过程。
  • 只要保证目标函数有满意的下降,可大大节省计算量

所以实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的一维搜索需要付出较高的代价,对加速收敛作用不大,因此花费计算量较少的不精确的一维搜索技术方法受到更为广泛的重视和欢迎。

确定步长最简单的方法,就是挨个试。从0开始,每隔一定距离计算一下目标函数的值,找出其中最小的那个,对应的步长就是我们要的结果。

显然,这种方法太过暴力,试的次数太多,很影响效率。所以有一些原则可以帮助我们提高效率。

一般而言主要有以下两种准则:Armijo-Goldstein准则 和 Wolf-Powell 准则。

1.2.1 Armijo-Goldstein准则

Armijo-Goldstein准则核心思想就两点:

  1. 目标函数值应该有足够的下降
  2. 一维搜索的步长 lambda 不应该太小

Armijo 又被称为充分下降条件(sufficient decrease condition),又称Armijo condition。

\[\begin{aligned}&f(x_k + \alpha p_k) <= f(x_k) + c . \alpha ▽ f^{T}_kp_k \\ \\&0 < c < \frac{1}{2} \\&▽f^{T}_kp_k < 0,p_k为函数下降方向\end{aligned} \]

Armijo condition这个约束太简单了,以至于任意小的步长 alpha 都可以满足该条件。为了保证每次迭代有充分的下降,我们加上Goldstein conditions。

\[\begin{aligned}&f(x_k)+(1-c)\alpha▽f^{T}_kp_k <= f(x_k + \alpha p_k) <= f(x_k) + c . \alpha ▽ f^{T}_kp_k \\ \\&0 < c < \frac{1}{2} \\&▽f^{T}_kp_k < 0,p_k为函数下降方向\end{aligned} \]

这是两个不等式,左右分别对应斜率不同的直线,将可接受区域约束在这两条直线之间。

如果步长 alpha 太小的话,会导致左边不等式接近于不成立的边缘。因此,左边不等式 就保证了 alpha 不能太小。

Armijo-Goldstein准则有可能把最优步长因子排除在可接受区间外,所以Wolfe-Powell更可以满足我们需求。

1.2.2 Wolf-Powell 准则

Wolfe conditions实际上规定了两件事情,

  1. 函数值必须下降
  2. 只接受导数较平缓的区域

Wolfe conditions使得目标点处的切线变得“不那么斜”了,这符合实际规律,因为极值点处不应该过于陡峭。

既然和导数大小有关,那么我们可以试着考虑二分点的导数值。如果二分点的导数值很小,直接满足Wolfe conditions,那就找到了可接受的步长。如果二分点的导数值很大,那么我们就选择与该点导数符号相反的那个端点,重新组成一个子区间。之所以选择符号相反的那个端点,是因为对于连续光滑的函数来说,两个斜率相反的点之间一定存在极值点,也就存在导数值很小的一段区域。按照这种策略,逐步缩小区间范围,直到某个二分点满足Wolfe conditions为止。

Wolfe-Powell方法相较于精确一维搜索,不再采用进退法去寻找搜索区间。在进退法里面,是通过慢慢扩展生成区间,然后在在区间中查找合适的,而在Wolfe-Powell中我们可以直接定义步长区间的界限,比如[0,10000],那么其会根据其准则去每次剔除不符合的区间,逐步缩小区间,其能够较为快速的跳过无用的计算,速度要快很多

Wolfe-Powell方法计算过程中,也用到了插值方法,用以区间切割剔除。

1.2.3 结合代码分析

Armijo准则:首先给一个较大的学习率,然后不断缩减学习率,如果对于函数f(xk+αdk)当前的学习率使函数从当前的位置f(xk)的减小一定程度后还大于预设的期望值,那这个学习率就符合要求了

什么意思?你看,对于函数f(xk+αdk),既然是求最小值,那对于当前的值f(xk)减小一定程度后就有个新值f(xk+1),于是,如果我们将f(xk+1)作为预设的期望值,即我们希望f(xk)在某个学习率α的情况下减小一定程度后可以到达f(xk+1),那这个α就是我们希望得到的α了对吧。

这个减小程度在Armijo准则中是公式:

c1α▽f(xk)Tdk,c1∈(0, 1)

因为dk一般取梯度负方向,所以用式子表达上面的话的话就是:

f(xk+1)= f(xk) + c1α▽f(xk)Tdk,c1∈(0, 1)

具体分析代码

function lamda = ArmijoGoldstein(func,gfunc,lamda0,ro,apha,iterNum,plotFlag)
  if nargin<7
      plotFlag = 1;
  end
  if nargin<6
      iterNum = 100;
  end
  if nargin<5
      apha = 2;
  end
  if nargin<4
      ro = 0.1;
  end
  if nargin<3
      lamda0 = 1;
  end
  
  a = 0; %左边界
  b = inf; %右边界
  lamda =lamda0;
  f0 = func(0);
  g0 = gfunc(0);

  while iterNum
      flamda = func(lamda);
      if flamda<=f0+ro*lamda*g0 %判断Armijo准则
          %满足充分下降条件
          %if flamda>=f0+(1-ro)*lamda*g0 %代码可以调整为判断Goldstein
          if gfunc(lamda)>=sigma*g0 %判断曲率条件        
              %满足wolf-powell,步长不会太小        
              break; %找到了可接受的步长,返回即可
          else 
              %不满足wolf-powell,说明当前步长落在了斜率较大的区域,此时有两种可能
              a = lamda; %左端的a设置为lamda
              if isinf(b) 
                 %如果是远离初始点的区域,那么在初始点和当前点之间一定存在可接受的区域。右端的b为空的时候,说明Armijo准则一直是满足的,步长太小了,扩大步长
                  lamda = alpha*lamda;
              else 
                  %如果是接近初始点的区域,这一区域不是我们想要的,需要进一步放大步长
                  lamda = (a+b)/2; %步长设定为区间的中值
              end
          end
      else 
          %找到了不满足充分下降条件的步长,因此该步长可以作为右边界,缩小b和步长
          b = lamda; %收缩
          lamda = (a+b)/2;
      end
      iterNum = iterNum - 1;
  end

%example
%lamda = WolfPowell(@(x)(sin(-4+x)-1),@(x)(cos(-4+x)),1,0.4,0.45,2,100,1)

0xFF 参考

优化方法基础系列-精确的一维搜索技术

优化方法基础系列-非精确的一维搜索技术

[原创]用“人话”解释不精确线搜索中的Armijo-Goldstein准则及Wolfe-Powell准则

https://www.zhihu.com/question/36425542

一维搜索算法介绍及其实现

数值优化|笔记整理(1)——引入,线搜索:步长选取条件

https://zhuanlan.zhihu.com/p/32821110

线搜索(一):步长的选取

最优化问题——一维搜索(二)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Alink漫谈(二十一) :回归评估之源码分析

    Alink 是阿里巴巴基于实时计算引擎 Flink 研发的新一代机器学习算法平台,是业界首个同时支持批式算法、流式算法的机器学习平台。本文和将带领大家来分析Al...

    罗西的思考
  • [梁山好汉说IT] 梁山好汉和抢劫银行

    今天看了一篇文章《史上最有学问的银行劫匪,教你如何把握人生重大机会》。先摘录精华如下,然后看看梁山好汉在类似情况下如何处理 (东京汴梁看灯项目)

    罗西的思考
  • [记录点滴]编译安装luarocks、luacheck、luautf8

    如今每个语言体系中都有一个包管理工具,PHP的Composer,Ruby的gem,Python的pip,lua第三方包管理工具就是luarocks。

    罗西的思考
  • Skywalking系列博客2-Skywalking使用

    Skywalking有多种使用方式,目前最流行(也是最强大)的使用方式是基于Java agent的。

    用户1516716
  • bash定时上传文件到ftp

    #!/bin/bash #上传本地的/var/ftp/test/a.log到ftp服务器的/var/ftp/test/目录下 #FTP信息 FTP_HOST='...

    苦咖啡
  • Python中zipfile压缩文件模块的基本使用教程

    创建一个压缩文件 test.zip(如果test.zip文件不存在) ,然后将test.txt文件加入到压缩文件 test.zip中,如果原来的压缩文件中有内容...

    砸漏
  • rapidJson 的使用

    bear_fish
  • 代理模式

    JDK动态代理的对象必须要实现接口,所以对于一些没有实现接口要被代理的对象,不适用JDK动态代理;cglib是通过继承被代理类,重写方法,织入通知通过动态字节码...

    OPice
  • numpy C语言源代码调试(三)

    鉴于ddd过于简陋,希望找一个新一些的调试工具,看到有很多人推荐gdbgui,这是一个非常新的调试工具,前端使用浏览器,现在采用这一架构的软件越来越多,可以完全...

    py3study
  • 通过调试获得SAP Fiori gateway系统的系统ID

    For example if you are working on this url: https://jerry.sap.corp:4080/sap/bc/u...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券