文档介绍：第六章一维搜索
本章主要内容:一维搜索的概念及其性质搜索区间的概念及其确定搜索区间的
进退法单谷函数的概念及其性质 、i法、
Newton切线法、割线法、二次插值法、Armijo-Goldstein法、
Wolfe-Powell法、后退法
教学目的及要求:理解一维搜索的概念并掌握其性质,理解搜索区间的概念并掌
握确定搜索区间的进退法,理解单谷函数的概念并掌握其性质,
;掌握Newton切线法、割线法、
二次插值法,了解Armijo-Goldstein法、Wolfe-Powell法、后退
法。
教学重点:.
教学难点:Armijo-Goldstein法.
教学方法:启发式.
教学手段:多媒体演示、演讲与板书相结合.
教学时间:5学时.
教学内容:
§ 一维搜索
给定,令.
定义如果求得步长,使得
()
.
定理1 对于问题,设是可微函数,是从出发沿方向作最优一维搜索得到的,则有.
,由满足()式,可知是的极小点,因此,即
.
定义如果选取,使目标函数沿方向取得适当的可接受的下降量,即使得下降量是我们可接受的,则称这样的一维搜索为可接受一维搜索或非精确一维搜索.
定义设,,那么称是问题的搜索区间.
定义设,若存在,使得在上严格单调减少,在上严格单调增加,则称是的单谷区间,是上的单谷函数或单峰函数.
定理2 设为的单谷区间,,且,那么
(1)若,则是的单谷区间;
(2)若,则是的单谷区间.
(1),,,从而,这与(1)(2).
算法6-1(进退法)
Step1 ,初始步长,加倍系数(一般取),计算,置.
Step2 ,计算.
Step3 ,转Step4;否则,转Step5.
Step4 ,转Step2.
Step5 ,转换搜索方向,,转Step2;否则,.
§
,并设在上为单谷函数,,只需增加两个试探点,就可把搜索区间缩短.
任取且,当时,取;当时,,,得一搜索区间序列:,
且,当时,中任一点都可作为的近似值.
那么,应当如何选择试探点呢?
在每次收缩区间时,新的搜索区间内已保留一个旧的试探点,:,.
,搜索区间为,为进一步缩短搜索区间,选取两个试探点,且,则有
情形1 当时,.
情形2 当时,.
现在要确定,使它们满足下述两个条件:
(1),不管删去哪一段,新的搜索区间
的长度不依赖于第次迭代结果,
, ()
. ()
对于情形1和情形2,式()分别对应如下两式:
, ()
. ()
由式()和()分别得到
, ()
. ()
(2)为减少计算量,在第次迭代中,保留一个旧的试探点,只增加一个新的试探点。
对情形1,由()和()两式,有
. ()
对情形2,由()和()两式,有
. ()
比较()和()式以及()和()式得
. ()
这就是当试探点满足条件(1)和(2)时,应满足的条件.
在(常数)的条件下,由()式得到
. ()
解得.
于是,由()和():
算法6-2()
Step1 .
Step2 计算最初两个试探点:,,求出,并置.
Step3 检查?是,停止计算,输出;否则,转Step4.
Step4 ,转Step5;若,转Step6.
Step5 .
并计算,转Step7.
Step6 .
并计算,转Step7.
Step7 置,转Step3.
i法.
定义 i数是指满足下述条件的数列:
()
用数学归纳法可以证明,i数可由下式表示:
. ()
现在来看