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

最優化問題概述§1.1最優化問題的數學模型

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

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

若x*∈D,對于一切x∈D恒有f(x*)≤f(x),則稱x*為最優化問題(P)的整體最優解.若x*∈D,x≠x*,恒有f(x*)<f(x),則稱x*為最優化問題(P)的嚴格整體最優解.23相關定義定義1.1.4(局部最優解)

若x*∈D,存在x*的某鄰域Ne(x*),使得對于一切x∈D∩Ne(x*),恒有f(x*)≤f(x),則稱為最優化問題(P)的局部最優解,其中Ne(x*)={x|||x-x*||<e,e>0}.當x≠x*時,若上面的不等式為嚴格不等式則稱x*為問題(P)的嚴格局部最優解.顯然,整體最優解一定是局部最優解,而局部最優解不一定是整體最優解.x*對應的目標函數值f(x*)稱為最優值，記為f

*.24相關定義求解最優化問題(P),就是求目標函數f(x)在約束條件(1.2),(1.3)下的極小點,實際上是求可行域D上的整體最優解.但是,在一般情況下,整體最優解是很難求出的,往往只能求出局部最優解.在求解時需要范數的概念，以下給出定義。25向量范數定義1.1.5

如果向量x∈Rn的某個實值函數||x||,滿足條件(1)||x||≥0(||x||=0當且僅當x=0)(正定性);(2)||ax||=|a|·||x||(對于任意a∈R);(3)||x+y||≤||x||+||y||(三角不等式);則稱||x||為Rn上的一個向量范數.26常用的向量范數1-范數2-范數(歐氏范數)∞-范數p-范數∞-范數是p-范數的極限27常用的向量范數對向量x=(1,-2,3)T,有||x||p是p的單調遞減函數.28最優化問題的分類根據數學模型中有無約束函數分為有約束的最優化問題和無約束的最優化問題.根據目標函數和約束函數的函數類型分類:線性最優化問題,非線性最優化問題,二次規劃,多目標規劃,動態規劃,整數規劃,0-1規劃.29§1.2最優化問題的一般算法30迭代算法迭代算法

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

f(xk+1)≤f(xk).31可行點列的產生在xk處求得一個方向pk(下降方向),在射線xk+apk(a>0)上求一點:xk+1=xk+akpk使得f(xk+1)≤f(xk).其中ak稱為步長.定義1.2.1(下降方向)在點xk處,對于方向pk≠0,若存在實數b>0,使得任意的a∈(0,b),有:f(xk+apk)<f(xk),則稱pk為函數f(x)在點xk處的一個下降方向.32下降方向若f(x)具有連續的一階偏導數,令由Taylor公式:當gkTpk<0時,f(xk+apk)<f(xk),所以pk是f(x)在xk處的一個下降方向.反之,當pk是f(x)在xk處的一個下降方向時,有gkTpk≤0.通常稱滿足gkTpk<0的方向pk是為f(x)在xk處的一個下降方向.

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

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

),有:xk+apk∈D,則稱pk為點xk處關于區域D的可行方向.對于D的內點(存在鄰域包含于D),任意方向可行,對于邊界點(任意鄰域既有D的點也有不在D中的點),則有些方向可行,有些方向不可行.若下降方向關于域D可行,則稱為可行下降方向.34最優化問題的算法的一般迭代格式給定初始點x0,令k=0.(1)確定xk處的可行下降方向pk;(2)確定步長ak,使得f(xk+akpk)<f(xk),(3)令xk+1=xk+akpk;(4)若xk+1滿足某種終止準則,則停止迭代,以xk+1為近似最優解;或者已經達到最大迭代步數,也可終止迭代.否則令k:=k+1,轉(1)35收斂性如果一個算法只有當初始點x0充分接近x*時,產生的點列才收斂于x*,則稱該算法為具有局部收斂的算法.如果對任意的x0∈D,由算法產生的點列都收斂x*,則稱該算法為具有全局收斂的算法.由于一般情況下最優解x*是未知的,所以只有具有全局收斂性的算法才有實用意義.但算法的局部收斂性分析,在理論上是重要的,因為它是全局收斂性分析的基礎。36收斂速度定義1.2.3

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

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

+1=

xk

+

ak

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

設f(x)在[a,b]上為下單峰函數,即有唯一的極小點x*,在x*左邊f(x)嚴格下降,在x*右邊f(x)嚴格上升.若f(x1)≥f(x2),則x*∈[x1,b].若f(x1)<f(x2),則x*∈[a,x2]50黃金分割法我們希望保留Fibonacci方法的優點(效率最高是不可能保留的),改進其缺點.若第一次選取的試點為x1<x2,則下一步保留的區間為[a,x2]或[x1,b],兩者的機會是均等的.因此我們選取試點時希望x2-a=b-x1.abx1x2設x1=a+p(b-a),則x2=a+(1-p)(b-a).51黃金分割法另外,我們希望如果縮小的區間包含原來的試點,則該試點在下一步被利用.若保留的區間為[a,x2],前一次的試點x1在這個區間內.abx1x2abx252黃金分割法abx1x2a’b’x2’我們希望原來的x1,在縮小的區間內成為新的“x2”.我們根據這一條件來計算p.計算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黃金分割法若保留區間為[x1,b],我們得到的結果是一致的.該方法稱為黃金分割法,實際計算取近似值:x1=a+0.382(b–a),x2=a+0.618(b–a),所以黃金分割法又稱為0.618法.黃金分割法每次縮小區間的比例是一致的,每次將區間長度縮小到原來的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,轉step2;

若f1=f2,則a=x1,b=x2,轉step1;

若f1>f2,則a=x2,x1=x2,f1=f2,轉step5;step5令x2=a+0.618(b–a)，f2=f(x2),轉step3.55例1.4.1

用黃金分割法求函數f(x)=x2-x+2在區間[-1,3]上的極小值，要求區間長度不大于原始區間長的0.08。56用0.618法求解例1.4.1的數據表迭代次數[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是

最優解x*=(0.443+0.665)/2=0.554570.618法和Fibonacci之間的關系0.618法為Fibonacci法的極限形式.580.618法和Fibonacci之間的關系迭代步數的比較0.618法:Fibonacci方法:忽略得到黃金分割法至多比Fibonacci法多一步59進退法(尋找下單峰區間)在一維搜索之前,必須先知道一個f(x)的下單峰區間.書中的算法1.4.3給出了求函數的一般的下單峰區間的算法.此處我們對算法1.4.3加以改進,求出f(x)的一個形如[0,b]形式的下單峰區間因為我們關心的問題是:我們的目的是找出兩個點x1<x2,使得f(x1)≤f(x2),f(x1)≤f(0).60進退法(尋找下單峰區間)給定初始點x0=0,初始步長Dx>0,x1=x0+Dx.x0下面分兩種情況討論.(1)f(x1)≤f(x0)x1對應著圖上用紅線標出的一部分61進退法(尋找下單峰區間)x0(1)f(x1)≤f(x0)此時x1取值小,我們加大步長向右搜索,取Dx=2Dx,x2=x1+Dx若f(x1)≤f(x2),則我們要找的區間即為[x0,x2]x1x2Dx2Dx62進退法(尋找下單峰區間)x0(1)f(x1)≤f(x0)若f(x1)>f(x2),則我們所取的步長偏小.令x1=x2,Dx=2Dx,x2=x1+Dx繼續往下判斷,直到滿足f(x1)≤f(x2).x1x2Dx2Dxx1x263進退法(尋找下單峰區間)x0(2)f(x1)>f(x0)此時x1取值大,我們縮小步長向x1左邊搜索,取Dx=Dx/2,x2=x1,

x1=x2-Dx若f(x1)≤f(x0),則我們要找的區間即為[x0,x2]否則繼續縮小區間,直到滿足f(x1)≤f(x0).x1x2x1641.4.2二分法若f(x)的導數存在且容易計算,則線性搜索的速度可以得到提高,下面的二分法每次將區間縮小至原來的二分之一.設f(x)為下單峰函數,若f(x)在[a,b]具有連續的一階導數,且f’(a)<0,f’(b)>0取c=(a+b)/2,若f’(c)=0,則c為極小點;若f’(c)>0,則以[a,c]代替[a,b]作為新區間;若f’(c)<0,則以[c,b]代替[a,b]作為新區間.651.4.3拋物線法在求一元函數的極小點問題上,我們可以利用若干點處的函數值來構造一個多項式,用這個多項式的極小點作為原來函數極小點的近似值.拋物線法就是一個用二次函數來逼近f(x)的方法,這也是我們常說的二次插值法.設在已知的三點x1<x0<x2處對應的函數值f(xi)=fi,且滿足：f1>f0,f0<f2過三點(x1,f1),(x0,f0),(x2,f2)作二次函數y=j(x),即作一條拋物線,則可推導出：66為求j(x)的極小點,令j’(x)=0,得:67若充分接近,即對于預先給定的精度,有,則把作為近似極小點.否則計算,找出和之間的大者,去掉或,使新的三點仍具有兩端點的函數值大于中間點的函數值的性質.利用新的點再構造二次函數,繼續進行迭代.681.4.4不精確的一維搜索前面介紹的得幾種一維搜索方法,都是為了獲得一元函數f(x)的最優解,所以習慣上稱為精確一維搜索.在解非線性規劃問題中,一維搜索一般很難得到真正的精確值.因此,不精確的一維搜索開始為人們所重視.即在xk點確定了下降方向pk后,只計算少量的幾個函數就可得到一個滿足f(xk+1)<f(xk)的近似點xk+1.69四、不精確的一維搜索考慮從xk

點出發，沿方向pk

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

(2)

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

原則：設

f(x)可微，在

xk

取方向

pk,有(即

pk

為下降方向)

求使

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

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