第一章 最優(yōu)化問題概述-最優(yōu)化方法課件

最優(yōu)化方法2目錄第一章最優(yōu)化問題概述第二章線性規(guī)劃第三章無約束最優(yōu)化方法第四章約束最優(yōu)化方法第一章

最優(yōu)化問題概述4§1.1最優(yōu)化問題的數(shù)學(xué)模型

與基本概念5例1.1.1運(yùn)輸問題設(shè)有m個(gè)水泥廠A1,A2,…,Am,年產(chǎn)量各為a1,a2,…,am噸.有k個(gè)城市B1,B2…,Bk用這些水泥廠生產(chǎn)的水泥,年需求量b1,b2,…,bk噸.再設(shè)由Ai到Bj每噸水泥的運(yùn)價(jià)為cij元.假設(shè)產(chǎn)銷是平衡的,即:試設(shè)計(jì)一個(gè)調(diào)運(yùn)方案,在滿足需要的同時(shí)使總運(yùn)費(fèi)最省.6A1

由題意可畫出如下的運(yùn)輸費(fèi)用圖:B2AmB1A2Bk產(chǎn)量需求量設(shè)Ai→Bj的水泥量為xij,已知Ai→Bj單價(jià)為cij,單位為元,則總運(yùn)費(fèi)為:7數(shù)學(xué)模型:注:平衡條件作為已知條件并不出現(xiàn)在約束條件中.8例1.1.2生產(chǎn)計(jì)劃問題設(shè)某工廠有m種資源B1,B2,…,Bm,數(shù)量各為:b1,b2,…,bm,用這些資源產(chǎn)n種產(chǎn)品A1,A2,…,An.每生產(chǎn)一個(gè)單位的Aj產(chǎn)品需要消耗資源Bi的量為aij,根據(jù)合同規(guī)定,產(chǎn)品Aj的量不少于dj.再設(shè)Aj的單價(jià)為cj.問如何安排生產(chǎn)計(jì)劃,才能既完成合同,又使該廠總收入最多?9假設(shè)產(chǎn)品Aj的計(jì)劃產(chǎn)量為xj.由題意可畫出如下的生產(chǎn)與消耗的關(guān)系圖:B1B2BmAnA2A1消耗10數(shù)學(xué)模型11例1.1.3指派問題設(shè)有四項(xiàng)任務(wù)B1,B2,B3,B4派四個(gè)人A1,A2,A3,A4去完成.每個(gè)人都可以承擔(dān)四項(xiàng)任務(wù)中的任何一項(xiàng),但所消耗的資金不同.設(shè)Ai完成Bj所需資金為cij.如何分配任務(wù),使總支出最少?設(shè)變量指派Ai完成bj不指派Ai完成bj12則總支出可表示為:數(shù)學(xué)模型:13例1.1.4數(shù)據(jù)擬合問題在實(shí)驗(yàn)數(shù)據(jù)處理或統(tǒng)計(jì)資料分析中常遇到如下問題.設(shè)兩個(gè)變量x和y,已知存在函數(shù)關(guān)系,但其解析表達(dá)式或者是未知的或者雖然為已知的但過于復(fù)雜.設(shè)已取得一組數(shù)據(jù):(xi,yi)i=1,2,…,m.根據(jù)這一組數(shù)據(jù)導(dǎo)出函數(shù)y=f(x)的一個(gè)簡(jiǎn)單而近似的解析表式.14最小二乘法解這種問題常用的方法是最小二乘法,以一個(gè)簡(jiǎn)單的函數(shù)序列j1(x),j2(x),···,jn(x)為基本函數(shù).一般選取1,x,x2,···,xn為基本函數(shù),即以作為近似表達(dá)式.15最小二乘法系數(shù)的選取要使得下面得平方和最小:因此,數(shù)據(jù)擬合問題得數(shù)學(xué)模型為其中xi,yi(i=1,2,…,m)及jj(x)(j=0,1,…,n)為已知.16最優(yōu)化問題最優(yōu)化問題的一般形式為:(1.1)(目標(biāo)函數(shù))(1.3)(不等式約束)(1.2)(等式約束)其中x是n維向量.在實(shí)際應(yīng)用中,可以將求最大值的目標(biāo)函數(shù)取相反數(shù)后統(tǒng)一成公式中求最小值的形式.17相關(guān)定義定義1.1.1(可行解)

滿足約束條件(1.2)和(1.3)的x稱為可行解,也稱為可行點(diǎn)或容許點(diǎn).定義1.1.2(可行域)全體可行解構(gòu)成的集合稱為可行域,也稱為容許集,記為D,即:D={x|hi(x)=0,i=1,···,m,gj(x)≥0,j=1,···,p,x∈Rn}.若hi(x),gj(x)為連續(xù)函數(shù),則D為閉集.18相關(guān)定義定義1.1.3(整體最優(yōu)解)

若x*∈D,對(duì)于一切x∈D恒有f(x*)≤f(x),則稱x*為最優(yōu)化問題(P)的整體最優(yōu)解.若x*∈D,x≠x*,恒有f(x*)<f(x),則稱x*為最優(yōu)化問題(P)的嚴(yán)格整體最優(yōu)解.19相關(guān)定義定義1.1.4(局部最優(yōu)解)

若x*∈D,存在x*的某鄰域Ne(x*),使得對(duì)于一切x∈D∩Ne(x*),恒有f(x*)≤f(x),則稱為最優(yōu)化問題(P)的局部最優(yōu)解,其中Ne(x*)={x|||x-x*||<e,e>0}.當(dāng)x≠x*時(shí),若上面的不等式為嚴(yán)格不等式則稱x*為問題(P)的嚴(yán)格局部最優(yōu)解.顯然,整體最優(yōu)解一定是局部最優(yōu)解,而局部最優(yōu)解不一定是整體最優(yōu)解.20相關(guān)定義求解最優(yōu)化問題(P),就是求目標(biāo)函數(shù)f(x)在約束條件(1.2),(1.3)下的極小點(diǎn),實(shí)際上是求可行域D上的整體最優(yōu)解.但是,在一般情況下,整體最優(yōu)解是很難求出的,往往只能求出局部最優(yōu)解.21向量范數(shù)定義1.1.5

如果向量x∈Rn的某個(gè)實(shí)值函數(shù)||x||,滿足條件(1)||x||≥0(||x||=0當(dāng)且僅當(dāng)x=0)(正定性);(2)||ax||=|a|·||x||(對(duì)于任意a∈R);(3)||x+y||≤||x||+||y||(三角不等式);則稱||x||為Rn上的一個(gè)向量范數(shù).22常用的向量范數(shù)1-范數(shù)2-范數(shù)(歐式范數(shù))∞-范數(shù)p-范數(shù)∞-范數(shù)是p-范數(shù)的極限23常用的向量范數(shù)對(duì)向量x=(1,-2,3)T,有||x||p是p的單調(diào)遞減函數(shù).24最優(yōu)化問題的分類根據(jù)數(shù)學(xué)模型中有無約束函數(shù)分為有約束的最優(yōu)化問題和無約束的最優(yōu)化問題.根據(jù)目標(biāo)函數(shù)和約束函數(shù)的函數(shù)類型分類:線性最優(yōu)化問題,非線性最優(yōu)化問題,二次規(guī)劃,多目標(biāo)規(guī)劃,動(dòng)態(tài)規(guī)劃,整數(shù)規(guī)劃,0-1規(guī)劃.25§1.2最優(yōu)化問題的一般算法26迭代算法迭代算法

選取一個(gè)初始可行點(diǎn)x0∈D,由這個(gè)初始可行點(diǎn)出發(fā),依次產(chǎn)生一個(gè)可行點(diǎn)列:x1,x2,···,xk,···,記為{xk},使得某個(gè)xk恰好是問題的一個(gè)最優(yōu)解,或者該點(diǎn)列收斂到問題的一個(gè)最優(yōu)解x*.下降算法在迭代算法中一般要求

f(xk+1)≤f(xk).27可行點(diǎn)列的產(chǎn)生在xk處求得一個(gè)方向pk(下降方向),在射線xk+apk(a>0)上求一點(diǎn):xk+1=xk+akpk使得f(xk+1)≤f(xk).其中ak稱為步長(zhǎng).定義1.2.1(下降方向)在點(diǎn)xk處,對(duì)于方向pk≠0,若存在實(shí)數(shù)b>0,使得任意的a∈(0,b),有:f(xk+apk)<f(xk),則稱pk為函數(shù)f(x)在點(diǎn)xk處的一個(gè)下降方向.28下降方向若f(x)具有連續(xù)的一階偏導(dǎo)數(shù),令由Taylor公式:當(dāng)gkTpk<0時(shí),f(xk+apk)<f(xk),所以pk是f(x)在xk處的一個(gè)下降方向.反之,當(dāng)pk是f(x)在xk處的一個(gè)下降方向時(shí),有g(shù)kTpk≤0(書中有錯(cuò)).通常稱滿足gkTpk<0的方向pk是為f(x)在xk處的一個(gè)下降方向.29可行方向定義1.2.2(可行方向)

已知區(qū)域,xk∈D,對(duì)于向量pk≠0,若存在實(shí)數(shù)b>0,使得對(duì)任意的a∈(0,b

),有:xk+apk∈D,則稱pk為點(diǎn)xk處關(guān)于區(qū)域D的可行方向.對(duì)于D的內(nèi)點(diǎn)(存在鄰域包含于D),任意方向可行,對(duì)于邊界點(diǎn)(任意鄰域既有D的點(diǎn)也有不在D中的點(diǎn)),則有些方向可行,有些方向不可行.若下降方向關(guān)于域D可行,則稱為可行下降方向.30最優(yōu)化問題的算法的一般迭代格式給定初始點(diǎn)x0,令k=0.(1)確定xk處的可行下降方向pk;(2)確定步長(zhǎng)ak,使得f(xk+akpk)<f(xk),(3)令xk+1=xk+akpk;(4)若xk+1滿足某種終止準(zhǔn)則,則停止迭代,以xk+1為近似最優(yōu)解;或者已經(jīng)達(dá)到最大迭代步數(shù),也可終止迭代.否則令k:=k+1,轉(zhuǎn)(1)31收斂性如果一個(gè)算法只有當(dāng)初始點(diǎn)x0充分接近x*時(shí),產(chǎn)生的點(diǎn)列才收斂于x*,則稱該算法為具有局部收斂的算法.如果對(duì)任意的x0∈D,由算法產(chǎn)生的點(diǎn)列都收斂x*,則稱該算法為具有全局收斂的算法.由于一般情況下最優(yōu)解x*是未知的,所以只有具有全局收斂性的算法才有實(shí)用意義.但算法的局部收斂性分析,在理論上是重要的,因?yàn)樗侨质諗啃苑治龅幕A(chǔ)。32收斂速度定義1.2.3

設(shè)序列{xk}收斂于x*,而且若0<b<1,則稱{xk}為線性收斂的,稱b為收斂比;定義1.2.4

設(shè)序列{xk}收斂于x*,而且若b=0,則稱{xk}為超線性收斂的.則稱{xk}為p階收斂.33終止準(zhǔn)則對(duì)于一種算法,應(yīng)該有某種終止準(zhǔn)則,當(dāng)某次迭代滿足終止準(zhǔn)則時(shí),就停止迭代.常用的終止準(zhǔn)則有:(1)或(2)或(3)(4)上面三種準(zhǔn)則的組合.注:其中e>0是預(yù)先給定的.34§1.3二維最優(yōu)化問題的幾何解釋35理論分析二維最優(yōu)化問題的目標(biāo)函數(shù)z=f(x1,x2)表示三維空間R3中的曲面.在空間直角坐標(biāo)系O-x1x2z中,平面z=c與曲面z=f(x1,x2)的交線在0-x1x2平面上的投影曲線為:取不同的c值得到不同的投影曲線,每一條投影曲線對(duì)應(yīng)一個(gè)c值,稱投影曲線為目標(biāo)函數(shù)的等值線或等高線.3637理論分析求目標(biāo)函數(shù)z=f(x1,x2)在可行域D上的極小點(diǎn),是在與可行域D有交集的等值線中找出具有最小值的等值線.也就是在可行域D上沿著f(x1,x2)的負(fù)梯度方向或某種下降方向上找取得最小值c的點(diǎn).38例1.3.1解首先畫出可行域D,目標(biāo)函數(shù)的等值線是以點(diǎn)(1,2)為圓心的一族圓.f(x1,x2)的梯度為39例1.3.1負(fù)梯度方向指向等值線圓心,所以等值線與可行域D的邊界相切的點(diǎn)x*=(1/2,3/2)T是此問題的最優(yōu)解,目標(biāo)函數(shù)的最優(yōu)值為1/2.40例1.3.2解首先畫出可行域D的圖形.D為凸多邊形ODEFGO.再以c為參數(shù)畫出目標(biāo)函數(shù)的等值線2x1+3x2=c.41例1.3.2目標(biāo)函數(shù)c的值由小到大逐漸增加,等值線沿著目標(biāo)函數(shù)的梯度方向平行移動(dòng).當(dāng)移動(dòng)到點(diǎn)E時(shí),再移動(dòng)就與可行域D不相交了,所以頂點(diǎn)E就是最優(yōu)點(diǎn),最優(yōu)值為14.42例1.3.3解如圖所示,可行域只能是圓弧ABE,其中點(diǎn)A和點(diǎn)E是等值線–x1–x2+1=0和圓x12+x22-9=0的交點(diǎn).注意到等值線是平行的拋物線,圖中畫出了幾條目標(biāo)函數(shù)的等值線.容易看出B點(diǎn)是最優(yōu)點(diǎn),所以最優(yōu)解是(0,-3)T,最優(yōu)值為-3.43§1.4一維搜索44問題描述已知xk,并且求出了xk處的可行下降方向pk,從xk出發(fā),沿方向pk求目標(biāo)函數(shù)的最優(yōu)解,即求解問題:設(shè)其最優(yōu)解為ak,于是得到一個(gè)新點(diǎn)xk+1=

xk+

akpk所以一維搜索是求解一元函數(shù)f(a)的最優(yōu)化問題(也叫一維最優(yōu)化問題).我們來求解45在[a,b]內(nèi)任取x1<x2,1.4.1Fibonacci法與黃金分割法

設(shè)f(x)在[a,b]上為下單峰函數(shù),即有唯一的極小點(diǎn)x*,在x*左邊f(xié)(x)嚴(yán)格下降,在x*右邊f(xié)(x)嚴(yán)格上升.若f(x1)≥f(x2),則x*∈[x1,b].若f(x1)<f(x2),則x*∈[a,x2]46Fibonacci方法如果只有一個(gè)試點(diǎn)x,我們無法將區(qū)間縮小.如果知道兩個(gè)試點(diǎn)x1<x2,根據(jù)f(x1),f(x2)的大小關(guān)系,可以得到縮小的區(qū)間[a,x2]或[x1,b].我們的目的是使max(x2-a,b-x1)盡量小.由于x2-a+b-x1=b-a+x2-x1>b-a,因此max(x2-a,b-x1)>(b-a)/2.我們盡量靠近[a,b]中點(diǎn)來取點(diǎn).一般取x1=(b-a)/2,x2=x1+0.1(b-a),或者x2=(b-a)/2,x1=x2-0.1(b-a).47Fibonacci法下面我們考慮任給一個(gè)f(x)的單峰區(qū)間[a,b],如果給定試點(diǎn)的個(gè)數(shù)n,如何使最后確定的包含最優(yōu)值的區(qū)間盡量的小.另一種思維方式為,按什么方式取點(diǎn),求n次函數(shù)值之后,可最多將多長(zhǎng)的原始區(qū)間長(zhǎng)度縮小為1.設(shè)Ln為試點(diǎn)個(gè)數(shù)為n,最終區(qū)間長(zhǎng)度為1時(shí),原始區(qū)間[a,b]的最大可能長(zhǎng)度。48Fibonacci法設(shè)最初兩個(gè)試點(diǎn)為x1和x2,若極小點(diǎn)在[a,x1]內(nèi),至多還有n–2個(gè)試點(diǎn),則x1-a≤Ln–2.若極小點(diǎn)在[x1,b]內(nèi),包括x2在內(nèi)可以有n–1個(gè)試點(diǎn),則b–x1≤Ln–1.因此,Ln≤Ln–1+Ln–2.如果我們采取合適的技巧,可以使得Ln=Ln–1+Ln–2.另外,顯然有L0=L1=1.49Fibonacci數(shù)列從而Ln滿足差分方程:此為Fibonacci數(shù)列,一般寫為:Fibonacci數(shù)列的前幾個(gè)數(shù)據(jù)為：50Fibonacci法若原始區(qū)間為[a,b],要求最終的區(qū)間長(zhǎng)度≤e,則Fn≥(b-a)/e,由此可確定n,區(qū)間縮短之后與之前的比依次為:n確定之后,最初兩個(gè)試點(diǎn)(關(guān)于[a,b]對(duì)稱)分別為:51Fibonacci法上述過程完成了一次迭代,新區(qū)間仍記為[a,b].若已經(jīng)進(jìn)行了i–1次迭代,第i次迭代時(shí),還有n–i+1個(gè)試點(diǎn)(包括已計(jì)算過的一個(gè)函數(shù)值).注:(1)最后的兩個(gè)試點(diǎn)取的方式:x1=(b-a)/2,x2=x1+0.1(b-a).(2)若f(x1)與f(x2)近似相等,則認(rèn)為x*在[x1,x2]內(nèi).52例1.4.1(Fibonacci方法)用Fibonacci法求函數(shù)f(x)=x2-x+2在區(qū)間[-1,3]上的極小點(diǎn).要求最終區(qū)間長(zhǎng)度不大于原始區(qū)間長(zhǎng)度的0.08倍。由Fn≥1/0.08=12.5,可知n應(yīng)取6(F6=13).解函數(shù)f(x)在區(qū)間[-1,3]上為下單峰函數(shù),53第一次迭代(a=–1,b=3)f1<f2,縮短后區(qū)間為[-1,1.462]x1=0.538x2=1.46255354x1=-0.077第二次迭代(a=–1,b=1.462)332新區(qū)間為[-0.077,1.462]55第三次迭代

(a=-0.077,b=1.462)新區(qū)間為新區(qū)間為第四次迭代(a=-0.077,b=0.846)56第五次迭代(a=0.231,b=0.846)取最優(yōu)解57Fibonacci方法評(píng)價(jià)Fibonacci方法的優(yōu)點(diǎn)(1)如果縮小的區(qū)間包含原來的試點(diǎn),則該試點(diǎn)在下一步被利用(2)效率最高,有限個(gè)試點(diǎn)的情況下,將最優(yōu)點(diǎn)所在的區(qū)間縮小到最小.Fibonacci方法的缺點(diǎn)(1)搜索前先要計(jì)算搜索的步數(shù)(2)每次搜索試點(diǎn)計(jì)算的公式不一致58黃金分割法我們希望保留Fibonacci方法的優(yōu)點(diǎn)(效率最高是不可能保留的),改進(jìn)其缺點(diǎn).若第一次選取的試點(diǎn)為x1<x2,則下一步保留的區(qū)間為[a,x2]或[x1,b],兩者的機(jī)會(huì)是均等的.因此我們選取試點(diǎn)時(shí)希望x2-a=b-x1.abx1x2設(shè)x1=a+p(b-a),則x2=a+(1-p)(b-a).59黃金分割法另外,我們希望如果縮小的區(qū)間包含原來的試點(diǎn),則該試點(diǎn)在下一步被利用.若保留的區(qū)間為[a,x2],前一次的試點(diǎn)x1在這個(gè)區(qū)間內(nèi).abx1x2abx260黃金分割法abx1x2a’b’x2’我們希望原來的x1,在縮小的區(qū)間內(nèi)成為新的“x2”.我們根據(jù)這一條件來計(jì)算p.計(jì)算x2的公式為x2=a+(1–p)(b–a).因此我們希望a+p(b–a)=a+(1–p)(a+(1–p)(b–a)–a)x’2=a’

+(1–p)(b’

–a’).即p2-3p+1=0化簡(jiǎn)得61黃金分割法若保留區(qū)間為[x1,b],我們得到的結(jié)果是一致的.該方法稱為黃金分割法,實(shí)際計(jì)算取近似值:x1=a+0.382(b–a),x2=a+0.618(b–a),所以黃金分割法又稱為0.618法.黃金分割法每次縮小區(qū)間的比例是一致的,每次將區(qū)間長(zhǎng)度縮小到原來的0.618倍.62算法1.4.2黃金分割法給定a,b(a<b)以及e>0,step1令x2=a+0.618(b-a),f2=f(x2);step2令x1=a+0.382(b-a),f1=f(x1);step3若|b–a|<e,則x*=(a+b)/2,Stop.step4若f1<f2,則b=x2,x2=x1,f2=f1,轉(zhuǎn)step2;

若f1=f2,則a=x1,b=x2,轉(zhuǎn)step1;

若f1>f2,則a=x2,x1=x2,f1=f2,轉(zhuǎn)step5;step5令x2=a+0.618(b–a)，f2=f(x2),轉(zhuǎn)step3.63用0.618法求解例1.4.1的數(shù)據(jù)表迭代次數(shù)[a,b]x1x2f1f2|b-a|<e0[-1,3]0.5281.4721.7512.695否1[-1,1.472]-0.0560.5282.0591.751否2[-0.056,1.472]0.5280.8881.7511.901否3[-0.056,0.888]0.3050.5281.7881.751否4[0.305,0.888]0.5280.6651.7511.777否5[0.305,0.665]0.4430.5281.7531.751否6[0.443,0.665]0.5280.5801.7511.757是

最優(yōu)解x*=(0.443+0.665)/2=0.554640.618法和Fibonacci之間的關(guān)系0.618法為Fibonacci法的極限形式.650.618法和Fibonacci之間的關(guān)系迭代步數(shù)的比較0.618法:Fibonacci方法:忽略得到黃金分割法至多比Fibonacci法多一步66進(jìn)退法(尋找下單峰區(qū)間)在一維搜索之前,必須先知道一個(gè)f(x)的下單峰區(qū)間.書中的算法1.4.3給出了求函數(shù)的一般的下單峰區(qū)間的算法.此處我們對(duì)算法1.4.3加以改進(jìn),求出f(x)的一個(gè)形如[0,b]形式的下單峰區(qū)間因?yàn)槲覀冴P(guān)心的問題是:我們的目的是找出兩個(gè)點(diǎn)x1<x2,使得f(x1)≤f(x2),f(x1)≤f(0).67進(jìn)退法(尋找下單峰區(qū)間)給定初始點(diǎn)x0=0,初始步長(zhǎng)Dx>0,x1=x0+Dx.x0下面分兩種情況討論.(1)f(x1)≤f(x0)x1對(duì)應(yīng)著圖上用紅線標(biāo)出的一部分68進(jìn)退法(尋找下單峰區(qū)間)x0(1)f(x1)≤f(x0)此時(shí)x1取值小,我們加大步長(zhǎng)向右搜索,取Dx=2Dx,x2=x1+Dx若f(x1)≤f(x2),則我們要找的區(qū)間即為[x0,x2]x1x2Dx2Dx69進(jìn)退法(尋找下單峰區(qū)間)x0(1)f(x1)≤f(x0)若f(x1)>f(x2),則我們所取的步長(zhǎng)偏小.令x1=x2,Dx=2Dx,x2=x1+Dx繼續(xù)往下判斷,直到滿足f(x1)≤f(x2).x1x2Dx2Dxx1x270進(jìn)退法(尋找下單峰區(qū)間)x0(2)f(x1)>f(x0)此時(shí)x1取值大,我們縮小步長(zhǎng)向x1左邊搜索,取Dx=Dx/2,x2=x1,

x1=x2-Dx若f(x1)≤f(x0),則我們要找的區(qū)間即為[x0,x2]否則繼續(xù)縮小區(qū)間,直到滿足f(x1)≤f(x0).x1x2x1711.4.2二分法若f(x)的導(dǎo)數(shù)存在且容易計(jì)算,則線性搜索的速多可以得到提高,下面的二分法每次將區(qū)間縮小至原來的二分之一.設(shè)f(x)為下單峰函數(shù),若f(x)在[a,b]具有連續(xù)的一階導(dǎo)數(shù),且f’(a)<0,f’(b)>0取c=(a+b)/2,若f’(c)=0,則c為極小點(diǎn);若f’(c)>0,則以[a,c]代替[a,b]作為新區(qū)間;若f’(c)<0,則以[b,c]代替[a,b]作為新區(qū)間.721.4.3拋物線法在求一元函數(shù)的極小點(diǎn)問題上,我們可以利用若干點(diǎn)處的函數(shù)值來構(gòu)造一個(gè)多項(xiàng)式,用這個(gè)多項(xiàng)式的極小點(diǎn)作為原來函數(shù)極小點(diǎn)的近似值.拋物線法就是一個(gè)用二次函數(shù)來逼近f(x)的方法,這也是我們常說的二次插值法.設(shè)在已知的三點(diǎn)x1<x0<x2處對(duì)應(yīng)的函數(shù)值f(xi)=fi,且滿足：f1>f0,f0<f2過三點(diǎn)(x1,f1),(x0,f0),(x2,f2)作二次函數(shù)y=j(x),即作一條拋物線,則可推導(dǎo)出：73為求j(x)的極小點(diǎn),令j’(x)=0,得:74若充分接近,即對(duì)于預(yù)先給定的精度,有,則把作為近似極小點(diǎn).否則計(jì)算,找出和之間的大者,去掉或,使新的三點(diǎn)仍具有兩端點(diǎn)的函數(shù)值大于中間點(diǎn)的函數(shù)值的性質(zhì).利用新的點(diǎn)再構(gòu)造二次函數(shù),繼續(xù)進(jìn)行迭代.751.4.4不精確的一維搜索前面介紹的得幾種一維搜索方法,都是為了獲得一元函數(shù)f(x)的最優(yōu)解,所以習(xí)慣上稱為精確一維搜索.在解非線性規(guī)劃問題中,一維搜索一般很難得到真正的精確值.因此,不精確的一維搜索開始為人們所重視.即在xk點(diǎn)確定了下降方向pk后,只計(jì)算少量的幾個(gè)函數(shù)就可得到一個(gè)滿足f(xk+1)<f(xk)的近似點(diǎn)xk+1.76不精確的一維搜索對(duì)于不精確的一維搜索,要求產(chǎn)生的點(diǎn)列具有某種收斂性.所以除了對(duì)下降方向pk有要求之外,對(duì)步長(zhǎng)ak也有要求,即要求目標(biāo)函數(shù)要“充分的下降”.下面令f(a)=f(xk+apk),我們討論ak滿足的條件.77不精確一維搜索對(duì)于一元函數(shù)f(a),精確一維搜索的條件為f’(ak)=0.不精確一維搜索的條件f’(ak)≈0,或|f’(ak)|≤s.實(shí)際計(jì)算中上式不好控制,一般的方法是|f’(ak)/f’(0)|≤s.s的選取：不宜太大——否則下降不夠充分；不宜太小——否則“太精確”.適合的范圍：比1稍小一些.78不精確一維搜索例：函數(shù)f(a)=(a-1)2.f’(a)=2(a-1),f’(0)=-2.取s=0.5,則控制條件為|f’(ak)|≤s|f’(0)|=1,即|2(ak-1)|≤1,1/2≤ak≤3/2.79不精確一維搜索上述條件是不夠的,甚至不能保證f(ak)<f(0).例如：對(duì)于一分段函數(shù)

a≤3/2時(shí),f(a)=(a-1)2;

a>3/2時(shí),f(a)=a-5/4.易見f(a)是一個(gè)連續(xù)可導(dǎo)函數(shù),且a>3/2時(shí)導(dǎo)數(shù)為1.|f’(ak)|≤s|f’(0)|=1確定的范圍是1/2≤ak,不能保證函數(shù)值下降.80不精確一維搜索為此,我們?cè)谥本€y=0以及函數(shù)f(a)在a=0處的切線之間畫一條直線,將搜索范圍首先限制在這條直線下方.81不精確一維搜索上述直線的方程為y-f(0)=mf’(0)a.因此搜索的條件為f(ak)-f(0)≤mf’(0)ak

.作業(yè)：對(duì)f(a)=f(xk+apk),證明82不精確一維搜索|f’(ak)/f’(0)|≤sf(ak)-f(0)≤mf’(0)a83不精確一維搜索的Wolfe原則設(shè)f(x)可微,取m∈(0,1/2),s∈(m,1),選取ak>0,使或用