Welcome To My Blog
在最优化(optimization)问题中,线搜索(line search)和置信域(trust region)方法是寻找局部最小值(local minimum)基本迭代方法(iterative approach),主要说说线搜索方法(置信域方法过于专业)
线搜索(Line search)
以f(x)为例,线搜索会先找一个使f(x)下降的方向,接着计算一个步长,步长决定了x改变的大小.
下降方向:可以通过梯度下降,牛顿法,拟牛顿法等计算
步长:有精确(exact)和非精确(inexact)两种,精确方法就是找出导数为零的极值点,例如共轭梯度法conjugate gradient method;非精确方法没有找出导数为零的点,而是使f(x)有一个充分的下降(sufficient descent),例如backtracking,wolfe conditions,goldstein conditions
线搜索流程:
非精确线搜索步长
精确线搜索的步长计算往往非常耗时,所以一般采用非精确线搜索
Wolfe conditions
Wolfe conditions 由 Armijo conditions和Curvature conditions构成,先分别介绍Armijo conditions和Curvature conditions
Armijo conditions
Armijo条件:
不等式两侧都可看成α的线性函数,所以不等式要求相当于,左侧的直线在右侧直线下方.实际应用中将c1取得很小,以使得不等式右侧的直线不是太倾斜(太倾斜会使得下降太多,可能取不到最优点)
Curvature condition
在满足Armijo条件的情况下我们希望步长尽量大一些,这样收敛快,所以引入curvature条件:
将等式两侧都写成α的函数形式,则有:
这要求:θ(α)’大于等于θ(0)’的c2倍
经验取值:
在拟牛顿法中,c2=0.9
在非线性共轭梯度方法中,c2=0.1
Wolfe conditions
Wolfe conditions:将Armijo conditions和Curvature conditions结合在一起
直观点,如下图:(忽略丑陋的字…)
由Armijo:函数值位于橘黄色的直线下面
由Curvature:斜率要大于等于θ(0)’的c2倍
所以最后满足条件的区域为(α1,α2)和(α3,α4)
可以看到,最小值在(α3,α4)中
Goldstein conditions
一般用于牛顿法,但不适合拟牛顿法,因为拟合的Hessian矩阵不能保持正定
第二个不等号和sufficient descent的形式完全一样
类似Wolfe conditions,写成θ(α)的形式
Goldstein conditions就是要求θ(α)要在两条直线之间,但可能避开最优解
像下面这样:
满足条件的区域为(α1,α2)和(α3,α4)
最小值并不在这里面
Backtracking method
在实际应用中,为提高效率,放弃Wolfe conditions中的Curvature conditions,只使用sufficient descent条件,这就是Backtracking method