最优化理论与应用-5

《最优化理论与应用-5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化理论与应用第5讲-线搜索方法电子科技大学自动化工程学院彭晓明1内容提要步长的选择牛顿法中Hessian矩阵的修改2步长的选择Wolfe条件Goldstein条件步长选择的一些算法牛顿法中Hessian矩阵的修改3步长的选择对于线搜索方法首先要选择一个使得函数值下降的方向，即满足f(x)Tp<0kk下一步是选择步长αk使得目标函数值能够充分的降低但我们同时又希望不要付出太高的计算代价，即不要搜索ϕ(α)=f(x+αp)的全局最优解4kkkk充分减少条件(sufficientdecreasecondition)(sufficientdecreasecondi

2、tion)如果选择步长α仅使得目标函数k值下降是不够的举例f(x)=(x+1)2x(k)=5/k,k=1,2,…不能收敛到最优解x=-1由此引出“充分减少”的概念5充分减少条件(sufficientdecreasecondition)(sufficientdecreasecondition)步长α需要满足以下的“充分减少条件”[也称为Armijo条件(Armijoconditions)]其中常量c(01)(0,1)[很小，例如110-4]即f(x)的减少值与α和f(x)Tp成kkk正比6充分减少条件(sufficientdecreasecondition)(suffi

3、cientdecreasecondition)7曲率条件(curvaturecondition)(curvaturecondition)仅充分减少条件还不够，因为这时步长α取值可能很小（见上页图）k为了排除这些小的步长，需要进一步满足“曲率条件”其中cc((1,1))218曲率条件(curvaturecondition)(curvaturecondition)可以证明：不等式的左边其实是ϕ’(α)[见Nocedal,p.629]k所以，曲率条件要求满足：函数ϕ(α)在α处的斜率要大于或等于kϕ’(0)的c倍29曲率条件(curvaturecondition)(curvat

4、urecondition)10Wolfe条件(Wolfeconditions)(Wolfeconditions)把这两个条件合在一起，构成了“Wolfe条件”11Wolfe条件(Wolfeconditions)(Wolfeconditions)12强Wolfe条件(strongWolfeconditions)(strongWolfeconditions)注意其曲率条件与Wolfe条件中的曲率条件的差别其目的是将步长限制在一个极小值的邻域中13强Wolfe条件(strongWolfeconditions)(strongWolfeconditions)ϕ’(0)-cϕ’(()0)c

5、ϕ’(0)22ϕ(α)l(α)α满足强Wolfe条件的α取值范围14强Wolfe条件(strongWolfeconditions)(strongWolfeconditions)ϕ’(0)-cϕ’(()0)cϕ’(0)22ϕ(α)l(α)α满足强Wolfe条件的α取值范围15强Wolfe条件(strongWolfeconditions)(strongWolfeconditions)可以证明：假设目标函数连续可微，选择p是一个下降方向，则一k定可以找到包含满足Wolfe条件和强Wolfe条件的步长的区间(见Nocedal,Lemma3.1,p.35)。16Goldstein条件(Gol

6、dsteinconditions)(Goldsteinconditions)目的：目标函数值获得充分的减少，且步长不能太短缺点：可能排除ϕ(α)的所有极k小点17Goldstein条件(Goldsteinconditions)(Goldsteinconditions)18步长的选取目的：从一个初始的步长α出发0，生成一个步长序列{α}，直到找i到（或找不到）一个满足给定条件的步长终止。可以分为两个阶段包括阶段(bracketingphase)选择阶段(selectionphase)19步长的选取包括阶段((gbracketingpphase))找到一个包含所求步长的区

7、间[,]ab选择阶段(selectionphase)(selectionphase)在区间[,]ab中找到满足条件的步长20回溯线搜索(backtrackinglinesearch)(backtrackinglinesearch)目的：从一个初始的步长出发，找到一个满足充分减少条件的步长对于牛顿法和拟牛顿法，初始步长可以设为121内插法((p)interpolation)回顾一下充分减少条件如果该条件不满足，我们知道在区间[0,]中包含了可