拟牛顿法及其相关解法

本文链接：/miaowei/52925.html最近在看条件随机场中的优化算法。其中就设计到了无约束化的最优化方法，也就是牛顿法。在CRF（conditionalrandomfield）中，使用的是L-BFGS法。费了好大的劲把算法的原理及推导算是看明白了，可是到了具体实现上，又碰到问题了，比如在求搜索方向的时候，使用H屮={I- -仇丫闾.）十p収吕?=vjHg+pe应但是程序中如何实现呢？现在转载一篇文章，看过之后，会非常受益。使用导数的最优化算法中，拟牛顿法是目前为止最为行之有效的一种算法，具有收敛速度快、算法稳定性强、编写程序容易等优点。在现今的大型计算程序中有着广泛的应用。本文试图介绍拟牛顿法的基础理论和若干进展。牛顿法（NewtonMethod）牛顿法的基本思想是在极小点附近通过对目标函数做二阶Taylor展开，进而找到’；的极小点的估计值［1］。一维情况下，也即令函数*打为齐（『）=+f际〕（T—跌）+訂"际）（T—It）则其导数'’满足了•盟=广:叫+广（咖仗一mJ=0因此——⑴将、+作为；极小点的一个进一步的估计值。重复上述过程,可以产生一系列的极小点估值集合'。一定条件下，这个极小点序列：收敛于；的极值点。将上述讨论扩展到,维空间，类似的，对于，维函数*有f（xj4/'；XJ=fZ+WRx-和J十戏天—x^.jTV2/（x-观j其中*和W人分别是目标函数的的一阶和二阶导数，表现为匸维向量和.■■■'-.''■■■矩阵，而后者又称为目标函数*在x处的Hesse矩阵。设设；可逆，则可得与方程⑴类似的迭代公式：人 了 V<-:s V：s ⑵这就是原始牛顿法的迭代公式。原始牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初始点需要尽量靠近极小点，否则有可能不收敛。因此人们又提出了阻尼牛顿法［1］。这种方法在算法形式上等同于所有流行的优化方法，即确定搜索方向，再沿此方向进行一维搜索，找出该方向上的极小点，然后在该点处重新确定搜索方向，重复上述过程，直至函数梯度小于预设判据,。具体步骤列为算法1。算法1:(1)给定初始点H，设定收敛判据■，二⑵计算和.⑶若「’峠<-,则停止迭代，否则确定搜索方向』 \ % '、.⑷从出发，沿做一维搜索，n护f凶-+人山j=f(xk+Xk-dk)令 •⑸设•； “I，转步骤⑵•在一定程度上，阻尼牛顿法具有更强的稳定性。拟牛顿法(Quasi-NewtonMethod)如同上一节指出，牛顿法虽然收敛速度快，但是计算过程中需要计算目标函数的二阶偏导数，难度较大。更为复杂的是目标函数的Hesse矩阵无法保持正定，从而令牛顿法失效。为了解决这两个问题，人们提出了拟牛顿法。这个方法的基本思想是不用二阶偏导数而构造出可以近似Hesse矩阵的逆的正定对称阵，从而在"拟牛顿"的条件下优化目标函数。构造方法的不同决定了不同的拟牛顿法。首先分析如何构造矩阵可以近似Hesse矩阵的逆：设第k次迭代之后得到点，将目标函数 在处展成Taylor级数，取二阶近似，得到gf^k+1]+ -F Xj叶]]因此v/(x)RS ,j+V2孑(強+1)(兀-XjfcHj令鼻，则人 7人 匸:S S ⑶记科=X<+|-也一Yl= i-vy(XL.j同时设Hesse矩阵'、： 可逆，则方程(3)可以表示为rVJ;:s v⑷因此，只需计算目标函数的一阶导数，就可以依据方程(4)估计该处的Hesse矩阵的逆。也即，为了用不包含二阶导数的矩阵H 近似牛顿法中的Hesse矩阵 的逆矩阵」丨必须满足方程(5)也称为拟牛顿条件。不加证明的，下面给出两个最常用的H 构造公式DFP公式设初始的矩阵】I为单位矩阵]，然后通过修正11给出H，即H忡=H,+AH,DFP算法中定义校正矩阵为\TT_軌抚氐皿,-阳4-球班-yiH1,y,因此]| ]|氏 ⑹可以验证，这样产生的H 对于二次凸函数而言可以保证正定，且满足拟牛顿条件。BFGS公式BFGS公式有时也称为DFP公式的对偶公式。这是因为其推导过程与方程(6)完全一样只需要用矩阵汗取代“ ，同时将“和匸互换，最后可以得到]|H-占&十(7)这个公式要优于DFP公式，因此目前得到了最为广泛的应用。利用方程(6)或(7)的拟牛顿法计算步骤列为算法2。算法2:⑴给定初始点x，设定收敛判据•，二人⑵设II1，计算出目标函数 在处的梯度⑶确定搜索方向门：酥=H丄馱⑷从出发，沿訂做一维搜索，满足fQu+人心1= +Xdu令尤卜十1=总-+九血⑸若 •-，则停止迭代，得到最优解* X ，否则进行步骤(6).⑹若二厶 ，则令X ' ，回到步骤(2)，否则进行步骤(7).⑺令' ， ' '，亠｛，利用方程(6)或(7)计算H ，设匸1，回到步骤(3)。限域拟牛顿法(LimitedStorageQuasi-NewtonMethod)算法2的步骤(3)中，为了确定第:次搜索方向，需要知道对称正定矩阵］I，因此对于匸维的问题，存储空间至少是'-，对于大型计算而言，这显然是一个极大的缺点。作为比较，共轭梯度法只需要存储3个」维向量。为了解决这个问题Nocedal首次提出了基于BFGS公式的限域拟牛顿法(L-BFGS)［2］。L-BFGS的基本思想是存储有限次数(如…次)的更新矩阵3I，如果＞'-，的话就舍弃…次以前的工1-，也即L-BFGS的记忆只有…次。如果…，则L-BFGS等价于标准的BFGS公式。首先将方程(7)写为乘法形式：H屮=(I -“y闾.］十阳闾.=讦印M+吋应其中」…八是- 的矩阵。乘法形式下"舍弃"等价于置「 】，：•：。容易得出，给定…后，BFGS的矩阵更新可以写为若• -，则Hb+1 HiVu-Vk-.Vk+vj-^：is：is.jV；…¥上(10)方程(9)和(10)称为狭义BFGS矩阵(specialBFGSmatrices)。仔细分析这两个方程以及-和「的定义，可以发现L-BFGS方法中构造 只需要保留 个维向量：个、…个丫以及］I(对角阵)。快速计算I-L-BFGS算法中确定搜索方向H需要计算HM，下列算法可以高效地完成计算任务：算法3:IF丄■■-Then■=0;=

ELSE|■:-= …；丨：'：|〔|=■■-ENDIFc]'I: .- ；DO=( -1),0,-1储存“；qq■■v；ENDDO1'II｛；DO=0,( -1)-.■：'.;':'VT；ENDDO完整的程序包可从下列网址下载：/~nocedal/software.html针对二次非凸函数的若干变形对于二次凸函数，BFGS算法具有良好的全局收敛性。但是对于二次非凸函数，也即目标函数Hesse矩阵非正定的情况，无法保证按照BFGS算法构造的拟牛顿方向必为下降方向。为了推广BFGS公式的应用范围，很多工作提出了对BFGS公式稍作修改或变形的办法。下面举两个例子。Li-Fukushima方法[3]Li和Fukushima提出新的构造矩阵H的方法：日屮={I-皿旺疳冋([-皿疳胡)+日屮={I-皿旺疳冋([-皿疳胡)+伽就(11)其中的定义见算法2中步骤(7)，而除此之外，算法2中步骤(3)的一维搜索采用如下方式：给定两个参数「「〔和匚「」一，找出最小的非负整数j，满足fg十巧业）<打严）+G,以血：取：=；,步长' '。Xiao-Wei-Wang方法［4］Xiao、Wei和Wang提出了计入目标函数值•’久的另一种］I的构造方法:护Y■' ，其中%= -f（粘十J+｛臥十I+乱］丁昌札II的构造方法与方程（7）和（11）形式相同：日屮=（I-心剧丁旧川-仮口話+詁刊話相应的v-而一维搜索则采用弱Wolfe-Powell准则：给定两个参数'：■-和■■'■ 1，找出步长〔，满足-』-（14）如果，=•满足方程（13）、（14），则取一：=一。可以看出，这两种方法只是改变了丫的定义方式，其他则与标准的BFGS方法完全一样。因此将二者推广到限域形式是非常直接的，这里不再给出算法。对于二次非凸函数的拟牛顿方法还在进一步发展当中，上述的两个例子并不一定是最佳算法。一维搜索使用导数的优化算法都涉及到沿优化方向」的一维搜索。事实上一维搜索算法本身就一个非常重要的课题，分为精确一维搜索以及非精确一维搜索。标准的拟牛顿法或L-BFGS均采用精确一维搜索。与前者相比，非精确一维搜索虽然牺牲了部分精度，但是效率更高，调用函数的次数更少。因此Li-Fukushima方法和Xiao-Wei-Wang方法中均采用了这类算法。不加证明的，本节分别给出两类范畴中各自的一个应用最为广泛的例子，分别是二点三次插值方法和Wolfe-Powell准则。二点三次插值方法在精确一维搜索各种算法中，这种方法得到的评价最高。其基本思想是选取两个初始点：和=，满足' <：?J>o这样的初始条件保证了在区间^1；：'一中存在极小点。利用这两点处的函数值、’■-（记为「、二）和导数值•’'、•‘T（记为•’、」）构造一个三次多项^5「，使得在：和亠处与目标函数；有相同的函数值和导数值，则设■■' ■' - ，‘ - ■ ■-- ［那么通过4个边界条件可以完全确定■■、、、

;4个参数。之后找出」:的零点-’，作为极小点的一个进一步的估计。可以证明，由：出发，最佳估计值的计算公式为1 (15)为了避免每次都要求解4维线性方程组的麻烦，整个搜索过程可以采用算法4:算法4:⑴给定初始点：和，满足< ，计算函数值’、二和导数值•’、二，并且•’<:>:，给定允许误差：。(2)计算如下方程，得到最佳估计值-■:' 一-二，'■'.'2(16)F=F=k+h卫—釣 芥;J(17)⑶若"一■:二，则停止计算，得到点：；否则进行步骤(4)。⑷计算’：和「：。若：’心‘，则停止计算，得到点：,若•’； <：，则令； ''■' ■'' ■' ■';，转步骤(2);若•’ ■' >:，则令■' ■-■' ' ■'，转步骤(2)。禾I」用三次函数插值，方程(16)、(17)并不是唯一的方法，也可以利用下式计算、、三个参数：._了；打；hhzzhl.a~I：!'，-!'l；J—I：J.—纠-JIJ/j~/l-(18)c~然后利用(15)式寻找最佳点［5］o此外即使’-<：一般而言也可以用(15)式外推寻找-'(参见［5］)。Wolfe-Powell准则不等式(13)、(14)给出了这种非精确一维搜索算法。如果我们将不等式(14)用下式替换：-'丨 二」(19)也即说心<显+1比<—疔歸血-则不等式(13)、(19)称为强Wolfe-Powell准则。其重要性在于当——…时，该方法过渡为精确一维搜索算法［6］。算法如下［5］算法5:(1)给定两个参数'■ : 和■■■'■ 为初始点(相应于， 八)，匚为猜想点(可设为1)。计算两点处的函数值「、二和导数值给定最大循环次数'■■■■---,设二匸=二;⑵若二和二违反不等式(13)或者不等式(19)的右半段，则缩小搜索范围的上限 ，否则转步骤⑸；⑶若二＞■'，利用二次插值方法寻找最佳点＞■:Jj-fi-fi'i-rj-.riJ设：」 ，计算二和'」；设 ，若 转步骤(2),否则转步骤(5)；若，二-，转步骤(4)；⑷禾I」用式(16)、(17)(或者式(15)、(18))寻找最佳点I＞.。令■-=■.■■■■.，计算二和二；设= ，若 ，转步骤(2),否则转步骤(5)；⑸若满足不等式(19)的左半段，则停止计算，得到最佳点否则转步骤(6)；⑹禾I」用式(16)、(17)(或者式(15)、(18))寻找最佳点并计算二以及二；设二-若转步骤(2),否则转步骤(7)；(7)停止计算得到目前最佳估计值：J。需要补充说明的是步骤(4)可以有不同的估算方法，例如此外，点处的导数值-，5,因为在一维搜索中，相当于待求步长。在大多数情况下，-以及：=•可以取得很好的效果。Wolfe-Powell准则的几何意义可以参考文献[5][6]。参考文献【1】陈宝林《最优化理论与算法(第二版)》(清华大学出版社2005)第9-10章.【2】J.Nocedal,Math.Comput.35,773(1980).【3】D.H.LiandM.Fukush