最优化方法及其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使目标函数∫沿方向d达到极小，即 f(k akdk)=min f(Ck adk), 0>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). Ç|¢k°(Ç|¢⁄ö°(Ç|¢É©. §¢°(Ç|¢, ¥ ç¶ αk ¶8IºÍ f ˜êï dk à4, = f(xk + αkdk) = min α>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].