《最优化理论与应用-5》由会员分享，可在线阅读，更多相关《最优化理论与应用-5（64页珍藏版）》请在金锄头文库上搜索。
1、最优化理论与应用最优化理论与应用第5讲-线搜索方法第 讲 线搜索方法电子科技大学电子科技大学 自动化工程学院自动化工程学院 彭晓明彭晓明彭晓明彭晓明1内容提要内容提要步长的选择步长的选择步长的选择步长的选择 牛顿法中牛顿法中Hessian矩阵的矩阵的 修改修改2步长的选择步长的选择步长的选择步长的选择 Wolfe条件条件 Goldstein 条件条件 步长选择的一些算法步长选择的一些算法 牛顿法中牛顿法中矩阵的矩阵的牛顿法中牛顿法中Hessian矩阵的矩阵的 修改修改修改修改3步长的选择步长的选择对于线搜索方法首先要选择对于线搜索方法首先要选择一一个个对于线搜索方法首先要选择个对于线搜索方法首
2、先要选择个 使得函数值下降的方向，即满足使得函数值下降的方向，即满足 f (xk)Tpk 0 下步是选择步长下步是选择步长下下一一步是选择步长步是选择步长k 使得目标函数值能够充分的降低使得目标函数值能够充分的降低使得目标函数值能够充分的降低使得目标函数值能够充分的降低 但我们同时又希望不要付出太高但我们同时又希望不要付出太高但我们同时又希望不要付出太高但我们同时又希望不要付出太高 的计算代价，即的计算代价，即不要搜索不要搜索 (k)=f (xk+kpk)的全局最优解的全局最优解4充分减少条件充分减少条件 (sufficient decrease condition)(sufficient d
3、ecrease condition)如果选择步长如果选择步长 仅使得目标函数仅使得目标函数如果选择步长如果选择步长k仅使得目标函数仅使得目标函数 值下降是不够的值下降是不够的 举例举例 f(x)=(x+1)2 x(k)=5/k, k=1,2, 不能收敛到最优解不能收敛到最优解1不能收敛到最优解不能收敛到最优解x=-1 由此引出由此引出“充分减少充分减少”的概念的概念由此引出由此引出充分减少充分减少的概念的概念5充分减少条件充分减少条件 (sufficient decrease condition)(sufficient decrease condition) 步长步长需要满足以下的需要满足以下
4、的“充分减充分减 步长步长需要满足以下的需要满足以下的充分减充分减 少条件”少条件”也称为也称为Armijo 条件条件 (Armijo conditions)其中常量其中常量很小很小例如例如(0 1)c 其中常量其中常量很小很小，例如例如 10-41(0,1)c 即即f(xk)的减少值的减少值与与和和f (xk)Tpk成成 比比正正比比6充分减少条件充分减少条件 (sufficient decrease condition)(sufficient decrease condition)7曲率条件曲率条件 (curvature condition)(curvature condition)仅充分
5、减少条件还不够仅充分减少条件还不够因为这时因为这时仅充分减少条件还不够仅充分减少条件还不够，因为这时因为这时 步长步长k取值可能很小取值可能很小（见上页图见上页图）步长步长k取值可能很小取值可能很小（见上页图见上页图） 为了排除这些小的步长，需要进一为了排除这些小的步长，需要进一 步满足“曲率条件”步满足“曲率条件”其中其中(1)cc其中其中821( ,1)cc曲率条件曲率条件 (curvature condition)(curvature condition)可以证明可以证明：不等式的左边其实是不等式的左边其实是可以证明可以证明：不等式的左边其实是不等式的左边其实是 (k)见Nocedal,
6、p.629见Nocedal,p.629 所以，曲率条件要求满足：函数所以，曲率条件要求满足：函数 ( )在在处的斜率要大于或等于处的斜率要大于或等于()在在k处的斜率要大于或等于处的斜率要大于或等于 (0)的的c2倍倍 (0)的的c2倍倍9曲率条件曲率条件 (curvature condition)(curvature condition)10Wolfe条件条件 (Wolfe conditions)(Wolfe conditions) 把这两个条件合在把这两个条件合在一一起起，构成构成把这两个条件合在起把这两个条件合在起，构成构成 了“了“Wolfe条件”条件”11Wolfe条件条件 (Wol
7、fe conditions)(Wolfe conditions)12强强Wolfe条件条件 (strong Wolfe conditions)(strong Wolfe conditions)注意其注意其曲率条件曲率条件与与Wolfe 条件中的条件中的 曲率条件的差别曲率条件的差别 其目的是将步长限制在个极小其目的是将步长限制在个极小其目的是将步长限制在其目的是将步长限制在一一个极小个极小 值的邻域中值的邻域中13值的邻域中值的邻域中强强Wolfe条件条件 (strong Wolfe conditions)(strong Wolfe conditions) (0)c (0)-c2(0)c2(0
8、)2 ( )( )()l()14满足强满足强Wolfe条件的条件的取值范围取值范围强强Wolfe条件条件 (strong Wolfe conditions)(strong Wolfe conditions) (0)c (0)-c2(0)c2(0)2 ( )( )()l()15满足强满足强Wolfe条件的条件的取值范围取值范围强强Wolfe条件条件 (strong Wolfe conditions)(strong Wolfe conditions)可以证明：假设目标函数连续可可以证明：假设目标函数连续可 微微选择选择是个下降方向是个下降方向则则微微，选择选择pk是是一一个下降方向个下降方向，则则
9、一一 定可以找到包含满足定可以找到包含满足Wolfe条件和强条件和强定可以找到包含满足定可以找到包含满足Wolfe条件和强条件和强 Wolfe条件的步长的区间条件的步长的区间(见见Nocedal, Lemma 3.1, p.35)。16Goldstein 条件条件 (Goldstein conditions)(Goldstein conditions) 目的目的：目标函数值获得充分的目标函数值获得充分的目的目的：目标函数值获得充分的目标函数值获得充分的 减少，且步长不能太短减少，且步长不能太短缺点缺点：可能排除可能排除( )的所有极的所有极缺点缺点：可能排除可能排除(k)的所有极的所有极 小点
10、小点17Goldstein 条件条件 (Goldstein conditions)(Goldstein conditions)18步长的选取步长的选取目的目的：从从一一个初始的步长个初始的步长0出发出发目的目的从个初始的步长从个初始的步长0出发出发 ，生成一个步长序列，生成一个步长序列i，直到找，直到找 到到（或找不到或找不到）个满足给定个满足给定条条到到（或找不到或找不到）一一个满足给定个满足给定条条 件件的步长终止的步长终止。件件的步长终止的步长终止。 可以分为两个阶段可以分为两个阶段可以分为两个阶段可以分为两个阶段 包括阶段(bracketing phase)包括阶段(bracketin
11、g phase) 选择阶段(selection phase)选择阶段(selection phase)19步长的选取步长的选取包括阶段包括阶段( (bracketinbracketing g p phasehase) )包括阶段包括阶段(g p)(g p) 找到一个包含所求步长的区间找到一个包含所求步长的区间 , a b选择阶段选择阶段(selection phase)(selection phase)选择阶段选择阶段(selection(selection phase)phase) 在区间在区间中找到满足条件的中找到满足条件的 , a b在区间在区间中找到满足条件的中找到满足条件的 步长步长
12、 , a b20回回溯线搜索溯线搜索 (backtracking line search)(backtracking line search) 目的目的：从从一一个初始的步长出发个初始的步长出发，目的目的从个初始的步长出发从个初始的步长出发， 找到一个满足找到一个满足充分减少条件充分减少条件的步的步 长长长长对于牛顿法和拟牛顿法，初始步对于牛顿法和拟牛顿法，初始步 长可以设为1长可以设为121内插法内插法(interpolation)(p)回顾回顾一一下充分减少条件下充分减少条件回顾下充分减少条件回顾下充分减少条件如果该条件不满足，我们知道在如果该条件不满足，我们知道在 区间区间中包含了可接受
13、的步长中包含了可接受的步长0区间区间中包含了可接受的步长中包含了可接受的步长 （见前面见前面FiFig g.3.3.3.3）00, （见前面见前面g g）22内插法内插法(interpolation)(p)对此对此，可以采用下面的可以采用下面的二二次次对此对此，可以采用下面的可以采用下面的次次 (quadratic)函数函数对对(0), (0) 和和 ()进行内插值进行内插值(0)进行内插值进行内插值可以验证可以验证可以验证可以验证23内插法内插法(interpolation)(p)新的步长新的步长1可以定义为可以定义为q()的极的极新的步长新的步长1可以定义为可以定义为q( )的极的极 小点
14、小点如果如果 还不满足充分减少条件还不满足充分减少条件如果如果1还不满足充分减少条件还不满足充分减少条件， 则可以继续进行下面的则可以继续进行下面的三三次次则可以继续进行下面的次则可以继续进行下面的次 (cubic)插值(cubic)插值24内插法内插法(interpolation)(p)三三次次( (cubiccubic) )插值插值：对对(0), (0), 次次()()插值插值对对( ), ( ), (0)和和(1)进行内插值进行内插值25内插法内插法(interpolation)(p)新的步长新的步长2可以定义为可以定义为c()的极的极新的步长新的步长2可以定义为可以定义为c( )的极的
15、极 小点小点26内插法内插法(interpolation)(p)这个过程可以这个过程可以一一直进行下去直进行下去：对对这个过程可以直进行下去这个过程可以直进行下去对对 (0), (0), (1)和和(2)进行内插进行内插 值并得到值并得到对对(0) (0) ()和和值并得到值并得到3,对对(0), (0), (2)和和 (3)进行内插值并得到进行内插值并得到4以此类以此类(3)进行内插值并得到进行内插值并得到4,以此类以此类 推推 当当i和和i-1相比过于接近或者相比过于接近或者i远远 小于小于时时可以可以小于小于i-1时时，可以可以27初始步长的选择初始步长的选择假设在假设在上一上一个解个解xk 1处对应的步长处对应的步长假设在个解假设在个解k-1处对应的步长处对应的步长 为为k-1,我们该如何为当前解我们该如何为当前解xk寻找寻找 个个初始的初始的步长步长从而通过计从而通过计一一个个初始的初始的步长步长0，从而通过计从而通过计 算算一一系列的系列的i而最终找到而最终找到k？算系列的算系列的i而最终找到而最终找到k？ 注意注意区区别别i和和i-1和和k和和k-1注意别注意别i和和i-1和和k和和k-1 28初始步长的选择初始步长的选择对于牛顿法
