第二章无约束优化问题的算法

《第二章无约束优化问题的算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、沈阳大学课程名称优化理论与方法教案授课章节第二章无约束优化问题的算法目的要求常用的线性搜索法；无约束最优化方法重点难点常用的线性搜索法；无约束最优化方法编写时间：20年月曰第一节常用线性搜索法在算法的迭代格式=兀⑷+匕〃⑷中，在假设迭代点兀⑹和下降搜索方向d⑹为已知的情况下，求步长使/（严“）=/（尹+蚣炉）＜/（严）成立。下而介绍儿种求步长Qa的算法。一、直接法（0.618法）（求步长）单谷函数（下单峰函数）：设广为一元函数0（f）的极小点，若tx＜t2,当t2＜f时，必有0（片）＞处2）；当厶丫广时,必有处

2、）＜处

3、2），则称0（。为单谷函数（一个谷）。1搜索区I'可的确定：搜索区间的选取采取如下算法一进■退算法:给定初始点f，初始步长力。⑴计算+〃）；（2）若（p（t）＞（p（t+h）,搜索成功,歩长加倍,若（p{t+h）＜（p（t+3ft）,则AS#]=[a,r+3〃],否则步长继续加倍;hh（3）若（p（t）＜（p{t+li）,搜索失败，后退一步长，若（P⑴＜（p（t一一）,则44△h[a,b]=[t——』+甸,否则继续加倍后退步长。420.618算法的原理第二章第1页解得2=0.618。由此

4、可得八=ci+(1—A)(b—

5、ci)t2=a+2(Z?-a)30.618算法Stepl确定0⑴的初始搜索区间[a,b](进■退搜索法)、精度£；Step2计算t}=d+(1-Q)(b-a),(P、=(p(t)；Step3计算t2=q+2(b一a),(p2=(p(t2)；Step4若％>0,则令a=t}.如果b-a<£,取t"=°+",停止计算。否则令-t2,0

6、=02，转Step3,(此时a=tl,ti=t2,在新的[aybK间计算乙);Step5若(p’s，则令b=g如果b-a

7、片=d+(l_2)@_a),(p、=(p(t),转Step4o注意：t]=t2与『2=耳在计算机语言屮不是一回事，是一个赋值的过程。二、精确线性搜索法(解析法)求步长色，满足f(x(k)+色〃⑹)二min/(兀⑷+加伙))oa>()令0(。)=f(x(k)+ad{k}),(pa)=Vf(x(k)^-adik))Tda)=0设包含/(/)的极小值点广的搜索区间为[。,切，即e[a,h],在搜索区间内给定三点v斤0(心)v(p(t2),不妨取心=a.t=—^—42=b。令p(t)=aQ+a{t

8、+a2t2是三点(tj9(p(tt))(z=0,1,2)的拟合抛物线,且设t3是抛物线的极小点，即(如图)二ela2二1的-/；»仏)+£-)+0；-f2(/j-^2Wo)+(Z2_Z0W1)+(ZO~lW?)结束条件:(1)(2))

9、V『3，或『3

10、够精确但计算量较小。为确保目标函数下降，步长不能太大，同时步长又不能太小，所以给一个限定范围。1Goldstein准贝U取步2满足下式00(0)+a(p)tk注：对上式的理解，可以

11、当/(尤)是一元函数时的特殊情况去理解。夹在两直与曲线刖=f(严+忆⑹)相交两点之间的f满足条件式(2.6)和(2.7),称其为可接受区间。2WoIfe准则在Goldstein准贝忡，似>)的极小点在可接受区间以外，为克服这一缺点，Wolfe准则提出一个式(2.7)的替补条件，即呼(卅)^tkd(k))Tda)>(Nf(x{k))Td(k)(2.9)可接受区间是切线/的切点、直线°(/)=0(0)+“冰0"与曲线的交点Z间的/的取值区I'可。说明：o•越小，线性搜索越精确，但计算量大。第二节最速下降法对下降方向的确定。

12、条件：目标函数于(力连续可微，Yf(兀⑹)H0。分析：/(X)在兀⑷点处的一阶泰勒展开为jx{k}+td{t})=f(x(k))+tVf(x(k)yd(k)+o^d⑷

13、)由函数梯度反方向是函数下降最快的方向(由二元函数可以看出)，所以令护=-V/(xa))7'则/(兀⑷-W))=/(卅))-呵(严厂号(严)+。(财许)当r>0满