§2.1精确线搜索及其Matlab实现 精确线搜索分为两类.一类是使用导数的搜索，如插值法，牛顿 法及抛物线法等；另一类是不用导数的搜索，如0.618法，分数法及成 功-失败法等.本书仅介绍0.618法和二次插值逼近法 1.黄金分割法 黄金分割法也称为0.618法，其基本思想是通过试探点函数值的 比较，使得包含极小点的搜索区间不断缩小.该方法仅需要计算函数 值，适用范围广，使用方便.下面我们来推导0.618法的计算公式 设 φ(s)=f(xk+sdk), 其中(s)是搜索区间[ao,bo]上的单峰函数.在第i次迭代时搜索区 间为[a,b.取两个试探点为pi,9∈[a,b吲且p:<q.计算p(p)和 Back Close
6/35 JJ II J I Back Close §2.1 °(Ç|¢9Ÿ Matlab ¢y °(Ç|¢©è¸a. òa¥¶^Í|¢, Xä{, ⁄Ó {9‘Ç{ ; ,òa¥ÿ^Í|¢, X 0.618 {, ©Í{9§ ı-î}{ . ÷=0 0.618 {⁄gä%C{. 1. ë7©{ ë7©{è°è 0.618 {, Ÿƒ g饜L£&:ºÍä ', ¶ù¹4:|¢´mÿ‰†. Tê{=IáOéºÍ ä, ·^âå2, ¶^êB. e°·Ç5Ì 0.618 {Oé˙™. φ(s) = f(xk + sdk), Ÿ• φ(s) ¥|¢´m [a0, b0] ˛¸¸ºÍ. 31 i gSìû|¢´ mè [ai , bi ]. ¸á£&:è pi , qi ∈ [ai , bi ] Ö pi < qi . Oé φ(pi) ⁄
(q).根据单峰函数的性质，可能会出现如下两种情形之一： (1)若(p)≤p(q),则令a+1:=ai,b+1:=q (2)若p(p)>p(q),则令a+1:=p,b+1:=b, 我们要求两个试探点p,和q满足下述两个条件： (a)[a,qi与p,b吲l的长度相同，即b,-p=q-a (b)区间长度的缩短率相同，即b+1一a+1=t(b:一a): 从而可得 Pi=ai+(1-t)(bi-ai),qi=ai+t(bi-ai). (2.5) 现在考虑情形(1).此时，新的搜索区间为 aiti,bit1 [ai,Qil. Back Close
7/35 JJ II J I Back Close φ(qi). 䂸¸ºÍ5ü, åU¨—yXe¸´ú/Éò: (1) e φ(pi) ≤ φ(qi), K- ai+1 := ai , bi+1 := qi ; (2) e φ(pi) > φ(qi), K- ai+1 := pi , bi+1 := bi . ·Çᶸá£&: pi ⁄ qi ˜ve„¸á^á: (a) [ai , qi ] Ü [pi , bi ] ›É”, = bi − pi = qi − ai ; (b) ´m›†·«É”, = bi+1 − ai+1 = t(bi − ai). l å pi = ai + (1 − t)(bi − ai), qi = ai + t(bi − ai). (2.5) y3ƒú/ (1). dû, #|¢´mè [ai+i , bi+1] = [ai , qi ]
为了进一步缩短搜索区间，需取新的试探点P+1,q9+1.由(2.5)得 q+1=a+1+t(b+1-a+1) =ai+t(qi-ai) ai +t2(bi-ai). 若令 t2=1-t,t>0, (2.6) 则 qi+1=a+(1-t)(b:-a)=p. 这样，新的试探点q+1就不需要重新计算.类似地，对于情形(2)，也有 相同的结论 解方程(2.6)得区间长度缩短率为 t=6、1 ≈0.618. Back 2 Close
8/35 JJ II J I Back Close è ?ò⁄†·|¢´m, I#£&: pi+1, qi+1. d (2.5) qi+1 = ai+1 + t(bi+1 − ai+1) = ai + t(qi − ai) = ai + t 2 (bi − ai). e- t 2 = 1 − t, t > 0, (2.6) K qi+1 = ai + (1 − t)(bi − ai) = pi . ˘, #£&: qi+1 “ÿIá#Oé. aq/, Èuú/ (2), èk É”(ÿ. )êß (2.6) ´m›†·«è t = √ 5 − 1 2 ≈ 0.618
因此，我们可以写出0.618法的计算步骤如下. 算法2.2(0.618法) 步0确定初始搜索区间[0，bo]和容许误差e>0.计算初始试 探点 p0=a0+0.382(b0-a0),q0=a0+0.618(bg-a0) 及相应的函数值p(po),p(q0).置i:=0. 步1若(P)≤(q),转步2；否则，转步3. 步2计算左试探点.若q:一a≤e,停算，输出Pi.否则，令 a+1:=a,b+1:=qi,p(9i+1）:=(P), 9i+1=p,Pi+1=a+1+0.382(b+1-a+). 计算(p+1),i:=i+1,转步1. Back Close
9/35 JJ II J I Back Close œd, ·Çå±— 0.618 {Oé⁄½Xe. é{ 2.2 (0.618 {) ⁄ 0 (½–©|¢´m [a0, b0] ⁄NNÿ ε > 0. Oé–©£ &: p0 = a0 + 0.382(b0 − a0), q0 = a0 + 0.618(b0 − a0) 9ÉAºÍä φ(p0), φ(q0). ò i := 0. ⁄ 1 e φ(pi) ≤ φ(qi), =⁄ 2; ƒK, =⁄ 3. ⁄ 2 OéÜ£&:. e |qi − ai | ≤ ε, é, —— pi . ƒK, - ai+1 := ai , bi+1 := qi , φ(qi+1) := φ(pi), qi+1 := pi , pi+1 := ai+1 + 0.382(bi+1 − ai+). Oé φ(pi+1), i := i + 1, =⁄ 1
步3计算右试探点.若b-p≤e,停算，输出q.否则，令 ai+1:=P,b+1:=bi,p(pi+1):=p(q), Pi+1:=qi, 9i+1:=ai+1+0.618(b+1-a+) 计算(q+1),i=i+1,转步1. 值得说明的是，由于每次迭代搜索区间的收缩率是t=0.618,故 0.618法只是线性收敛的，即这一方法的计算效率并不高.但该方法每 次迭代只需计算一次函数值的优点足以弥补这一缺憾. 下面给出用0.618法求单变量函数中在单峰区间上近似极小点 的Matlab程序， 程序2.1(0.618法程序)用0.618法求单变量函数中在单峰区 间[a,bl上的近似极小点. function [s,phis,k,G,E]=golds(phi,a,b,delta,epsilon) Back %输入：phi是目标函数，a,b是搜索区间的两个端点 Close
10/35 JJ II J I Back Close ⁄ 3 Oém£&:. e |bi − pi | ≤ ε, é, —— qi . ƒK, - ai+1 := pi , bi+1 := bi , φ(pi+1) := φ(qi), pi+1 := qi , qi+1 := ai+1 + 0.618(bi+1 − ai+). Oé φ(qi+1), i := i + 1, =⁄ 1. ä`²¥, duzgSì|¢´m¬†«¥ t = 0.618, 0.618 {ê¥Ç5¬Ò, =˘òê{Oé«øÿp. Tê{z gSìêIOéògºÍä`:v±ë÷˘ò"Ã. e°â—^ 0.618 {¶¸C˛ºÍ φ 3¸¸´m˛Cq4: Matlab ßS. ßS 2.1 (0.618 {ßS) ^ 0.618 {¶¸C˛ºÍ φ 3¸¸´ m [a, b] ˛Cq4:. function [s,phis,k,G,E]=golds(phi,a,b,delta,epsilon) %—\: phi¥8IºÍ, a, b ¥|¢´m¸á‡: