《建模仿真與優(yōu)化設(shè)計(jì).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《建模仿真與優(yōu)化設(shè)計(jì).ppt（138頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,建模仿真與優(yōu)化設(shè)計(jì) 第一部分 中北大學(xué) 張保成,掌握優(yōu)化問(wèn)題的數(shù)學(xué)描述方法； 2. 熟練掌握常用優(yōu)化算法。,一 優(yōu)化模型的一般意義 二 非線(xiàn)性規(guī)劃建模無(wú)約束最優(yōu)化 非線(xiàn)性規(guī)劃建模有約束非線(xiàn)性規(guī)劃 四 連續(xù)結(jié)構(gòu)體建模與優(yōu)化設(shè)計(jì),學(xué) 習(xí) 內(nèi) 容,目 的,（一）優(yōu)化模型的數(shù)學(xué)描述,一 優(yōu)化模型的一般意義,“受約束于”之意,（二）優(yōu)化模型的分類(lèi),1.根據(jù)是否存在約束條件 有約束問(wèn)題和無(wú)約束問(wèn)題。 2.根據(jù)設(shè)計(jì)變量的性質(zhì) 靜態(tài)問(wèn)題和動(dòng)態(tài)問(wèn)題。,3.根據(jù)目標(biāo)函數(shù)和約束條件表達(dá)式的性質(zhì) 線(xiàn)性規(guī)劃，非線(xiàn)性規(guī)劃，二次規(guī)劃，多目標(biāo)規(guī)劃等。,（1）非線(xiàn)性規(guī)劃 目標(biāo)函數(shù)和約束條件中，至少有一個(gè)非線(xiàn)性函數(shù)。,（2）線(xiàn)

2、性規(guī)劃（LP） 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量 的線(xiàn)性函數(shù)。,（3）二次規(guī)劃問(wèn)題 目標(biāo)函數(shù)為二次函數(shù)，約束條件為線(xiàn)性約束,5. 根據(jù)變量具有確定值還是隨機(jī)值 確定規(guī)劃和隨機(jī)規(guī)劃。,4. 根據(jù)設(shè)計(jì)變量的允許值,整數(shù)規(guī)劃（0-1規(guī)劃）和實(shí)數(shù)規(guī)劃。,（三）建立優(yōu)化模型的一般步驟,1.確定設(shè)計(jì)變量和目標(biāo)變量； 2.確定目標(biāo)函數(shù)的表達(dá)式； 3.尋找約束條件。,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),函數(shù)的梯度,泰勒展開(kāi),二階導(dǎo)數(shù)矩陣,矢量的概念、運(yùn)算和點(diǎn)積,矩陣的運(yùn)算和逆矩陣,（一）方向?qū)?shù),和 分別是 函數(shù) f( x1 , x2 )在x0點(diǎn)處沿坐標(biāo)軸x1和x2方向的變化率,故函數(shù) f( x1 , x2 )在x0

3、(x10 , x20)點(diǎn)處沿某一方向S的變化率為： 稱(chēng)為該函數(shù)沿此方向的方向?qū)?shù) 偏導(dǎo)數(shù)可以看作是函數(shù)沿坐標(biāo)軸 方向的方向?qū)?shù)，并有 （二）梯度 二元函數(shù)在點(diǎn)x0的梯度是由函數(shù)在該點(diǎn)的各一階偏導(dǎo)數(shù)組成的向量。即 :,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),設(shè)S方向單位向量 則有 函數(shù)的梯度具有以下性質(zhì)： （1）函數(shù)在一點(diǎn)的梯度是一個(gè)向量。梯度的方向是該點(diǎn)函數(shù)值上升最快的方向，與梯度相反的方向是該點(diǎn)函數(shù)值下降的最快的方向，梯度的大小就是它的模長(zhǎng)。 （2）一點(diǎn)的梯度方向是與過(guò)該點(diǎn)的等值線(xiàn)或等值面的切線(xiàn)或切平面相垂直的方向，或者說(shuō)是該點(diǎn)等值線(xiàn)或等值面的法線(xiàn)方向。 （3）梯度是函數(shù)在一點(diǎn)鄰域內(nèi)局部形態(tài)的描述。在一點(diǎn)上

4、升得快的方向，離開(kāi)該領(lǐng)域后就不一定上升得快，甚至可能下降。,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),（三）泰勒展開(kāi) 為了便于數(shù)學(xué)問(wèn)題的分析和求解，往往需要將一個(gè)復(fù)雜的非線(xiàn)性函數(shù)簡(jiǎn)化成線(xiàn)性函數(shù)或二次函數(shù)。簡(jiǎn)化的方法可以采用泰勒展開(kāi)式。 由高等數(shù)學(xué)可知，一元函數(shù) f(x)若在點(diǎn)x0的鄰域內(nèi)n階可導(dǎo)，則函數(shù)可在該點(diǎn)鄰域內(nèi)作泰勒展開(kāi)： 二元函數(shù) f(x)在點(diǎn)x0(x10 , x20)也可以作泰勒展開(kāi)，展開(kāi)式一般取前三項(xiàng)，即：,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),將上式寫(xiě)為矩陣形式 其中，G(x0)稱(chēng)為函數(shù) f( x1 , x2 )在點(diǎn)x0處的二階導(dǎo)數(shù)矩陣或海賽矩陣。,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),在優(yōu)化計(jì)算中，當(dāng)某點(diǎn)附近的函數(shù)值采用泰

5、勒展開(kāi)式作近似表達(dá)時(shí)，研究該點(diǎn)鄰域的極值問(wèn)題需要分析二次型函數(shù)是否正定。當(dāng)對(duì)任何非零向量x使 則二次型函數(shù)正定，G為正定矩陣,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),（四）二次函數(shù) 當(dāng)將函數(shù)的泰勒展開(kāi)式取到二次項(xiàng)時(shí)得到二次函數(shù)形式。優(yōu)化計(jì)算經(jīng)常把目標(biāo)函數(shù)表示為二次函數(shù)以使問(wèn)題分析得以簡(jiǎn)化。在線(xiàn)性代數(shù)中將二次齊次函數(shù)稱(chēng)作二次型，其矩陣形式 在優(yōu)化計(jì)算中，當(dāng)某點(diǎn)附近的函數(shù)值采用泰勒展開(kāi)式作近似表達(dá)時(shí)，研究該點(diǎn)鄰域的極值問(wèn)題需要分析二次型函數(shù)是否正定。當(dāng)對(duì)任何非零向量x使 則二次型函數(shù)正定，G為正定矩陣,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),對(duì)于一般二次函數(shù) 矩陣有正定和負(fù)定之分。對(duì)于所有非零向量： （1）若有 ，則稱(chēng)矩陣是正定

6、的； （2）若有 ，則稱(chēng)矩陣是半正定的； （3）若有 ，則稱(chēng)矩陣是負(fù)定的； （4）若有 ，則稱(chēng)矩陣是半負(fù)定的； （5）若有 ，則稱(chēng)矩陣是不定的,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),可以證明，正定二次函數(shù)具有以下性質(zhì)： （1）正定二次函數(shù)的等值線(xiàn)或等值面是一簇同心圓或同心橢球。橢圓簇或橢球簇的中心就是該二次函數(shù)的極小點(diǎn)。 （2）非正定二次函數(shù)在極小點(diǎn)附近的等值線(xiàn)或等值面近似于橢圓或橢球。,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),（五）無(wú)約束優(yōu)化問(wèn)題的極值條件 二次函數(shù) f(x1 , x2)在x0取得極值的必要條件為 充分條件為：該點(diǎn)處海賽矩陣正定，即,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),正定：各階主子式均大于零。,現(xiàn)代設(shè)計(jì)方法概論課程

7、教案,（六） 下降迭代算法及其收斂性,無(wú)約束最優(yōu)化問(wèn)題求優(yōu)過(guò)程的求解方法大致分為兩類(lèi)。 （1）解析法,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),現(xiàn)代設(shè)計(jì)方法概論課程教案,（2）數(shù)值迭代計(jì)算,（六） 下降迭代算法及其收斂性,二、優(yōu)化求解的數(shù)學(xué)基礎(chǔ),三、優(yōu)化設(shè)計(jì)的迭代計(jì)算,（一）優(yōu)化問(wèn)題的求解方法,1、優(yōu)化問(wèn)題的本質(zhì),優(yōu)化問(wèn)題的本質(zhì)求極值的數(shù)學(xué)問(wèn)題。,2、優(yōu)化問(wèn)題的求解方法,理論上,解析法,數(shù)值計(jì)算法,能求解嗎？,由于實(shí)際優(yōu)化數(shù)學(xué)模型的目標(biāo)函數(shù)及約束函數(shù)往往是非線(xiàn)性的,解析法求解非常困難，甚至無(wú)法實(shí)現(xiàn),（二）數(shù)值計(jì)算法的迭代方法,1、數(shù)值計(jì)算法的數(shù)學(xué)基礎(chǔ),計(jì)算方法,2、數(shù)值計(jì)算法的迭代方法,數(shù)值計(jì)算法可以較好地解決

8、這類(lèi)問(wèn)題,三、優(yōu)化設(shè)計(jì)的迭代計(jì)算,從目標(biāo)函數(shù)出發(fā),構(gòu)造一種使目標(biāo)函數(shù)值逐次下降的數(shù)值計(jì)算方法,利用計(jì)算機(jī)進(jìn)行反復(fù)迭代運(yùn)算,一步步搜索、調(diào)優(yōu)逐步逼近函數(shù)極值點(diǎn)或最優(yōu)點(diǎn),直到滿(mǎn)足一定的精度時(shí)終止迭代計(jì)算,最后所逼近的設(shè)計(jì)點(diǎn)即最優(yōu)點(diǎn)，所得到的解即一定精度下的近似解,三、優(yōu)化設(shè)計(jì)的迭代計(jì)算,（三）迭代計(jì)算的迭代過(guò)程,由選定的初始點(diǎn)x(0)出發(fā),使?jié)M足,由于各設(shè)計(jì)點(diǎn)的函數(shù)值依次下降，可見(jiàn)迭代點(diǎn)不斷向理論最優(yōu)點(diǎn)逼近，最后可得到一定精度下的近似最優(yōu)點(diǎn)，記作x*。,三、優(yōu)化設(shè)計(jì)的迭代計(jì)算,迭代過(guò)程圖示：,X(0),X(1),X(k),s(0),a(0),X(2),x*,三、優(yōu)化設(shè)計(jì)的迭代計(jì)算,（四）迭代計(jì)算的

9、終止準(zhǔn)則,由于數(shù)值迭代是逐步逼近最優(yōu)點(diǎn)而獲得近似解的，所以要考慮優(yōu)化問(wèn)題解的收斂性及迭代過(guò)程的終止條件。,1、迭代的收斂性,指某種迭代程序產(chǎn)生的序列xk (k=0,1,2,)收斂于,2、通常采用的終止準(zhǔn)則,（1）點(diǎn)距準(zhǔn)則,|xk+1-xk| 1,相鄰兩個(gè)設(shè)計(jì)點(diǎn)的距離已達(dá)到充分小,或,兩迭代點(diǎn)的坐標(biāo)分量之差,三、優(yōu)化設(shè)計(jì)的迭代計(jì)算,（2）函數(shù)下降量準(zhǔn)則,相鄰迭代點(diǎn)的函數(shù)值下降量達(dá)到充分小,或,相鄰迭代點(diǎn)的函數(shù)值的相對(duì)值達(dá)到充分小,（3）梯度準(zhǔn)則,無(wú)約束最優(yōu)化,非線(xiàn)性規(guī)劃建模,教學(xué)目的,教學(xué)內(nèi)容,2、掌握用數(shù)學(xué)軟件包求解無(wú)約束最優(yōu)化問(wèn)題。,1、了解無(wú)約束最優(yōu)化基本算法。,1.無(wú)約束優(yōu)化基本思想及基

10、本算法。,3. 用MATLAB求解無(wú)約束優(yōu)化問(wèn)題。,2. MATLAB優(yōu)化工具箱簡(jiǎn)介,無(wú)約束最優(yōu)化問(wèn)題,求解無(wú)約束最優(yōu)化問(wèn)題的的基本思想,*無(wú)約束最優(yōu)化問(wèn)題的基本算法,標(biāo)準(zhǔn)形式：,求解無(wú)約束最優(yōu)化問(wèn)題的基本思想,求解的基本思想 ( 以二元函數(shù)為例 ),5,3,1,連續(xù)可微,多局部極小,唯一極小 (全局極小),搜索過(guò)程,最優(yōu)點(diǎn) (1 1) 初始點(diǎn) (-1 1),-1,1,4.00,-0.79,0.58,3.39,-0.53,0.23,2.60,-0.18,0.00,1.50,0.09,-0.03,0.98,0.37,0.11,0.47,0.59,0.33,0.20,0.80,0.63,0.05,

11、0.95,0.90,0.003,0.99,0.99,1E-4,0.999,0.998,1E-5,0.9997,0.9998,1E-8,坐標(biāo)輪換法,一、坐標(biāo)輪換法的迭代過(guò)程 如圖，以二次函數(shù)為例。,x2,x0 x01,x02 x21,x11,x12,x1,x21,坐標(biāo)輪換法,任取一初始點(diǎn)x0作為第一輪的始點(diǎn)x01,先沿第一坐標(biāo)軸的方向e1作一維搜索，用一維優(yōu)化方法確定最優(yōu)步長(zhǎng)11，得第一輪的第一個(gè)迭代點(diǎn)x11=x01+ 11 e1，然后以x11為新起點(diǎn)，沿第二坐標(biāo)軸的方向e2作一維搜索，確定步長(zhǎng)21 ，得第一輪的第二個(gè)迭代點(diǎn)x21=x11+ 11 e2 第二輪迭代，需要 x11x01 x12 x

12、02+ 12 e1 x22=x12+ 22 e2 依次類(lèi)推，不斷迭代，目標(biāo)函數(shù)值不斷下降，最后逼近該目標(biāo)函數(shù)的最優(yōu)點(diǎn)。,坐標(biāo)輪換法,二、終止準(zhǔn)則 可以采用點(diǎn)距準(zhǔn)則或者其它準(zhǔn)則。 注意： 若采用點(diǎn)距準(zhǔn)則或函數(shù)值準(zhǔn)則，其中采用的點(diǎn)應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，而不是某搜索方向的前后迭代點(diǎn)。,坐標(biāo)輪換法,三、坐標(biāo)輪換法的流程圖,入口,給定：x0，,K=1,i=1,Xik=x0,沿ei方向一維搜索求i xik=xi-1k+ ikei x=xk f=f(x),i=n?,|xnk-x0k|?,x*=x f*=f(x*),出口,i=i+1,x0=x0k,k=k+1,N,Y,N,Y,坐標(biāo)輪換法,四、例題 五、小

13、結(jié) 坐標(biāo)輪換法程序簡(jiǎn)單，易于掌握。但是計(jì)算效率比較低，尤其是當(dāng)優(yōu)化問(wèn)題的維數(shù)較高時(shí)更為嚴(yán)重。一般把此種方法應(yīng)用于維數(shù)小于10的低維優(yōu)化問(wèn)題。 對(duì)于目標(biāo)函數(shù)存在 “脊線(xiàn)”的情況，在脊線(xiàn) 的尖點(diǎn)處沒(méi)有一個(gè)坐標(biāo)方 向可以使函數(shù)值下降，只 有在銳角所包含的范圍搜 索才可以達(dá)到函數(shù)值下降 的目的，故坐標(biāo)輪換法對(duì) 此類(lèi)函數(shù)會(huì)失效。,x2,x1,脊線(xiàn),鮑威爾方法方向加速法,鮑威爾方法是直接利用函數(shù)值來(lái)構(gòu)造共軛方向的一種共軛方向法。這種方法是在研究具有正定矩陣G的二次函數(shù) 的極小化問(wèn)題時(shí)形成的。其基本思想是在不用導(dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G的共軛方向。 一、共軛方向的概念 設(shè)G為一正定對(duì)稱(chēng)矩陣，若有一組非

14、零向量S1，S2， ，Sn滿(mǎn)足 SiTGSj=0 (i j )，則稱(chēng)這組向量關(guān)于矩陣G共軛。 共軛方向?qū)τ跇?gòu)造一種有效的算法是很重要的。以正定二元二次函數(shù)為例，我們進(jìn)行探討。,鮑威爾方法,正定的二元二次函數(shù)的等值線(xiàn)為一組橢圓，任選初始點(diǎn)x0沿某個(gè)下降方向S0作一維搜索，得x1 x1=x0+ 0S0此時(shí)，點(diǎn)x1的梯度必然與方向S0垂直，即有 f(x1)TS0=0S0與某一等值線(xiàn)相切于x1點(diǎn)。下一次的迭代，若選擇負(fù)梯度方向?yàn)樗阉鞣较颍瑢a(chǎn)生鋸齒現(xiàn)象。為避免鋸齒的產(chǎn)生，我們?nèi)〉较騍1直指極小點(diǎn)x*，如圖所示。,x0,x*,x1,1S1,- f(x1),S1,0S0,鮑威爾方法,若選定這樣的方向，

15、則對(duì)于二元二次函數(shù)只需進(jìn)行S0 和S1兩次搜索就可以求得極小點(diǎn)x*，即 x*=x1+ 1S1由于f(x1)=Gx1+b，當(dāng)x1 x*時(shí) 1S1 0，由于x*是f （x）的極小點(diǎn)，應(yīng)滿(mǎn)足極值必要條件，故f(x*)=Gx*+b=0，即 f(x*)=G（x1+ 1S1）+b= f(x1)+ 1GS1 =0 等式兩端同乘以(S0)T,得（S0）TGS1=0 ，故兩個(gè)向量S0、S1是G的共軛向量。 因此，若要使第二個(gè)迭代點(diǎn)成為正定二元二次函數(shù)的極小點(diǎn)，只要使兩次一維搜索的方向S0、S1關(guān)于函數(shù)的二階導(dǎo)數(shù)矩陣G共軛就可以了。,鮑威爾方法,二、共軛 方向的生成 設(shè)xk、xk+1為從不同點(diǎn)出發(fā)，沿同一方向Sj

16、 進(jìn)行一維搜索得到的兩個(gè)極小點(diǎn)，如圖所示。根據(jù)梯度和等值面的性質(zhì)， Sj 和xk、xk+1兩點(diǎn)處的梯度gk、gk+1之間存在如下關(guān)系 (Sj)Tgk=0 (Sj)Tgk+1=0又因?yàn)閤k、xk+1兩點(diǎn)處的梯度 可表示為 gk=Gxk+b gk+1=Gxk+1+b 兩式相減，得 gk+1-gk=G(xk+1-xK),鮑威爾方法,因此有 (Sj)T (gk+1-gk)= (Sj)T G(xk+1-xK)=0 若取方向Sk= xk+1-xK，則Sk和Sj對(duì)G共軛。這說(shuō)明只要沿方向Sj 分別對(duì)函數(shù)作兩次一維搜索，得到兩個(gè)極小點(diǎn)，則這兩點(diǎn)的連線(xiàn)方向就是與Sj 共軛的方向。,鮑威爾方法,三、鮑威爾基本算法

17、 如圖所示，以三維二次目標(biāo)函數(shù)的無(wú)約束優(yōu)化問(wèn)題為例。,x1,x3,x2,e1,e2,e3,e2,e3,e3,x01,x11,x21,x31,x1,x12,x22,x32,x13,x23,x33,x2,x3,S3,-S1,S2,S2,S1,鮑威爾方法,鮑威爾基本算法的步驟： 第一環(huán)基本方向組取單位坐標(biāo)矢量系e1、 e2、 e3 、 en，沿這些方向依次作一維搜索，然后將始末兩點(diǎn)相連作為新生方向，再沿新生方向作一維搜索，完成第一環(huán)的迭代。以后每環(huán)的基本方向組是將上環(huán)的第一個(gè)方向淘汰，上環(huán)的新生方向補(bǔ)入本環(huán)的最后而構(gòu)成。n維目標(biāo)函數(shù)完成n環(huán)的迭代過(guò)程稱(chēng)為一輪。從這一輪的終點(diǎn)出發(fā)沿新生方向搜索所得到的

18、極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成了算法的循環(huán)。,鮑威爾方法,鮑威爾基本算法的缺陷： 可能在某一環(huán)迭代中出現(xiàn)基本方向組為線(xiàn)性相關(guān)的矢量系的情況。如第k環(huán)中，產(chǎn)生新的方向： Sk=xnk-x0k=1kS1k+ 2kS2k + + nkSnk 式中， S1k、S2k 、 、 Snk為第k環(huán)基本方向組矢量， 1k 、 2k 、 、 nk為個(gè)方向的最優(yōu)步長(zhǎng)。 若在第k環(huán)的優(yōu)化搜索過(guò)程中出現(xiàn)1k =0，則方向Sk表示為S2k 、 S3k 、 、 Snk的線(xiàn)性組合，以后的各次搜索將在降維的空間進(jìn)行，無(wú)法得到n維空間的函數(shù)極小值，計(jì)算將失敗。,鮑威爾方法,鮑威爾基本算法的退化,如圖所示為一個(gè)三維優(yōu)化問(wèn)

19、題的示例，設(shè)第一環(huán)中1 =0 ，則新生方向與e2 、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。,鮑威爾方法,四、鮑威爾修正算法 在某環(huán)已經(jīng)取得的n+1各方向中，選取n個(gè)線(xiàn)性無(wú)關(guān)的并且共軛程度盡可能高的方向作為下一環(huán)的基本方向組。 鮑威爾修正算法的搜索方向的構(gòu)造： 在第k環(huán)的搜索中， x0k 為初始點(diǎn)，搜索方向?yàn)镾1k、S2k 、 、 Snk，產(chǎn)生的新方向?yàn)镾k ，此方向的極小點(diǎn)為xk。點(diǎn) xn+1k=2xnk-x0k ， 為x0k對(duì)xnk的映射點(diǎn)。 計(jì)算x0k 、 x1k 、 、 xnk 、 xk、 x n+1k 各點(diǎn)的函數(shù)值，記作： F1=F(x

20、0k) F2=F(xnk) F3=F(xn+1k) = F(xmk) -F(xm-1k) 是第k環(huán)方向組中，依次沿各方向搜索函數(shù)值下降最大值，即Smk方向函數(shù)下降最大。,鮑威爾方法,為了構(gòu)造第k+1環(huán)基本方向組，采用如下判別式： 按照一下兩種情況處理： 1、上式中至少一個(gè)不等式成立，則第k+1環(huán)的基本方向仍用老方向組S1k、S2k 、 、 Snk。 k+1的環(huán)初始點(diǎn)取 x0k+1=xnk F2F3 x0k+1=xn+1k F2F3 2、兩式均不成立，則淘汰函數(shù)值下降最大的方向，并用第k環(huán)的新生方向補(bǔ)入k+1環(huán)基本方向組的最后，即k+1環(huán)的方向組為S1k、S2k 、 、 Sm-1k、Sm+1k

21、、 Snk 、 Sn+1k 。k+1環(huán)的初始點(diǎn)取 x0k+1=xk xk是第k環(huán)沿Sn+1k方向搜索的極小點(diǎn)。,鮑威爾方法,x0k,x1k,x2k,x3k,xm-1k,xmk,Snk,xnk,Smk,S3k,S2k,Sk,xk,xn+1k,F1,F2,F3,鮑威爾方法,鮑威爾算法的終止條件： | xk-x0k | 五、鮑威爾算法的迭代步驟及流程圖 六、例題,梯度法,優(yōu)化設(shè)計(jì)是追求目標(biāo)函數(shù)值最小，因此，自然可以設(shè)想從某點(diǎn)出發(fā)，其搜索方向取該點(diǎn)的負(fù)梯度方向，使函數(shù)值在該點(diǎn)附近下降最快。這種方法也稱(chēng)為最速下降法。 一、基本原理梯度法的迭代公式為： x(k+1)=x(k)-(k)g(k)其中g(shù)(k)是

22、函數(shù)F(x)在迭代點(diǎn)x(k)處的梯度f(wàn)(xk) ， (k)一般采用一維搜索的最優(yōu)步長(zhǎng)，即 f(x(k+1)=f(x(k)-(k)g(k) =min f(x(k)-(k)g(k)=min()據(jù)一元函數(shù)極值條件和多元復(fù)合函數(shù)求導(dǎo)公式，得 ()= -( f(x(k)-(k)g(k)T g(k) =0即 （ f(x(k+1)T g(k) =0或 (g(k+1)Tg(k)=0,梯度法,此式表明，相鄰的兩個(gè)迭代點(diǎn)的梯度是彼此正交的。也即在梯度的迭代過(guò)程中，相鄰的搜索方向相互垂直。梯度法向極小點(diǎn)的逼近路徑是鋸齒形路線(xiàn)，越接近極小點(diǎn)，鋸齒越細(xì)，前進(jìn)速度越慢。 這是因?yàn)?，梯度是函?shù)的局部性質(zhì)，從局部上看，在該點(diǎn)

23、附近函數(shù)的下降最快，但從總體上看則走了許多彎路，因此函數(shù)值的下降并不快。,梯度法,二、迭代終止條件 采用梯度準(zhǔn)則： | g(k) | 三、迭代步驟（1）任選初始迭代點(diǎn)x(0)，選收斂精度 。（2）確定x(k)點(diǎn)的梯度（開(kāi)始k=0)（3）判斷是否滿(mǎn)足終止條件| g(k) | ？若滿(mǎn)足輸出最優(yōu)解，結(jié)束計(jì)算。否則轉(zhuǎn)下步。（4）從x(k)點(diǎn)出發(fā)，沿-g(k)方向作一維搜索求最優(yōu)步長(zhǎng)(k)。得下一迭代點(diǎn) x(k+1)=x(k)-(k)g(k) ，令k=k+1 返回步驟（2）。,梯度法,四、梯度法流程圖,入口,給定： x(0)，,k=0,|g(k)| ？,x*=x(k) f*=f(x(k),出口,x(k)

24、= x(0,計(jì)算：g(k),k=k+1,沿g(k)方向一維搜索， 求最優(yōu)步長(zhǎng)(k)。,N,Y,共軛梯度法,共軛梯度法是共軛方向法的一種，因?yàn)樵摲椒ㄖ忻恳粋€(gè)共軛向量都是依賴(lài)于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)的，所以稱(chēng)作共軛梯度法。 一、共軛梯度法的搜索方向 共軛梯度法的搜索方向采用梯度法基礎(chǔ)上的共軛方向，如圖所示，目標(biāo)函數(shù)F(x)在迭代點(diǎn)xk+1處的負(fù)梯度為- f(xk+1)，該方向與前一搜索方向Sk互為正交，在此基礎(chǔ)上構(gòu)造一種具有較高收斂速度的算法，該算法的搜索方向要滿(mǎn)足以下兩個(gè)條件： （1）以xk+1點(diǎn)出發(fā)的搜索方向 Sk+1是- f(xk+1)與Sk的線(xiàn)性組合。即,xk,x*,xk+1,- f(

25、xk+1),Sk+1,Sk,共軛梯度法,Sk+1 = - f(xk+1) + kSk （2）以Sk與Sk+1為基底的子空間中，矢量Sk與Sk+1相共軛，即滿(mǎn)足 Sk+1T G Sk = 0 二、 k的確定 確定方法不作要求。記住 三、 共軛梯度法的算法 （1）選初始點(diǎn)x0和收斂精度。 （2）令k=0，計(jì)算S0 = - f(x0) 。 （3）沿Sk方向進(jìn)行一維搜索求(k)，得 x(k+1)=x(k)+(k)S(k) （4）計(jì)算 f(xk+1) ，若| f(xk+1)| ，則終止迭代，取x*=xk+1；否則進(jìn)行下一步。,共軛梯度法,（5）檢查搜索次數(shù)，若k=n，則令x0=xk+1，轉(zhuǎn)（2）， 否則

26、，進(jìn)行下一步。 （6）構(gòu)造新的共軛方向 Sk+1 = - f(xk+1) + kSk 令k=k+1，轉(zhuǎn)（3）,共軛梯度法,四、共軛梯度法流程圖,入口,k=0，計(jì)算：- f(x0),| f(xk+1) | ？,出口,求(k) ，x(k+1)= x(k) +(k)S(k),計(jì)算： f(xk+1),x*=xk+1 f(x*)=f(xk+1),Y,N,給定： x(0)，,k n ？,x0=xk+1,N,Y,Sk+1 = - f(xk+1) + kSk,K=K+1,共軛梯度法,五、共軛梯度法的特點(diǎn) 共軛梯度法屬于解析法，其算法需求一階導(dǎo)數(shù)，所用公式及算法簡(jiǎn)單，所需存儲(chǔ)量少。該方法以正定二次函數(shù)的共軛方向

27、理論為基礎(chǔ)，對(duì)二次型函數(shù)可以經(jīng)過(guò)有限步達(dá)到極小點(diǎn)，所以具有二次收斂性。但是對(duì)于非二次型函數(shù)，以及在實(shí)際計(jì)算中由于計(jì)算機(jī)舍入誤差的影響，雖然經(jīng)過(guò)n次迭代，仍不能達(dá)到極小點(diǎn)，則通常以重置負(fù)梯度方向開(kāi)始，搜索直至達(dá)到預(yù)定精度，其收斂速度也是較快的。 六、例題,牛頓法,牛頓法是求無(wú)約束最優(yōu)解的一種古典解析算法。牛頓法可以分為原始牛頓法和阻尼牛頓法兩種。實(shí)際中應(yīng)用較多的是阻尼牛頓法。,原始牛頓法,一、原始牛頓法的基本思想 在第k次迭代的迭代點(diǎn)x(k)鄰域內(nèi)，用一個(gè)二次函數(shù)去近似代替原目標(biāo)函數(shù)f(x)，然后求出該二次函數(shù)的極小點(diǎn)作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)，依次類(lèi)推，通過(guò)多次重復(fù)迭代，是迭代點(diǎn)逐步逼

28、近原目標(biāo)函數(shù)的極小點(diǎn)。如圖所示。,F(x),1(x),0(x),x0,x1,x2,x*,原始牛頓法,二、原始牛頓法的迭代公式 設(shè)目標(biāo)函數(shù)f(x)具有連續(xù)的一、二階導(dǎo)數(shù)，在x(k)點(diǎn)鄰域內(nèi)取f(x)的二次泰勒多項(xiàng)式作近似式，即取逼近函數(shù)(x)為設(shè)xk+1為(x)極小點(diǎn)，根據(jù)極值的必要條件，應(yīng)有(xk+1)=0，即 f(xk)+ G(xk)x=0 又 x= xk+1 - xk 得 xk+1 = xk- G(xk)-1 f(xk) 即牛頓法迭代公式，方向- G(xk)-1 f(xk)稱(chēng)為牛頓方向,原始牛頓法,三、原始牛頓法的特點(diǎn) 若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是

29、完全相同的二次式，其等值線(xiàn)完全重合，故從任一點(diǎn)出發(fā)，一定可以一次達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。 因此，牛頓法是具有二次收斂性的算法。其優(yōu)點(diǎn)是：對(duì)于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對(duì)于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。 原始牛頓法的缺點(diǎn)是：由于迭代點(diǎn)的位置是按照極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，對(duì)于非二次函數(shù)，有時(shí)會(huì)使函數(shù)值上升，即 f(xk+1) f(xk)，而使計(jì)算失敗。,阻尼牛頓法,一、對(duì)原始牛頓法的改進(jìn) 為解決原始牛頓法的不足，加入搜索步長(zhǎng)(k)因此，迭代公式變?yōu)椋?xk+1 = xk - (k)G(xk)-1 f(xk) 這就

30、是阻尼牛頓法的迭代公式，最優(yōu)步長(zhǎng)(k)也稱(chēng)為阻尼因子，是沿牛頓方向一維搜索得到的最優(yōu)步長(zhǎng)。 二、阻尼牛頓法的迭代步驟 （1）給定初始點(diǎn)和收斂精度 （2）計(jì)算 f(xk) 、 G(xk)、 G(xk)-1 （3）求xk+1 = xk - (k)G(xk)-1 f(xk) （4）檢查收斂精度，若| xk+1- xk |則x*=xk+1，停止，否則 k=k+1，返回（2）繼續(xù),阻尼牛頓法,三、阻尼牛頓法的特點(diǎn) 優(yōu)點(diǎn)： 由于阻尼牛頓法每次迭代都在牛頓方向進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對(duì)初始點(diǎn)的選擇沒(méi)有苛刻的要求。 缺點(diǎn)： 1、對(duì)目標(biāo)函數(shù)要求苛刻，要求函數(shù)具

31、有連續(xù)的一、二階導(dǎo)數(shù)；為保證函數(shù)的穩(wěn)定下降，海賽矩陣必須正定；為求逆陣要求海賽矩陣非奇異。 2、計(jì)算復(fù)雜且計(jì)算量大，存儲(chǔ)量大,變尺度法,Matlab優(yōu)化工具箱簡(jiǎn)介,1.MATLAB求解優(yōu)化問(wèn)題的主要函數(shù),2. 優(yōu)化函數(shù)的輸入變量,使用優(yōu)化函數(shù)或優(yōu)化工具箱中其它優(yōu)化函數(shù)時(shí), 輸入變量見(jiàn)下表:,3. 優(yōu)化函數(shù)的輸出變量下表:,4控制參數(shù)options的設(shè)置,(3) MaxIter: 允許進(jìn)行迭代的最大次數(shù),取值為正整數(shù).,Options中常用的幾個(gè)參數(shù)的名稱(chēng)、含義、取值如下:,(1)Display: 顯示水平.取值為off時(shí),不顯示輸出; 取值為iter時(shí),顯示每次迭代的信息;取值為final時(shí),

32、顯示最終結(jié)果.默認(rèn)值為final.,(2)MaxFunEvals: 允許進(jìn)行函數(shù)評(píng)價(jià)的最大次數(shù),取值為正整數(shù).,例：opts=optimset(Display,iter,TolFun,1e-8) 該語(yǔ)句創(chuàng)建一個(gè)稱(chēng)為opts的優(yōu)化選項(xiàng)結(jié)構(gòu),其中顯示參數(shù)設(shè)為iter, TolFun參數(shù)設(shè)為1e-8.,控制參數(shù)options可以通過(guò)函數(shù)optimset創(chuàng)建或修改。命令的格式如下：,(1) options=optimset(optimfun) 創(chuàng)建一個(gè)含有所有參數(shù)名,并與優(yōu)化函數(shù)optimfun相關(guān)的默認(rèn)值的選項(xiàng)結(jié)構(gòu)options.,（2）options=optimset(param1,value1,

33、param2,value2,.) 創(chuàng)建一個(gè)名稱(chēng)為options的優(yōu)化選項(xiàng)參數(shù),其中指定的參數(shù)具有指定值,所有未指定的參數(shù)取默認(rèn)值.,(3)options=optimset(oldops,param1,value1,param2, value2,.) 創(chuàng)建名稱(chēng)為oldops的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應(yīng)的參數(shù).,用Matlab解無(wú)約束優(yōu)化問(wèn)題,其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。,常用格式如下： （1）x= fminbnd (fun,x1

34、,x2) （2）x= fminbnd (fun,x1,x2 ，options) （3）x，fval= fminbnd（.） （4）x，fval，exitflag= fminbnd（.） （5）x，fval，exitflag，output= fminbnd（.）,主程序?yàn)閣liti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語(yǔ)句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8),例2 對(duì)邊長(zhǎng)為3米的正方形鐵板，在四個(gè)角剪去相等的正方形以制成方形無(wú)蓋水

35、槽，問(wèn)如何剪法使水槽的容積最大？,解,先編寫(xiě)M文件fun0.m如下: function f=fun0(x) f=-(3-2*x).2*x;,主程序?yàn)閣liti2.m: x,fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval,運(yùn)算結(jié)果為: xmax = 0.5000,fmax =2.0000.即剪掉的正方形的邊長(zhǎng)為0.5米時(shí)水槽的容積最大,最大容積為2立方米.,命令格式為: （1）x= fminunc（fun,X0 ）；或x=fminsearch（fun,X0 ） （2）x= fminunc（fun,X0 ，options）； 或x=fminsearch（fu

36、n,X0 ，options） （3）x，fval= fminunc（.）； 或x，fval= fminsearch（.） （4）x，fval，exitflag= fminunc（.）； 或x，fval，exitflag= fminsearch （5）x，fval，exitflag，output= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.）,2、多元函數(shù)無(wú)約束優(yōu)化問(wèn)題,標(biāo)準(zhǔn)型為：min F(X),3 fminunc為中型優(yōu)化算法的步長(zhǎng)一維搜索提供了兩種算法， 由options中參數(shù)LineSearchType控制： LineSearchT

37、ype=quadcubic(缺省值)，混合的二次和三 次多項(xiàng)式插值； LineSearchType=cubicpoly，三次多項(xiàng)式插,使用fminunc和 fminsearch可能會(huì)得到局部最優(yōu)解.,說(shuō)明:,fminsearch是用單純形法尋優(yōu). fminunc的算法見(jiàn)以下幾點(diǎn)說(shuō)明：,1 fminunc為無(wú)約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由options中的參數(shù)LargeScale控制： LargeScale=on(默認(rèn)值),使用大型算法 LargeScale=off(默認(rèn)值),使用中型算法,2 fminunc為中型優(yōu)化算法的搜索方向提供了4種算法，由 options中的參數(shù)HessUp

38、date控制： HessUpdate=bfgs（默認(rèn)值），擬牛頓法的BFGS公式； HessUpdate=dfp，擬牛頓法的DFP公式； HessUpdate=steepdesc，最速下降法,例3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1),1、編寫(xiě)M-文件 fun1.m: function f = fun1 (x) f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); 2、輸入M文件wliti3.m如下: x0 = -1, 1; x=fminunc(fun1,x0); y=fun1(x),3、運(yùn)行結(jié)果:

39、 x= 0.5000 -1.0000 y = 1.3029e-10,3.用fminsearch函數(shù)求解,輸入命令: f=100*(x(2)-x(1)2)2+(1-x(1)2; x,fval,exitflag,output=fminsearch(f, -1.2 2),運(yùn)行結(jié)果: x =1.0000 1.0000 fval =1.9151e-010 exitflag = 1 output = iterations: 108 funcCount: 202 algorithm: Nelder-Mead simplex direct search,4. 用fminunc 函數(shù),(1)建立M-文件fun2

40、.m function f=fun2(x) f=100*(x(2)-x(1)2)2+(1-x(1)2,(2)主程序wliti44.m,Rosenbrock函數(shù)不同算法的計(jì)算結(jié)果,可以看出，最速下降法的結(jié)果最差.因?yàn)樽钏傧陆捣ㄌ貏e不適合于從一狹長(zhǎng)通道到達(dá)最優(yōu)解的情況.,例5 產(chǎn)銷(xiāo)量的最佳安排 某廠生產(chǎn)一種產(chǎn)品有甲、乙兩個(gè)牌號(hào)，討論在產(chǎn)銷(xiāo)平衡的情況下如何確定各自的產(chǎn)量，使總利潤(rùn)最大. 所謂產(chǎn)銷(xiāo)平衡指工廠的產(chǎn)量等于市場(chǎng)上的銷(xiāo)量.,基本假設(shè),1價(jià)格與銷(xiāo)量成線(xiàn)性關(guān)系,2成本與產(chǎn)量成負(fù)指數(shù)關(guān)系,模型建立,若根據(jù)大量的統(tǒng)計(jì)數(shù)據(jù),求出系數(shù)b1=100,a11=1,a12=0.1,b2=280, a21=0.2

41、,a22=2,r1=30,1=0.015,c1=20, r2=100,2=0.02,c2=30,則 問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題：求甲,乙兩個(gè)牌號(hào)的產(chǎn)量x1，x2，使 總利潤(rùn)z最大.,為簡(jiǎn)化模型,先忽略成本,并令a12=0,a21=0,問(wèn)題轉(zhuǎn)化為求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的極值. 顯然其解為x1 = b1/2a11 = 50, x2 = b2/2a22 = 70, 我們把它作為原問(wèn)題的初始值.,總利潤(rùn)為： z(x1,x2)=(p1-q1)x1+(p2-q2)x2,模型求解,1.建立M-文件fun.m: function f = fu

42、n(x) y1=(100-x(1)- 0.1*x(2)-(30*exp(-0.015*x(1)+20)*x(1); y2=(280-0.2*x(1)- 2*x(2)-(100*exp(-0.02*x(2)+30)*x(2); f=-y1-y2;,2.輸入命令: x0=50,70; x=fminunc(fun,x0), z=fun(x),3.計(jì)算結(jié)果: x=23.9025, 62.4977, z=6.4135e+003 即甲的產(chǎn)量為23.9025,乙的產(chǎn)量為62.4977,最大利潤(rùn)為6413.5.,非線(xiàn)性規(guī)劃建模,有約束非線(xiàn)性規(guī)劃,教學(xué)目的,教學(xué)內(nèi)容,2、掌握用數(shù)學(xué)軟件求解優(yōu)化問(wèn)題。,1、直觀了

43、解非線(xiàn)性規(guī)劃的基本內(nèi)容。,1.非線(xiàn)性規(guī)劃的基本理論。,2. 用數(shù)學(xué)軟件求解非線(xiàn)性規(guī)劃。,3. 鋼管訂購(gòu)及運(yùn)輸優(yōu)化模型,*非線(xiàn)性規(guī)劃的基本解法,非線(xiàn)性規(guī)劃,非線(xiàn)性規(guī)劃的基本概念,定義 如果目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線(xiàn)性函數(shù)時(shí)的最優(yōu)化問(wèn)題就叫做非線(xiàn)性規(guī)劃問(wèn)題,非線(xiàn)性規(guī)劃的基本概念,一般形式: （1） 其中 ， 是定義在 En 上的實(shí)值函數(shù)，簡(jiǎn)記:,其它情況: 求目標(biāo)函數(shù)的最大值或約束條件為小于等于零的情況，都可通過(guò)取其相反數(shù)化為上述一般形式,定義1 把滿(mǎn)足問(wèn)題（1）中條件的解 稱(chēng)為可行解（或可行點(diǎn)），所有可行點(diǎn)的集合稱(chēng)為可行集（或可行域）記為D即 問(wèn)題(1)可簡(jiǎn)記為 ,定義2 對(duì)于問(wèn)題(1

44、)，設(shè) ， 若存在 ,使得對(duì)一切 ，且 ，都有 ，則稱(chēng)X*是f(X)在D上的局部極小值點(diǎn)（局部最優(yōu)解）特別地當(dāng) 時(shí),若 ，則稱(chēng)X*是f(X)在D上的嚴(yán)格局部極小值點(diǎn)（嚴(yán)格局部最優(yōu)解）,定義3 對(duì)于問(wèn)題(1),設(shè) ,對(duì)任意的 ,都有 則稱(chēng)X*是f(X)在D上的全局極小值點(diǎn)（全局最優(yōu)解）特別地當(dāng) 時(shí)，若 ，則稱(chēng)X*是f(X)在D上的嚴(yán)格全局極小值點(diǎn)（嚴(yán)格全局最優(yōu)解）,非線(xiàn)性規(guī)劃的基本解法,SUTM外點(diǎn)法,SUTM內(nèi)點(diǎn)法（障礙罰函數(shù)法）,1. 罰函數(shù)法,2. 近似規(guī)劃法,罰函數(shù)法,罰函數(shù)法基本思想是通過(guò)構(gòu)造罰函數(shù)把約束問(wèn)題轉(zhuǎn)化為一系列無(wú)約束最優(yōu)化問(wèn)題，進(jìn)而用無(wú)約束最優(yōu)化方法去求解這類(lèi)方法稱(chēng)為序列無(wú)約

45、束最小化方法.簡(jiǎn)稱(chēng)為SUMT法 其一為SUMT外點(diǎn)法,其二為SUMT內(nèi)點(diǎn)法,其中T(X,M)稱(chēng)為罰函數(shù)，M稱(chēng)為罰因子，帶M的項(xiàng)稱(chēng)為罰項(xiàng)，這里的罰函數(shù)只對(duì)不滿(mǎn)足約束條件的點(diǎn)實(shí)行懲罰:當(dāng) 時(shí)，滿(mǎn)足各 ，故罰項(xiàng)=0，不受懲罰當(dāng) 時(shí)，必有 的約束條件，故罰項(xiàng)0，要受懲罰,SUTM外點(diǎn)法,罰函數(shù)法的缺點(diǎn)是：每個(gè)近似最優(yōu)解Xk往往不是容許解，而只能近似滿(mǎn)足約束，在實(shí)際問(wèn)題中這種結(jié)果可能不能使用；在解一系列無(wú)約束問(wèn)題中，計(jì)算量太大，特別是隨著Mk的增大，可能導(dǎo)致錯(cuò)誤,1、任意給定初始點(diǎn)X0，取M11，給定允許誤差 ，令k=1； 2、求無(wú)約束極值問(wèn)題 的最優(yōu)解，設(shè)為Xk=X(Mk)，即 ； 3、若存在 ，使

46、，則取MkM( )令k=k+1返回（2），否則，停止迭代得最優(yōu)解 . 計(jì)算時(shí)也可將收斂性判別準(zhǔn)則 改為 .,SUTM外點(diǎn)法(罰函數(shù)法)的迭代步驟,SUTM內(nèi)點(diǎn)法（障礙函數(shù)法）,內(nèi)點(diǎn)法的迭代步驟,近似規(guī)劃法的基本思想：將問(wèn)題(3)中的目標(biāo)函數(shù) 和約束條件 近似為線(xiàn)性函數(shù)，并對(duì)變量的取值范圍加以限制，從而得到一個(gè)近似線(xiàn)性規(guī)劃問(wèn)題,再用單純形法求解之，把其符合原始條件的最優(yōu)解作為(3)的解的近似,近似規(guī)劃法,每得到一個(gè)近似解后，都從這點(diǎn)出發(fā)，重復(fù)以上步驟,這樣，通過(guò)求解一系列線(xiàn)性規(guī)劃問(wèn)題，產(chǎn)生一個(gè)由線(xiàn)性規(guī)劃最優(yōu)解組成的序列，經(jīng)驗(yàn)表明，這樣的序列往往收斂于非線(xiàn)性規(guī)劃問(wèn)題的解。,近似規(guī)劃法的算法步驟如下

47、,用MATLAB軟件求解,其輸入格式如下: 1.x=quadprog(H,C,A,b); 2.x=quadprog(H,C,A,b,Aeq,beq); 3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6.x,fval=quaprog(.); 7.x,fval,exitflag=quaprog(.); 8.x,fval,exitflag,output=quaprog(.);,1

48、、二次規(guī)劃,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,1、寫(xiě)成標(biāo)準(zhǔn)形式：,2、 輸入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3、運(yùn)算結(jié)果為： x =0.6667 1.3333 z = -8.2222,s.t.,1. 首先建立M文件fun.m,定義目標(biāo)函數(shù)F（X）: function f=fun(X); f=F(X);,2、

49、一般非線(xiàn)性規(guī)劃,其中X為n維變?cè)蛄浚珿(X)與Ceq(X)均為非線(xiàn)性函數(shù)組成的向量，其它變量的含義與線(xiàn)性規(guī)劃、二次規(guī)劃中相同.用Matlab求解上述問(wèn)題，基本步驟分三步：,3. 建立主程序.非線(xiàn)性規(guī)劃求解的函數(shù)是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon) (5)x=fmincon(fun,X0,A

50、,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmincon(.),輸出極值點(diǎn),M文件,迭代的初值,參數(shù)說(shuō)明,變量上下限,注意： 1 fmincon函數(shù)提供了大型優(yōu)化算法和中型優(yōu)化算法。默認(rèn)時(shí)，若在fun函數(shù)中提供了梯度（options參數(shù)的GradObj設(shè)置為on），并且只有上下界存在或只有等式約束，fmincon函數(shù)將選擇大型算法。當(dāng)既有等式約束又有梯度約束時(shí)，使用中型算法。 2 fmincon函數(shù)的中

51、型算法使用的是序列二次規(guī)劃法。在每一步迭代中求解二次規(guī)劃子問(wèn)題，并用BFGS法更新拉格朗日Hessian矩陣。 3 fmincon函數(shù)可能會(huì)給出局部最優(yōu)解，這與初值X0的選取有關(guān)。,1、寫(xiě)成標(biāo)準(zhǔn)形式： s.t.,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,例2,2、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,3、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fminco

52、n(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、運(yùn)算結(jié)果為： x = 0.7647 1.0588 fval = -2.0294,1先建立M文件 fun4.m,定義目標(biāo)函數(shù): function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,例3,2再建立M文件mycon.m定義非線(xiàn)性約束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-

53、x(1)*x(2)-10;,3主程序youh3.m為: x0=-1;1; A=;b=; Aeq=1 1;beq=0; vlb=;vub=; x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),3. 運(yùn)算結(jié)果為： x = -1.2250 1.2250 fval = 1.8951,例4,1先建立M-文件fun.m定義目標(biāo)函數(shù): function f=fun(x); f=-2*x(1)-x(2);,2再建立M文件mycon2.m定義非線(xiàn)性約束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-

54、7;,3. 主程序fxx.m為: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2),4. 運(yùn)算結(jié)果為: x = 4.0000 3.0000 fval =-11.0000 exitflag = 1 output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: ,應(yīng)用實(shí)例： 供應(yīng)與選址,某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表

55、示，距離單位：千米 ）及水泥日用量d(噸)由下表給出。目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20噸。假設(shè)從料場(chǎng)到工地之間均有直線(xiàn)道路相連。 （1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少?lài)嵥?，使總的噸千米?shù)最小。 （2）為了進(jìn)一步減少?lài)嵡讛?shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20噸，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？,（一）、建立模型,記工地的位置為(ai，bi)，水泥日用量為di，i=1,6;料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為ej，j=1,2；從料場(chǎng)j向工地i的運(yùn)送量為Xij。,當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij， 當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策

56、變量為：Xij，xj，yj。,（二）使用臨時(shí)料場(chǎng)的情形,使用兩個(gè)臨時(shí)料場(chǎng)A(5,1)，B(2,7).求從料場(chǎng)j向工地i的運(yùn)送量為Xij，在各工地用量必須滿(mǎn)足和各料場(chǎng)運(yùn)送量不超過(guò)日儲(chǔ)量的條件下，使總的噸千米數(shù)最小，這是線(xiàn)性規(guī)劃問(wèn)題. 線(xiàn)性規(guī)劃模型為：,設(shè)X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 編寫(xiě)程序gying1.m,計(jì)算結(jié)果為：,x = 3.0000 5.0000 0.0000 7.0000 0.0

57、000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000 fval = 136.2275,（三）改建兩個(gè)新料場(chǎng)的情形,改建兩個(gè)新料場(chǎng),要同時(shí)確定料場(chǎng)的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最小.這是非線(xiàn)性規(guī)劃問(wèn)題。非線(xiàn)性規(guī)劃模型為：,設(shè) X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=

58、X16,（1）先編寫(xiě)M文件liaoch.m定義目標(biāo)函數(shù)。,(2) 取初值為線(xiàn)性規(guī)劃的計(jì)算結(jié)果及臨時(shí)料場(chǎng)的坐標(biāo): x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7; 編寫(xiě)主程序gying2.m.,(3) 計(jì)算結(jié)果為：,x= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867 fval = 105.4626 exitflag = 1,(4) 若修改主程序gying2.m, 取初值為上面的計(jì)算結(jié)果: x0= 3.0000 5.0000 0.070

59、7 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867,得結(jié)果為: x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852 fval =103.4760 exitflag = 1,總的噸千米數(shù)比上面結(jié)果略?xún)?yōu).,(5) 若再取剛得出的結(jié)果為初值, 卻計(jì)算不出最優(yōu)解.,(6) 若取初值為: x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8

60、687 7.2479 7.7499, 則計(jì)算結(jié)果為: x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500 fval =89.8835 exitflag = 1 總的噸千米數(shù)89.8835比上面結(jié)果更好.,通過(guò)此例可看出fmincon函數(shù)在選取初值上的重要性.,連續(xù)結(jié)構(gòu)體建模與優(yōu)化設(shè)計(jì),連續(xù)體形狀優(yōu)化例一,連續(xù)體形狀優(yōu)化例二,注：并非結(jié) 構(gòu)變形動(dòng)畫(huà)， 而是結(jié)構(gòu)受 力狀況下自 動(dòng)尋優(yōu)過(guò)程 注意：網(wǎng)格 變化過(guò)程 （網(wǎng)格拓?fù)?不改變，類(lèi) 似蜘蛛網(wǎng)受 力變化）,離散模型敏度分析

61、方法,對(duì)E求導(dǎo),？,對(duì)E求導(dǎo),離散法主要為有限 元程序開(kāi)發(fā)者應(yīng)用,代入已知得所求,連續(xù)模型敏度分析方法,敏度表達(dá)為位移、 應(yīng)力等和區(qū)域形狀 變化量的邊界積分 或區(qū)域積分的形式,圖 連續(xù)體變形過(guò)程的映射示意圖,網(wǎng)格均勻化(Mesh Smoothing),啟發(fā)式算法,啟發(fā)式算法(heuristic algorithm)是相對(duì)于最優(yōu)化算法提出的,啟發(fā)式算法定義：一種技術(shù)。這種技術(shù)使得在可接受的計(jì)算 的計(jì)算費(fèi)用內(nèi)去尋找最好的解，但不一定能保證所得解的可 行性和最優(yōu)性，甚至在多數(shù)情況下，無(wú)法闡述所得解同最優(yōu) 解的近似程度,結(jié)構(gòu)優(yōu)化之滿(mǎn)應(yīng)力法,滿(mǎn)應(yīng)力法理論上受啟發(fā)于生物進(jìn)化方式,滿(mǎn)應(yīng)力法是一種經(jīng)過(guò)實(shí)踐檢驗(yàn)的較好的優(yōu)化方法,滿(mǎn)應(yīng)力法數(shù)學(xué)模型可以看成是最優(yōu)問(wèn)題的近似模型,連續(xù)體拓?fù)鋬?yōu)化例一,注意：圖片中的孤立塊和鋸齒邊界形狀,連續(xù)體拓?fù)鋬?yōu)化例二,注意：圖片中的棋盤(pán)圖案,連續(xù)體拓?fù)鋬?yōu)化例三,注意：拓?fù)鋬?yōu)化是 一種概念設(shè)計(jì),映射反演方法例一,微分方程,代數(shù)方程,求解代數(shù)方程,方程解,拉氏變換,反拉氏變換,RMI方法使用條件：,映射須是兩類(lèi)數(shù)學(xué)對(duì)象之間 的一一對(duì)應(yīng)關(guān)系； 映射須是可定映的； 逆映射（反演）具有能行性,授課結(jié)束 謝 謝 大 家！,