数值优化(Numerical Optimization)学*系列-拟牛顿方法(Quasi-Newton)

发布于:2021-09-26 13:18:06

概述


拟牛顿方法类似于最速下降法,在每一步迭代过程中仅仅利用梯度信息,但是通过度量梯度之间的变化,能够产生超线性的收敛效果。本节主要学*一下知识点:
1. 拟牛顿方程推导
2. 几个常见的拟牛顿方法
3. 拟牛顿方法的收敛性



拟牛顿方程

拟牛顿方法既有线搜索的影子也有牛顿方法的思想,下面从两个角度分别介绍拟牛顿方程,即在拟牛顿方法中要遵循的一个原则。


线搜索角度

假设在第K步迭代过程中,对点

xk
进行建模





mk(p)=fk+?fTk+12pTBkp

,这是一个相对标准的建模过程,在点x_k处寻找下一个搜索方向。该模型满足



mk(0)=fk;??mk(0)=?fTk


此时如果B为正定矩阵,则最优解为



pk=?B?1k?fk
。则下一个迭代值



xk+1=xk+αkpk
.

问题来了如何构造有效的



Bk
呢,如果选择Hessian矩阵该方法就为线搜索的牛顿方法。

高人就想出了通过当前点和上一步的搜索点构造该矩阵的方法,
需要满足模型m和目标函数f在

xk,xk+1
保持梯度一致


此时在

xk+1
处的模型为





mk+1(p)=fk+1+?fTk+1+12pTBk+1p

,需要满足



xk,xk+1
梯度一致。则有




?mk+1(xk+1)=?fk+1?mk+1(xk)=?fk

等价于




?mk+1(0)=?fk+1?mk+1(?αkpk)=?fk

从而有




?mk+1(?αkpk)=?fk+1?αkBk+1pk=?fk

。根据



xk+1=xk+αkpk




Bk+1(xk+1?xk)=?fk+1??fk
。一般情况下记




sk=xk+1?xkyk=?fk+1??fk



可以推出拟牛顿方程也叫(Secant equation):




Bk+1sk=yk



牛顿法角度

拟牛顿方法也可以认为是一种特殊的共轭梯度算法,其主要思想是利用目标函数梯度的差分构造目标函数Hessian矩阵的某种*似,然后基于牛顿方程产生搜索方向,最后通过线搜索完成迭代过程。
假设在点

xk+1
处进行泰勒展开有





f(x)=fk+1+?fTk+1(x?xk+1)+12(x?xk+1)T?2fk+1(x?xk+1)



两端对x求梯度并且



x=xk





?fk=?fk+1+?2fk+1(xk?xk+1)

,整理后得到




?2fk+1(xk+1?xk)=?fk+1??fk

由于Hessian矩阵比较难求解,用其*似矩阵



Bk+1
代替,同时借用上面的表达式有



Bk+1sk=yk


如果记



Hk+1=B?1k+1
,也有



Hk+1sk=yk


以上两种形式都称为拟牛顿方程。



拟牛顿方程:

Bk+1sk=yk
或者

Hk+1sk=yk



拟牛顿方程成立条件

由于

Bk
需要满足对称正定,因此需要满足

sTkyk≥0
,如果步长满足一定条件,例如Wolfe条件,则上式一定成立。



前半部分是由于

sTkBk+1sk=skyk
,由于B是正定的,肯定必须满足两个向量相乘大于0


后半部分是由于,Wolfe条件的第二个约束是





?fTk+1sk≥c2?fTksk<=>?fTk+1sk??fTksk≥c2?fTksk??fTksk<=>yTksk≥(c1?1)αk?fTkpk

由于



c2<1
如果搜索方向是下降方向则一定是大于0的。


拟牛顿方法

根据拟牛顿方程可以找到很多满足约束的矩阵,为求解方便需要进行一些约束,主要是秩的约束,由此产生了下面一些方法。


DFP方法

为保证B求解的唯一性,寻找满足条件约束并且离

Bk
最*的一个矩阵,因此问题转变为:





min||B?Bk||?s.tB=BT?Bsk=yk



如果上面范数选择Weighted Frobenius范数并且加权矩阵采用*均Hessian,则可以推导出一个唯一确定的解




Bk+1=(I?ρkyksTk)Bk(I?ρkyksTk)+ρkykyTk

其中




ρk=1/(yTksk)

。由于实际应用时会用到



Hk+1=B?1k+1
,根据一个求逆公式(Morrison-Woodbury)可以得到




Hk+1=Hk?HkykyTkHkyTkHkyk+sksTkyTksk



该构造方法称之为DFP方法


BFGS方法

类似于DFP方法,如果利用第二个拟牛顿方程,问题转变为:





min||H?Hk||?s.tH=HT?Hsk=yk



如果上面范数选择Weighted Frobenius范数并且加权矩阵采用*均Hessian,则可以推导出一个唯一确定的解




Hk+1=(I?ρkskyTk)Hk(I?ρkskyTk)+ρksksTk

其中




ρk=1/(yTksk)

。根据一个求逆公式(Morrison-Woodbury)可以得到




Bk+1=Bk?BksksTkBksTkBksk+ykyTkyTksk



该构造方法称之为BFGS方法,利用四个发明者名字进行命名。


DFP和BFGS关系

可以看到DFP和BFGS好像是将

sk,yk以及Bk,Hk
进行了位置替换。理论证明他们互为对偶。



    BFGS和DFP一个比较好的性质是,如果H_k是正定的,则下一个

    Hk+1
    也是正定的,可以从公式中推导出来。BFGS和DFP都有一定能力进行自我修正,如果某个位置选择的矩阵不好,在未来几步呢,可以自我修复。这个能力,BFGS比DFP效果要好,这也是BFGS比较常用的原因。不好的地方就是:需要存储这个对称矩阵。


BFGS算法如下图所示



实际实现中初始值

H0
一般选择单位,初始化步长为1。 Wolfe条件中的参数

c1=10?1,c2=0.9



SR-1方法

上面推导DFP和BFGS方法是从最优化角度进行考虑,由于满足拟牛顿方程解个数不止一个,另外一个自然的想法就是通过对

Bk
进行修正从而得到

Bk+1
,即





Bk+1=Bk+ΔBk

。*惯上根据



ΔBk
的秩来称呼校正公司,例如秩-1校正公式和秩-2校正公式


秩-2校正公式

DFP秩-2校正公式





Hk+1=Hk+asksTk+bHkykyTkHk



BFGS秩-2校正公式




Bk+1=Bk+aykyTk+bBksksTkBk

根据拟牛顿方程可以推导出参数a和b的值,最终结果和上述最优化问题保持一致。


秩-1校正公式(SR-1)

SR-1校正公式为





Hk+1=Hk+vkvTk

根据拟牛顿条件可以推导出




Hk+1=Hk+(sk?Hkyk)(sk?Hkyk)T(sk?Hkyk)Tyk



优缺点

相对与BFGS



    SR1能够更好的拟合Hessian矩阵,因此在一些带约束的问题或者部分可导的函数,不总是能满足Wolfe条件或者

    sTkyk
    是大于0的SR1最大缺点是不能保证每一求解到的矩阵

    Hk+1
    是正定的


Broyden族校正公式

校正公式为:





Hk+1=Hk+asksTk+b(HkyksTk+skyTkHk)+cHkykyTkHk

可以根据牛顿条件求解到参数值。


SR-1、DFP和BFGS都是该一族算法,共同的问题是
1) 不能利用目标函数的稀疏性质
2)需要存储中间矩阵H


收敛性

拟牛顿方法具有全局收敛性并且有超线性的收敛速度



总结

通过本节的学*能够了解
1. 拟牛顿方程以及由来
2. DFP、BFGS方法的迭代公式以及使用条件、场景和优缺点
3. 了解其收敛速度

相关推荐

最新更新

猜你喜欢