1、1經濟數學系數學建模研究室無約束最優化無約束最優化數學建模與數學實驗數學建模與數學實驗2實驗目的實驗目的實驗內容實驗內容2、掌握用數學軟件包求解無約束最優化問題。、掌握用數學軟件包求解無約束最優化問題。1、了解無約束最優化基本算法。、了解無約束最優化基本算法。1 1、無約束優化基本思想及基本算法。、無約束優化基本思想及基本算法。4 4、實驗作業。、實驗作業。3、用、用MATLAB求解無約束優化問題。求解無約束優化問題。2、MATLAB優化工具箱簡介優化工具箱簡介3 無約束最優化問題無約束最優化問題返回4 XfnEXmin 其中 1:EEfn標準形式：標準形式：求解無約束最優化問題的基本思想求解

2、無約束最優化問題的基本思想求解的基本思想求解的基本思想 ( 以二元函數為例 )1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf連續可微 XfnEXmax = minXfnEX 56多局部極小298.0f0f298.0f 唯一極小(全局極小)2122212121322)(xxxxxxxxf7搜索過程搜索過程21221221)1 ()(100)(minxxxxxf最優點 (1 1)初始點 (-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 給定初始點nEX 0，允許誤差0,令 k=0； 計算kXf； 檢驗是否滿足收斂性的判別準則： kXf， 若滿足，則停止迭代，得點kXX*，否則進行； 令kkXfS，從kX出發，沿kS進行一維搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回.無約束優化問題的基本算法無約束優化問題的基本算法 最速下降法是一種最基本的算法，它在最優化方法中占有重要地位.最速下降法的優點是工作量小，存儲變量較少,初始點

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

5、但由于這種函數在極值點附近和二次函數很近似,因此牛頓法的收斂速度還是很快的. 牛頓法的收斂速度雖然較快，但要求Hessian矩陣要可逆，要計算二階導數和逆矩陣，就加大了計算機計算量和存儲量.103 3擬牛頓法擬牛頓法 為克服牛頓法的缺點，同時保持較快收斂速度的優點，利用第 k 步和第 k+1 步得到的kX，1kX，)(kXf，)(1kXf，構造一個正定矩陣1kG近似代替)(2kXf,或用1kH近似代替12)(kXf，將牛頓方向改為： 1kG1kS=-)(1kXf，1kS=-1kH)(1kXf從而得到下降方向.11 通常采用迭代法計算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 計算時可置IH 1（單位陣） ，對于

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

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

9、或迭代的最大次數 exitflag0,表目標函數不收斂output包含優化結果信息的輸出結構. Iterations:迭代次數 Algorithm:所采用的算法 FuncCount:函數評價次數所有優化函數164 4控制參數控制參數optionsoptions的設置的設置 (3) MaxIterMaxIter: 允許進行迭代的最大次數,取值為正整數.OptionsOptions中常用的幾個參數的名稱、含義、取值如下中常用的幾個參數的名稱、含義、取值如下: : (1)DisplayDisplay: 顯示水平.取值為off時,不顯示輸出; 取值為iter時,顯示每次迭代的信息;取值為final時,

10、顯示最終結果.默認值為final.(2)MaxFunEvalsMaxFunEvals: 允許進行函數評價的最大次數,取值為正整數.17例：opts=optimset(Display,iter,TolFun,1e-8) 該語句創建一個稱為opts的優化選項結構,其中顯示參數設為iter, TolFun參數設為1e-8. 控制參數控制參數optionsoptions可以通過函數可以通過函數optimsetoptimset創建或修改。命創建或修改。命令的格式如下：令的格式如下：(1) options=optimset(optimfun)options=optimset(optimfun) 創建一個含

11、有所有參數名,并與優化函數optimfun相關的默認值的選項結構options.（2）options=optimset(param1,value1,param2,value2,.)options=optimset(param1,value1,param2,value2,.) 創建一個名稱為options的優化選項參數,其中指定的參數具有指定值,所有未指定的參數取默認值.(3)options=optimset(oldops,param1,value1,param2,options=optimset(oldops,param1,value1,param2, value2,.) value2,.)

12、創建名稱為oldops的參數的拷貝,用指定的參數值修改oldops中相應的參數.返回18用用MatlabMatlab解無約束優化問題解無約束優化問題 1. 一一元元函函數數無無約約束束優優化化問問題題: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右邊可選用（1）或（2）的等式右邊。 函數fminbnd的算法基于黃金分割法和二次插值法，它要求目標函數必須是連續函數，并可能只給出局部最優解。常用格式如下：常用格式如下：（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運行結果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448To Matlab(wliti1) 例例 1 1 求 f = 2xexsin在 0 x8 中的最

14、小值與最大值 主程序為主程序為wliti1.m:wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作圖語句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8)20例例2 2 對邊長為3米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？設剪去的正方形的邊長為x，則水槽的容積為：xx )23(2建立無約束優化模型為：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成本與產量成負指數關系成本與產量成負指數關系甲的成本隨其產量的增長而降低,且有一個漸進值,可以假設為負指數關系,即: 0,11111111crcerqx 同理， 0,22222222crcerqx30 模型建立模型建立 若根據大量的統計數據,求出系數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,則問題轉化為無約束優化問題：求甲,乙兩個牌號的產量x1，x2，使總利潤z最大. 為簡化模型,先忽略成本,并令a

16、12=0,a21=0,問題轉化為求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的極值. 顯然其解為x1 = b1/2a11 = 50, x2 = b2/2a22 = 70,我們把它作為原問題的初始值.總利潤為：總利潤為： 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.計算結果: x=23.9025, 62.4977, z=6.4135e+003 即甲的產量為23.9025,乙的產量為62.4977,最大利潤為6413.5.To Matlab(wliti5)返回32實驗作業實驗作業1. 求下列函數的極小點： 1) 2123222118294xxxxxXf；2) 212122212223xxxxxxXf；3) 224121

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