当前位置：首页 > 最优化理论与算法（第二章）
用反证法证明 若?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
本文作者：...共分享92篇相关文档
