最優(yōu)化方法課件

最優(yōu)化方法南京郵電大學(xué)理學(xué)院前言一、什么是最優(yōu)化最優(yōu)化是一門應(yīng)用性相當(dāng)廣泛的學(xué)科，它討論決策問題的最佳選擇之特性，尋找最佳的計(jì)算方法，研究這些計(jì)算方法的理論性質(zhì)及其實(shí)際計(jì)算表現(xiàn)。應(yīng)用范圍：信息工程及設(shè)計(jì)、經(jīng)濟(jì)規(guī)劃、生產(chǎn)管理、交通運(yùn)輸、國防工業(yè)以及科學(xué)研究等諸多領(lǐng)域。2二、包含的內(nèi)容按照優(yōu)化思想分為經(jīng)典方法與現(xiàn)代方法。經(jīng)典方法主要包括：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃等現(xiàn)代方法主要包括：隨機(jī)規(guī)劃、模糊規(guī)劃、模擬退火算法、遺傳算法、禁忌搜索和人工神經(jīng)網(wǎng)絡(luò)等。我們學(xué)習(xí)的內(nèi)容主要是經(jīng)典的最優(yōu)化方法。內(nèi)容包括線性規(guī)劃及其對偶規(guī)劃，無約束最優(yōu)化方法、約束最優(yōu)化方法等主要內(nèi)容。3三、學(xué)習(xí)方法1、認(rèn)真聽講，課后及時(shí)復(fù)習(xí)鞏固，并主動完成課后習(xí)題。2、多看參考書，通過不同學(xué)者的講述，全方位理解最優(yōu)化方法的思想方法和應(yīng)用，特別是計(jì)算方法。3、學(xué)以致用，通過最優(yōu)化方法的學(xué)習(xí)，培養(yǎng)研究生數(shù)學(xué)建模的能力和解決實(shí)際問題的能力。大家可以嘗試對于一些實(shí)際問題，先建立數(shù)學(xué)模型，轉(zhuǎn)化為數(shù)學(xué)問題，通過一些算法解決。4四、主要參考書教材：解可新、韓健、林友聯(lián)：最優(yōu)化方法（修訂版），天津大學(xué)出版社，2004年8月。其它參考書：1.蔣金山，何春雄，潘少華：最優(yōu)化計(jì)算方法，廣州：華南理工大學(xué)出版社，2007年10月。2.謝政，李建平，湯澤瀅：非線性最優(yōu)化。長沙：國防科技大學(xué)出版社，2003年9月。3.李董輝等：數(shù)值最優(yōu)化。北京：科學(xué)出版社，2005年。4.謝政，李建平，陳摯：非線性最優(yōu)化理論與方法。北京：高等教育出版社，2010年1月。5最優(yōu)化應(yīng)用具有廣泛的實(shí)用性運(yùn)輸問題，車輛調(diào)度，員工安排，空運(yùn)控制等工程設(shè)計(jì)，結(jié)構(gòu)設(shè)計(jì)等資源分配，生產(chǎn)計(jì)劃等通信：光網(wǎng)絡(luò)、無線網(wǎng)絡(luò)，adhoc等.制造業(yè)：鋼鐵生產(chǎn)，車間調(diào)度等醫(yī)藥生產(chǎn)，化工處理等電子工程，集成電路VLSIetc.排版（TEX,Latex,etc.）6目錄第一章最優(yōu)化問題概述第二章線性規(guī)劃第三章無約束最優(yōu)化方法第四章約束最優(yōu)化方法7第一章

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

與基本概念9例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)最省.10A1由題意可畫出如下的運(yùn)輸費(fèi)用圖:B2AmB1A2Bk產(chǎn)量需求量設(shè)Ai→Bj的水泥量為xij,已知Ai→Bj單價(jià)為cij,單位為元,則總運(yùn)費(fèi)為:11數(shù)學(xué)模型:注:平衡條件作為已知條件并不出現(xiàn)在約束條件中.12例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ì)劃,才能既完成合同,又使該廠總收入最多?13假設(shè)產(chǎn)品Aj的計(jì)劃產(chǎn)量為xj.由題意可畫出如下的生產(chǎn)與消耗的關(guān)系圖:B1B2BmAnA2A1消耗14數(shù)學(xué)模型15例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完成bj16則總支出可表示為:數(shù)學(xué)模型:17例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è)簡單而近似的解析表式.18最小二乘法解這種問題常用的方法是最小二乘法,以一個(gè)簡單的函數(shù)序列j1(x),j2(x),···,jn(x)為基本函數(shù).一般選取1,x,x2,···,xn為基本函數(shù),即以作為近似表達(dá)式.19最小二乘法系數(shù)的選取要使得下面得平方和最小:因此,數(shù)據(jù)擬合問題得數(shù)學(xué)模型為其中xi,yi(i=1,2,…,m)及jj(x)(j=0,1,…,n)為已知.20最優(yōu)化問題最優(yōu)化問題的一般形式為:(1.1)(目標(biāo)函數(shù))(1.3)(不等式約束)(1.2)(等式約束)其中x是n維向量.在實(shí)際應(yīng)用中,可以將求最大值的目標(biāo)函數(shù)取相反數(shù)后統(tǒng)一成公式中求最小值的形式.我們總是討論P(yáng):21相關(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為閉集.22相關(guān)定義定義1.1.3(整體最優(yōu)解)

若x*∈D,對于一切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)解.23相關(guān)定義定義1.1.4(局部最優(yōu)解)

若x*∈D,存在x*的某鄰域Ne(x*),使得對于一切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)解.x*對應(yīng)的目標(biāo)函數(shù)值f(x*)稱為最優(yōu)值，記為f

*.24相關(guān)定義求解最優(yōu)化問題(P),就是求目標(biāo)函數(shù)f(x)在約束條件(1.2),(1.3)下的極小點(diǎn),實(shí)際上是求可行域D上的整體最優(yōu)解.但是,在一般情況下,整體最優(yōu)解是很難求出的,往往只能求出局部最優(yōu)解.在求解時(shí)需要范數(shù)的概念，以下給出定義。25向量范數(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||(對于任意a∈R);(3)||x+y||≤||x||+||y||(三角不等式);則稱||x||為Rn上的一個(gè)向量范數(shù).26常用的向量范數(shù)1-范數(shù)2-范數(shù)(歐氏范數(shù))∞-范數(shù)p-范數(shù)∞-范數(shù)是p-范數(shù)的極限27常用的向量范數(shù)對向量x=(1,-2,3)T,有||x||p是p的單調(diào)遞減函數(shù).28最優(yōu)化問題的分類根據(jù)數(shù)學(xué)模型中有無約束函數(shù)分為有約束的最優(yōu)化問題和無約束的最優(yōu)化問題.根據(jù)目標(biāo)函數(shù)和約束函數(shù)的函數(shù)類型分類:線性最優(yōu)化問題,非線性最優(yōu)化問題,二次規(guī)劃,多目標(biāo)規(guī)劃,動態(tài)規(guī)劃,整數(shù)規(guī)劃,0-1規(guī)劃.29§1.2最優(yōu)化問題的一般算法30迭代算法迭代算法

選取一個(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).31可行點(diǎn)列的產(chǎn)生在xk處求得一個(gè)方向pk(下降方向),在射線xk+apk(a>0)上求一點(diǎn):xk+1=xk+akpk使得f(xk+1)≤f(xk).其中ak稱為步長.定義1.2.1(下降方向)在點(diǎn)xk處,對于方向pk≠0,若存在實(shí)數(shù)b>0,使得任意的a∈(0,b),有:f(xk+apk)<f(xk),則稱pk為函數(shù)f(x)在點(diǎn)xk處的一個(gè)下降方向.32下降方向若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.通常稱滿足gkTpk<0的方向pk是為f(x)在xk處的一個(gè)下降方向.

稱為f(x)在x處的梯度。33可行方向定義1.2.2(可行方向)

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

),有:xk+apk∈D,則稱pk為點(diǎn)xk處關(guān)于區(qū)域D的可行方向.對于D的內(nèi)點(diǎn)(存在鄰域包含于D),任意方向可行,對于邊界點(diǎn)(任意鄰域既有D的點(diǎn)也有不在D中的點(diǎn)),則有些方向可行,有些方向不可行.若下降方向關(guān)于域D可行,則稱為可行下降方向.34最優(yōu)化問題的算法的一般迭代格式給定初始點(diǎn)x0,令k=0.(1)確定xk處的可行下降方向pk;(2)確定步長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)35收斂性如果一個(gè)算法只有當(dāng)初始點(diǎn)x0充分接近x*時(shí),產(chǎn)生的點(diǎn)列才收斂于x*,則稱該算法為具有局部收斂的算法.如果對任意的x0∈D,由算法產(chǎn)生的點(diǎn)列都收斂x*,則稱該算法為具有全局收斂的算法.由于一般情況下最優(yōu)解x*是未知的,所以只有具有全局收斂性的算法才有實(shí)用意義.但算法的局部收斂性分析,在理論上是重要的,因?yàn)樗侨质諗啃苑治龅幕A(chǔ)。36收斂速度定義1.2.3

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

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

+1=

xk

+

ak

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

設(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]50黃金分割法我們希望保留Fibonacci方法的優(yōu)點(diǎn)(效率最高是不可能保留的),改進(jìn)其缺點(diǎn).若第一次選取的試點(diǎn)為x1<x2,則下一步保留的區(qū)間為[a,x2]或[x1,b],兩者的機(jī)會是均等的.因此我們選取試點(diǎn)時(shí)希望x2-a=b-x1.abx1x2設(shè)x1=a+p(b-a),則x2=a+(1-p)(b-a).51黃金分割法另外,我們希望如果縮小的區(qū)間包含原來的試點(diǎn),則該試點(diǎn)在下一步被利用.若保留的區(qū)間為[a,x2],前一次的試點(diǎn)x1在這個(gè)區(qū)間內(nèi).abx1x2abx252黃金分割法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化簡得53黃金分割法若保留區(qū)間為[x1,b],我們得到的結(jié)果是一致的.該方法稱為黃金分割法,實(shí)際計(jì)算取近似值:x1=a+0.382(b–a),x2=a+0.618(b–a),所以黃金分割法又稱為0.618法.黃金分割法每次縮小區(qū)間的比例是一致的,每次將區(qū)間長度縮小到原來的0.618倍.54算法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.55例1.4.1

用黃金分割法求函數(shù)f(x)=x2-x+2在區(qū)間[-1,3]上的極小值，要求區(qū)間長度不大于原始區(qū)間長的0.08。56用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.554570.618法和Fibonacci之間的關(guān)系0.618法為Fibonacci法的極限形式.580.618法和Fibonacci之間的關(guān)系迭代步數(shù)的比較0.618法:Fibonacci方法:忽略得到黃金分割法至多比Fibonacci法多一步59進(jìn)退法(尋找下單峰區(qū)間)在一維搜索之前,必須先知道一個(gè)f(x)的下單峰區(qū)間.書中的算法1.4.3給出了求函數(shù)的一般的下單峰區(qū)間的算法.此處我們對算法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).60進(jìn)退法(尋找下單峰區(qū)間)給定初始點(diǎn)x0=0,初始步長Dx>0,x1=x0+Dx.x0下面分兩種情況討論.(1)f(x1)≤f(x0)x1對應(yīng)著圖上用紅線標(biāo)出的一部分61進(jìn)退法(尋找下單峰區(qū)間)x0(1)f(x1)≤f(x0)此時(shí)x1取值小,我們加大步長向右搜索,取Dx=2Dx,x2=x1+Dx若f(x1)≤f(x2),則我們要找的區(qū)間即為[x0,x2]x1x2Dx2Dx62進(jìn)退法(尋找下單峰區(qū)間)x0(1)f(x1)≤f(x0)若f(x1)>f(x2),則我們所取的步長偏小.令x1=x2,Dx=2Dx,x2=x1+Dx繼續(xù)往下判斷,直到滿足f(x1)≤f(x2).x1x2Dx2Dxx1x263進(jìn)退法(尋找下單峰區(qū)間)x0(2)f(x1)>f(x0)此時(shí)x1取值大,我們縮小步長向x1左邊搜索,取Dx=Dx/2,x2=x1,

x1=x2-Dx若f(x1)≤f(x0),則我們要找的區(qū)間即為[x0,x2]否則繼續(xù)縮小區(qū)間,直到滿足f(x1)≤f(x0).x1x2x1641.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,則以[c,b]代替[a,b]作為新區(qū)間.651.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處對應(yīng)的函數(shù)值f(xi)=fi,且滿足：f1>f0,f0<f2過三點(diǎn)(x1,f1),(x0,f0),(x2,f2)作二次函數(shù)y=j(x),即作一條拋物線,則可推導(dǎo)出：66為求j(x)的極小點(diǎn),令j’(x)=0,得:67若充分接近,即對于預(yù)先給定的精度,有,則把作為近似極小點(diǎn).否則計(jì)算,找出和之間的大者,去掉或,使新的三點(diǎn)仍具有兩端點(diǎn)的函數(shù)值大于中間點(diǎn)的函數(shù)值的性質(zhì).利用新的點(diǎn)再構(gòu)造二次函數(shù),繼續(xù)進(jìn)行迭代.681.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.69四、不精確的一維搜索考慮從xk

點(diǎn)出發(fā)，沿方向pk

尋找新迭代點(diǎn)：要求:(1)

(2)

不能太小。最常用的不精確的一維搜索來確定步長的一個(gè)原則，稱為Wolfe

原則：設(shè)

f(x)可微，在

xk

取方向

pk,有(即

pk

為下降方向)

求使

其中為取定參數(shù)。實(shí)際中常取附近。70不精確一維搜索的Wolfe原則設(shè)f(x)可微,取m∈(0,1/2),s∈(m,1),選取ak>0,使或用下面更強(qiáng)的條件代替(1.7)式:71Wolfe原則關(guān)于滿足Wolfe原則的步長ak的存在性:定理1.4.2

設(shè)f(x)有下界且gkTpk<0.令m∈(0,1/2),s∈(m,1),則存在區(qū)間[c1,c2],使得任意的a∈[c1,c2]均滿足式(1.6)和(1.7)(也滿足(1.8)).72不精確