《数值最优化方法》课程教学课件（讲稿，打印版）线搜索技术

最优化方法及其Matlab程序设计 第二章线搜索技术 Back Close

1/35 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1Ÿ Ç|¢E‚

从本章开始，介绍无约束优化问题的一些常用数值方法.我们考 虑下面的无约束优化模型 min f(x). x∈Rn 众所周知，研究上述无约束优化问题的数值方法，不仅是出于实际问 题的需要，同时也是研究约束优化问题数值方法的基础。本章主要讨 论一维线搜索算法及其收敛性分析 我们在第1章论及无约束优化问题迭代算法的一般框架时，其中 有下面的一个迭代步： 通过某种搜索方式确定步长因子Qk,使得 f(Tk+akdi)<f(Tk). (2.1) 这实际上是(n个变量的)目标函数f(x)在一个规定的方向上移 动所形成的单变量优化问题，也就是所谓的“线搜索”或“一维搜索” Back Close

2/35 JJ II J I Back Close lŸm©, 0ÃÂ`zØKò ~^Íäê{. ·Ç ƒe°ÃÂ`z. min x∈Rn f(x). ا±, Ôƒ˛„ÃÂ`zØKÍäê{, ÿ=¥—u¢SØ KIá, ”ûè¥ÔƒÂ`zØKÍäê{ƒ:. ŸÃá? ÿòëÇ|¢é{9Ÿ¬Ò5©¤. ·Ç31 1 Ÿÿ9ÃÂ`zØKSìé{òѵeû, Ÿ• ke°òáSì⁄: œL,´|¢ê™(½⁄œf αk, ¶ f(xk + αkdk) < f(xk). (2.1) ˘¢S˛¥ (n áC˛) 8IºÍ f(x) 3òá5½êï˛£ ƒ§/§¸C˛`zØK, è“¥§¢/Ç|¢0½/òë|¢0

技术.令 (a)=f(Tk+adk), (2.2) 这样，搜索式(2.1)等价于求步长a使得 p(a)0 或 (a)=min (a). 0>0 若f(x)是连续可微的，那么由精确线搜索得到的步长因子α具有如 下性质： Vf(xk+ad)Td=0(亦即9+1d=0): Back (2.3) Close

3/35 JJ II J I Back Close E‚. - φ(α) = f(xk + αdk), (2.2) ˘, |¢™ (2.1) du¶⁄ αk ¶ φ(αk) 0 f(xk + αdk), ½ φ(αk) = min α>0 φ(α). e f(x) ¥ÎYåá, @od°(Ç|¢⁄œf αk ‰kX e5ü: ∇f(xk + αkdk) T dk = 0 ( ½= g T k+1dk = 0 ). (2.3)

上述性质在后面的算法收敛性分析中将起着重要的作用 所谓非精确线搜索，是指选取Q使目标函数∫得到可接受的下 降量，即△f=f(xk)-f(xk+ad)>0是可接受的 精确线搜索的基本思想是：首先确定包含问题最优解的搜索区 间，然后采用某种插值或分割技术缩小这个区间，进行搜索求解.下面 给出搜索区间的定义， 定义2.1设中是定义在实数集上一元实函数，a*∈[0，+∞)，并 且 (a)=min(a). (2.4) a>0 若存在区间[a,b]C[0,+o),使a*∈(a,b),则称[a,b是极小化问题 (2.4)的搜索区间.进一步，若a*使得(@)在[a,a]上严格递减，在 [a*,bl上严格递增，则称[a,b]是(a)的单峰区间，(a)是[a,b]上的 单峰函数 Back Close

4/35 JJ II J I Back Close ˛„5ü3￾°é{¬Ò5©¤•ÚÂX­áä^. §¢ö°(Ç|¢, ¥ç¿ αk ¶8IºÍ f å.e ¸˛, = ∆fk = f(xk) − f(xk + αkdk) > 0 ¥å.. °(Ç|¢ƒgé¥: ƒk(½ù¹ØKÅ`)|¢´ m, ,￾Ê^,´ä½©E‚†˘á´m, ?1|¢¶). e° â—|¢´m½¬. ½¬ 2.1  φ ¥½¬3¢Í8˛ò¢ºÍ, α ∗ ∈ [0, +∞), ø Ö φ(α ∗ ) = min α≥0 φ(α). (2.4) e3´m [a, b] ⊂ [0, +∞), ¶ α ∗ ∈ (a, b), K° [a, b] ¥4zØK (2.4) |¢´m. ?ò⁄, e α ∗ ¶ φ(α) 3 [a, α∗ ] ˛ÓÇ4~, 3 [α ∗ , b] ˛ÓÇ4O, K° [a, b] ¥ φ(α) ¸¸´m, φ(α) ¥ [a, b] ˛ ¸¸ºÍ.

下面介绍一种确定搜索区间并保证具有近似单峰性质的数值算 法一进退法，其基本思想是从一点出发，按一定步长，试图确定函数值 呈现“高-低高”的三点，从而得到一个近似的单峰区间， 算法2.1（进退法） 步1选取a0≥0，h0>0.计算0=(ao.置k=0. 步2令ak+1=a十hk,计算k+1=(ak+1.若k+1<k,转 步3，否则转步4. 步3加大步长.令hk+1=2hk,a=ak,ak=Qk+1,pk=pk+1, k=k十1，转步2 步4反向搜索或输出.若k=0,令h1=-h0,a=a1,a1=Q0, 1=p0,k=1,转步2；否则停止迭代，令 a minta,a+1,a maxta,a+1. 输出[a,. Back Close

5/35 JJ II J I Back Close e°0ò´(½|¢´møy‰kCq¸¸5üÍäé {—?Ú{, Ÿƒgé¥lò:—u, Uò½⁄, £„(½ºÍä •y/p-$-p0n:, l òáCq¸¸´m. é{ 2.1 (?Ú{) ⁄ 1 ¿ α0 ≥ 0, h0 > 0. Oé φ0 := φ(α0). ò k := 0. ⁄ 2 - αk+1 = αk + hk, Oé φk+1 := φ(αk+1). e φk+1 < φk, = ⁄ 3, ƒK=⁄ 4. ⁄ 3 \å⁄. - hk+1 := 2hk, α := αk, αk := αk+1, φk := φk+1, k := k + 1, =⁄ 2. ⁄ 4 áï|¢½——. e k = 0, - h1 := −h0, α := α1, α1 := α0, φ1 := φ0, k := 1, =⁄ 2; ƒK éSì, - a = min{α, αk+1}, a = max{α, αk+1}. —— [a, b].

§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¸á‡: