发布时间 : 星期一 文章最优化理论与算法(第二章)更新完毕开始阅读a7d1d02de2bd960590c6773b
用反证法证明 若?f(xk)不趋于零,那么存在??0和一个子序列{xk}K1,使得k?K1时,
?f(xk)??,
由此可推得 事实上,由 ?k??kdk?0(k?K1,k??)。
?2?? ,有
cos?k?cos(??)?sin?。
2?再由 ??f(xk)T?kdk??f(xk)即得
?kdkcos?k?0
?kdk?0, (k?K1,k??)。
另一方面,由?f(xk)的一致连续性有:
f(xk?1)?f(xk)??f(xk)T?kdk??(?kdk)
故有
?(?kdk)f(xk)?f(xk?1) ?1???f(xk)T?kdk??f(xk)T?kdk注意到k?K1,k??时,有
?(?kdk)?(?kdk)?kdk。 ???0(前一因子极限为0,后一因子有界)
??f(xk)T?kdk?kdk??f(xk)T?kdk事实上:0??kdk??f(xk)T?kdk??kdk?kdk1。 ???f(xk)?kdkcos?k?sin??kdk?sin?由此即得
f(xk)?f(xk?1)?1,
??f(xk)T?kdk这与f(xk??kdk)?f(xk)?(1??)?f(xk)T?kdk矛盾。
类似的,若采用Wolfe-Powell准则,由?f(xk)的连续性,
?f(xk??kdk)T?kdk??f(xk)T?kdk??(?kdk) (?kdk?0)
?f(xk??kdk)T?kdk由此得: ?1 (由于当k?K1,k??时,?kdk?0)
?f(xk)T?kdkTT这与Wolfe—Powell第二准则?f(xk??kdk)dk???f(xk)dk (??1)矛盾,从而定理得证。
下面是另一形式的收敛定理:
25
定理2.15 设函数f(x)连续可微,?f(x)满足Lipschitz条件:
?f(x)??f(y)?Mx?y。
又设算法采用Wolfe-Powell准则,且dk与(??f(xk))的夹角?k满足
?k??2?? (0????2)
那么由算法产生的点列{xk},或者对某个k,有?f(xk或者f(xk)???,或者?f(xk)?0。 )?0,证明:不妨设?k,?f(xk)?0,且f(xk)有下界。由定理2.13(用到Lipschitz条件)
f(xk)?f(xk??kdk)?这里 ???(1??)M?f(xk)cos2?k??cos2?k?f(xk),
22?(1??)M。
于是: f(x0)?f(xk)?令k??,则有:
?[f(xi)?f(xi?1)]???cos2?i?f(xi)
i?0i?0k?1k?12*fx(?)f )??cos2?k?f(xk)?f(x0)?f* (limk?2k?0k??由cos?k?sin?有
?sin???f(xk)?f(x0)?f*
2k?0?2从而级数
?k?0??f(xk)收敛,故lim?f(xk)?0。
k??2下面定理给出不精确一维搜索条件下,每步迭代目标函数下降量的估计式。 定理2.16 设?k满足不精确一维搜索准则中第一条,若函数还满足:
my?yT?2f(x)y?My,(y?z)T??f(y)??f(z)???y?z
则必有:f(xk)?f(xk??kdk)?T222??1?Mm?kdk。
2证明:1)若dk?f(xk??kdk)?0,则
f(xk)?f(xk??kdk)???dkT?f(xk?tdk)dt0?k
26
??d[?f(xk??kdk)??f(xk?tdk)]dt???(?k?t)dkdt
00?kTk?k21???kdk22???1?Mm?kdk(最后一个不等式由1?Mm?2, ??1得)
2T2)若dk?f(xk??kdk)?0,由dkT?f(xk)?0,则必存在0??*??k使得
Tdk?f(xk??*dk)?0。
在xk??*dk处将函数展开,有
21M?*dk 221**f(xk??kdk)?f(xk??dk)?m(?k??)dk
2f(xk)?f(xk??*dk)?又由f(xk??kdk)?f(xk),因而有
M?*dk解得: 或
2?m(?k??*)dk
2?k?(1?Mm)?* ?*?1?k
1?Mm再由?k满足第一准则,故有:
f(xk)?f(xk??kdk)???k?dkT?f(xk)??k?dkT[?f(xk??*dk)??f(xk)]????k?*dk
2
???1?Mm?kdk, 定理证毕。
2 27