第5講_無(wú)約束優(yōu)化

1、1經(jīng)濟(jì)數(shù)學(xué)系數(shù)學(xué)建模研究室無(wú)約束最優(yōu)化無(wú)約束最優(yōu)化數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)2實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容2、掌握用數(shù)學(xué)軟件包求解無(wú)約束最優(yōu)化問(wèn)題。、掌握用數(shù)學(xué)軟件包求解無(wú)約束最優(yōu)化問(wèn)題。1、了解無(wú)約束最優(yōu)化基本算法。、了解無(wú)約束最優(yōu)化基本算法。1 1、無(wú)約束優(yōu)化基本思想及基本算法。、無(wú)約束優(yōu)化基本思想及基本算法。4 4、實(shí)驗(yàn)作業(yè)。、實(shí)驗(yàn)作業(yè)。3、用、用MATLAB求解無(wú)約束優(yōu)化問(wèn)題。求解無(wú)約束優(yōu)化問(wèn)題。2、MATLAB優(yōu)化工具箱簡(jiǎn)介優(yōu)化工具箱簡(jiǎn)介3 無(wú)約束最優(yōu)化問(wèn)題無(wú)約束最優(yōu)化問(wèn)題返回4 XfnEXmin 其中 1:EEfn標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式：求解無(wú)約束最優(yōu)化問(wèn)題的基本思想求解

2、無(wú)約束最優(yōu)化問(wèn)題的基本思想求解的基本思想求解的基本思想 ( 以二元函數(shù)為例 )1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf連續(xù)可微 XfnEXmax = minXfnEX 56多局部極小298.0f0f298.0f 唯一極小(全局極小)2122212121322)(xxxxxxxxf7搜索過(guò)程搜索過(guò)程21221221)1 ()(100)(minxxxxxf最優(yōu)點(diǎn) (1 1)初始點(diǎn) (-1 1)1x2xf-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.3

3、30.200.800.630.050.950.90 0.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8返回8 給定初始點(diǎn)nEX 0，允許誤差0,令 k=0； 計(jì)算kXf； 檢驗(yàn)是否滿(mǎn)足收斂性的判別準(zhǔn)則： kXf， 若滿(mǎn)足，則停止迭代，得點(diǎn)kXX*，否則進(jìn)行； 令kkXfS，從kX出發(fā)，沿kS進(jìn)行一維搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回.無(wú)約束優(yōu)化問(wèn)題的基本算法無(wú)約束優(yōu)化問(wèn)題的基本算法 最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點(diǎn)是工作量小，存儲(chǔ)變量較少,初始點(diǎn)

4、要求不高；缺點(diǎn)是收斂慢，最速下降法適用于尋優(yōu)過(guò)程的前期迭代或作為間插步驟，當(dāng)接近極值點(diǎn)時(shí)，宜選用別種收斂快的算法. 1 1最速下降法（共軛梯度法）算法步驟：最速下降法（共軛梯度法）算法步驟：92 2牛頓法算法步驟：牛頓法算法步驟：(1) 選定初始點(diǎn)nEX 0，給定允許誤差0，令 k=0；(2) 求kXf,12kXf,檢驗(yàn)：若kXf,則 停止迭代,kXX*.否則, 轉(zhuǎn)向(3)；(3) 令 kkkXfXfS12（牛頓方向） ； (4) kkkSXX1,1 kk,轉(zhuǎn)回(2). 如果f是對(duì)稱(chēng)正定矩陣A的二次函數(shù)，則用牛頓法經(jīng)過(guò)一次迭代一次迭代就可達(dá)到最優(yōu)點(diǎn),如不是二次函數(shù)，則牛頓法不能一步達(dá)到極值點(diǎn)，

5、但由于這種函數(shù)在極值點(diǎn)附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的. 牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計(jì)算二階導(dǎo)數(shù)和逆矩陣，就加大了計(jì)算機(jī)計(jì)算量和存儲(chǔ)量.103 3擬牛頓法擬牛頓法 為克服牛頓法的缺點(diǎn)，同時(shí)保持較快收斂速度的優(yōu)點(diǎn)，利用第 k 步和第 k+1 步得到的kX，1kX，)(kXf，)(1kXf，構(gòu)造一個(gè)正定矩陣1kG近似代替)(2kXf,或用1kH近似代替12)(kXf，將牛頓方向改為： 1kG1kS=-)(1kXf，1kS=-1kH)(1kXf從而得到下降方向.11 通常采用迭代法計(jì)算1kG，1kH，迭迭代代公公式式為:B BF FG GS S（

6、Boryden-Fletcher-Goldfarb-Shanno）公式 kkTkkTkkkkTkTkkkkxGxGxxGxfffGG)()()()(1 kTkTkkkTkkkTkkkxfxxxffHfHH)()()()(11 kTkTkkkkTkkxfxfHHfx)()()(12 D DF FP P（Davidon-Fletcher-Powell）公式： kTkTkkkTkkkTkkkXffffXXGXGG)()()()(11 kTkTkkkkTkkfXfXGGXf)()()( kkTkkTkkkkTkTkkkkfHfHffHXfXXHH)()()()(1 計(jì)算時(shí)可置IH 1（單位陣） ，對(duì)于

7、給出的1X利 用上面的公式進(jìn)行遞推.這種方法稱(chēng)為擬牛頓法擬牛頓法. . 返回13MatlabMatlab優(yōu)化工具箱簡(jiǎn)介優(yōu)化工具箱簡(jiǎn)介1.MATLAB1.MATLAB求解優(yōu)化問(wèn)題的主要函數(shù)求解優(yōu)化問(wèn)題的主要函數(shù)類(lèi) 型模 型基本函數(shù)名一元函數(shù)極小Min F（x）s.t.x1xx2x=fminbnd(F,x1,x2)無(wú)約束極小Min F(X)X=fminunc(F,X0)X=fminsearch(F,X0)線(xiàn)性規(guī)劃M(mǎn)in XcTs.t.AX=bX=linprog(c,A,b)二次規(guī)劃M(mǎn)in 21xTHx+cTxs.t. Ax=bX=quadprog(H,c,A,b)約束極小（非線(xiàn)性規(guī)劃）Min F(

8、X)s.t. G(X)=0X=fmincon(FG,X0)達(dá)到目標(biāo)問(wèn)題Min rs.t. F(x)-wr=goalX=fgoalattain(F,x,goal,w)極小極大問(wèn)題Min max Fi(x)X Fi(x)s.t. G(x)0,則x為解;否則,x不是最終解,它只是迭代制止時(shí)優(yōu)化過(guò)程的值所有優(yōu)化函數(shù)fval解x處的目標(biāo)函數(shù)值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出條件: exitflag0,表目標(biāo)函數(shù)收斂于解x處 exitflag=0,表已達(dá)到函數(shù)評(píng)價(jià)

9、或迭代的最大次數(shù) exitflag0,表目標(biāo)函數(shù)不收斂output包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu). Iterations:迭代次數(shù) Algorithm:所采用的算法 FuncCount:函數(shù)評(píng)價(jià)次數(shù)所有優(yōu)化函數(shù)164 4控制參數(shù)控制參數(shù)optionsoptions的設(shè)置的設(shè)置 (3) MaxIterMaxIter: 允許進(jìn)行迭代的最大次數(shù),取值為正整數(shù).OptionsOptions中常用的幾個(gè)參數(shù)的名稱(chēng)、含義、取值如下中常用的幾個(gè)參數(shù)的名稱(chēng)、含義、取值如下: : (1)DisplayDisplay: 顯示水平.取值為off時(shí),不顯示輸出; 取值為iter時(shí),顯示每次迭代的信息;取值為final時(shí),

10、顯示最終結(jié)果.默認(rèn)值為final.(2)MaxFunEvalsMaxFunEvals: 允許進(jìn)行函數(shù)評(píng)價(jià)的最大次數(shù),取值為正整數(shù).17例：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ù)控制參數(shù)optionsoptions可以通過(guò)函數(shù)可以通過(guò)函數(shù)optimsetoptimset創(chuàng)建或修改。命創(chuàng)建或修改。命令的格式如下：令的格式如下：(1) options=optimset(optimfun)options=optimset(optimfun) 創(chuàng)建一個(gè)含

11、有所有參數(shù)名,并與優(yōu)化函數(shù)optimfun相關(guān)的默認(rèn)值的選項(xiàng)結(jié)構(gòu)options.（2）options=optimset(param1,value1,param2,value2,.)options=optimset(param1,value1,param2,value2,.) 創(chuàng)建一個(gè)名稱(chēng)為options的優(yōu)化選項(xiàng)參數(shù),其中指定的參數(shù)具有指定值,所有未指定的參數(shù)取默認(rèn)值.(3)options=optimset(oldops,param1,value1,param2,options=optimset(oldops,param1,value1,param2, value2,.) value2,.)

12、創(chuàng)建名稱(chēng)為oldops的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應(yīng)的參數(shù).返回18用用MatlabMatlab解無(wú)約束優(yōu)化問(wèn)題解無(wú)約束優(yōu)化問(wèn)題 1. 一一元元函函數(shù)數(shù)無(wú)無(wú)約約束束優(yōu)優(yōu)化化問(wèn)問(wèn)題題: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標(biāo)函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。常用格式如下：常用格式如下：（1）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) )（2）x= fminbnd (x= fminbnd (fu

13、n,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）19運(yùn)行結(jié)果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448To Matlab(wliti1) 例例 1 1 求 f = 2xexsin在 0 x8 中的最

14、小值與最大值 主程序?yàn)橹鞒绦驗(yàn)閣liti1.m:wliti1.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)20例例2 2 對(duì)邊長(zhǎng)為3米的正方形鐵板，在四個(gè)角剪去相等的正方形以制成方形無(wú)蓋水槽，問(wèn)如何剪法使水槽的容積最大？設(shè)剪去的正方形的邊長(zhǎng)為x，則水槽的容積為：xx )23(2建立無(wú)約束優(yōu)化模型為：min y=-xx )23(2， 0 x 0，且a11 a12；同理， p2 = b2 - a21 x

15、1- a22 x2 ，b2，a21，a22 0，且a22 a21 .2 2成本與產(chǎn)量成負(fù)指數(shù)關(guān)系成本與產(chǎn)量成負(fù)指數(shù)關(guān)系甲的成本隨其產(chǎn)量的增長(zhǎng)而降低,且有一個(gè)漸進(jìn)值,可以假設(shè)為負(fù)指數(shù)關(guān)系,即: 0,11111111crcerqx 同理， 0,22222222crcerqx30 模型建立模型建立 若根據(jù)大量的統(tǒng)計(jì)數(shù)據(jù),求出系數(shù)b1=100,a11=1,a12=0.1,b2=280,a21=0.2,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)化模型,先忽略成本,并令a

16、12=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)為：總利潤(rùn)為： z z( (x x1 1,x,x2 2)=()=(p p1 1-q-q1 1) )x x1 1+(+(p p2 2-q-q2 2) )x x2 231 模型求解模型求解 1.建立M-文件fun.m: function f = fun(x) y1=(100-x(1)- 0.1*x(2)-(30*exp(-0.015*x(1)+20)

17、*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.To Matlab(wliti5)返回32實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè)1. 求下列函數(shù)的極小點(diǎn)： 1) 2123222118294xxxxxXf；2) 212122212223xxxxxxXf；3) 224121

18、xXf. 第1） ，2）題的初始點(diǎn)可任意選取， 第3）題的初始點(diǎn)取為T(mén)X1 , 00.332 2. . 梯梯子子長(zhǎng)長(zhǎng)度度問(wèn)問(wèn)題題一樓房的后面是一個(gè)很大的花園. 在花園中緊靠著樓房有一個(gè)溫室,溫室伸入花園 2m,高 3m,溫室正上方是樓房的窗臺(tái). 清潔工打掃窗臺(tái)周?chē)?他得用梯子越過(guò)溫室,一頭放在花園中,一頭 靠在樓房的墻上. 因?yàn)闇厥沂遣荒艹惺?a 梯子壓力的,所以梯子太短是不行的. 現(xiàn)清潔工只有一架 7m 長(zhǎng)的梯子, b 你認(rèn)為它能達(dá)到要求嗎? 能 滿(mǎn)足要求的梯子的最小 長(zhǎng)度為多少? 343 3. . 陳陳酒酒出出售售的的最最佳佳時(shí)時(shí)機(jī)機(jī)問(wèn)問(wèn)題題某酒廠有批新釀的好酒,如果現(xiàn)在就出售,可得總收入 R0=50 萬(wàn)元(人民幣),如果窖藏起來(lái)待來(lái)日(第 n 年)按陳酒價(jià)格出售,第 n 年末可得總收入60neRR (萬(wàn)元),而銀行利率為 r=0.05,試分析這批好酒窖藏多少年后出售可使總收入的現(xiàn)值最大. (假設(shè)現(xiàn)有資金 X 萬(wàn)元,將其存入銀行,到第 n 年時(shí)增值為 R(n)萬(wàn)元,則稱(chēng) X 為 R(n)的現(xiàn)值.)并填下表：35第一種方案：將酒現(xiàn)在出售，所獲 50 萬(wàn)元本金存入銀行；第二種方案：將酒窖藏起來(lái)，待第 n 年出售。（1） 計(jì)算 15 年內(nèi)采用兩種方案，50 萬(wàn)元增值的數(shù)目并 填入表 1，2 中；（2） 計(jì)算 15 年內(nèi)陳酒