步长加速法是由Hooke和Jeeves(1961年)给出的一种直接方法。对于变量数目较少的无约束极小化问题,这是一个程序简单又比较有效的方法。
基本思想
步长加速法主要由交替进行的“探测搜索”和“模式移动”组成。前者是为了寻找当前迭代点的下降方向,而后者则是沿着这个有利的方向寻求新的迭代点。
给出初始点x 0,以它作为探测搜索的出发点(称为参考点,用r 表示,即r = x 0 ,在其周围寻找比它更好的点b (称为基点),即f ( b ) < f ( r ) ,以得到下降方向 b − r(称为模式)。然后从b 出发沿模式b − r 做直线搜索(称为模式移动)。r ~ = b + α ( b − r )是从b 出发,沿方向b − r 移动α 个单位而得,其中α > 0 (一般取α = 1 或用直线搜索技术来确定), 以获得新的参考点(新的迭代点)。然后再开始探测搜索,模式移动。交替进行的“探测搜索”和“模式移动”将使得迭代点逐渐地向极小点靠近。
探测搜索
步长加速法
已知:目标函数f ( x ) ,步长收缩系数的终止限ε
注意:算法中的模式为b − b 0 。当由3产生时,模式既为b − r;但当由6产生时,模式才为b − b 0 这是加速模式。
在迭代开始时,基点和参考点重合,并都在初始处,经过探测搜索,得到新的基点,然后再经过模式移动,得到新的参考点,再探测,再移动,探测搜索与模式移动交替进行下去,迭代点就将逐渐地向极小点靠近。
I型探测搜索:出发点既是参考点,又是基点,目的是在基点周围构造一个模式。II型探测搜索:出发点单纯是参考点,目的是判别上次的模式移动是否成功,从而能否作加速移动。
我的微信公众号名称:深度学习与先进智能决策
微信公众号ID:MultiAgent1024
公众号介绍:主要研究分享深度学习、机器博弈、强化学习等相关内容!期待您的关注,欢迎一起学习交流进步!