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

1、1無約束最優(yōu)化無約束最優(yōu)化數(shù)學(xué)建模與數(shù)學(xué)實驗數(shù)學(xué)建模與數(shù)學(xué)實驗2實驗?zāi)康膶嶒災(zāi)康膶嶒瀮?nèi)容實驗內(nèi)容2、掌握用數(shù)學(xué)軟件包求解無約束最優(yōu)化問題。、掌握用數(shù)學(xué)軟件包求解無約束最優(yōu)化問題。1、了解無約束最優(yōu)化基本算法。、了解無約束最優(yōu)化基本算法。1 1、無約束優(yōu)化基本思想及基本算法。、無約束優(yōu)化基本思想及基本算法。4 4、實驗作業(yè)。、實驗作業(yè)。3、用、用MATLAB求解無約束優(yōu)化問題。求解無約束優(yōu)化問題。2、MATLAB優(yōu)化工具箱簡介優(yōu)化工具箱簡介3 無約束最優(yōu)化問題無約束最優(yōu)化問題返回4 XfnEXmin 其中 1:EEfn標準形式：標準形式：求解無約束最優(yōu)化問題的基本思想求解無約束最優(yōu)化問題的基本思

2、想求解的基本思想求解的基本思想 ( 以二元函數(shù)為例 )1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf連續(xù)可微 XfnEXmax = minXfnEX 56多局部極小298.0f0f298.0f 唯一極小(全局極小)2122212121322)(xxxxxxxxf7搜索過程搜索過程21221221)1 ()(100)(minxxxxxf最優(yōu)點 (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.330.200.800.6

3、30.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出發(fā)，沿kS進行一維搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回.無約束優(yōu)化問題的基本算法無約束優(yōu)化問題的基本算法 最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，

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

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

6、cher-Goldfarb-Shanno）公式 kkTkkTkkkkTkTkkkkxGxGxxGxfffGG)()()()(1 kTkTkkkTkkkTkkkxfxxxffHfHH)()()()(11 kTkTkkkkTkkxfxfHHfx)()()(12 D DF FP P（Davidon-Fletcher-Powell）公式： kTkTkkkTkkkTkkkXffffXXGXGG)()()()(11 kTkTkkkkTkkfXfXGGXf)()()( kkTkkTkkkkTkTkkkkfHfHffHXfXXHH)()()()(1 計算時可置IH 1（單位陣） ，對于給出的1X利 用上面的公

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

8、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不是最終解,它只是迭代制止時優(yōu)化過程的值所有優(yōu)化函數(shù)fval解x處的目標函數(shù)值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出條件: exitflag0,表目標函數(shù)收斂于解x處 exitflag=0,表已達到函數(shù)評價或迭代的最大次數(shù) exi

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

10、inal.(2)MaxFunEvalsMaxFunEvals: 允許進行函數(shù)評價的最大次數(shù),取值為正整數(shù).17例：opts=optimset(Display,iter,TolFun,1e-8) 該語句創(chuàng)建一個稱為opts的優(yōu)化選項結(jié)構(gòu),其中顯示參數(shù)設(shè)為iter, TolFun參數(shù)設(shè)為1e-8. 控制參數(shù)控制參數(shù)optionsoptions可以通過函數(shù)可以通過函數(shù)optimsetoptimset創(chuàng)建或修改。命創(chuàng)建或修改。命令的格式如下：令的格式如下：(1) options=optimset(optimfun)options=optimset(optimfun) 創(chuàng)建一個含有所有參數(shù)名,并與優(yōu)化函

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

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

13、x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）19運行結(jié)果： 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米的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？設(shè)剪去的正方形的邊長為x，則水槽的容積為：xx )23(2建立無約束優(yōu)化模型為：min y=-xx )23(2， 0 x 0，且a11 a12；同理， p2 = b2 - a21 x1- a22 x2 ，b

15、2，a21，a22 0，且a22 a21 .2 2成本與產(chǎn)量成負指數(shù)關(guān)系成本與產(chǎn)量成負指數(shù)關(guān)系甲的成本隨其產(chǎn)量的增長而降低,且有一個漸進值,可以假設(shè)為負指數(shù)關(guān)系,即: 0,11111111crcerqx 同理， 0,22222222crcerqx30 模型建立模型建立 若根據(jù)大量的統(tǒng)計數(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,則問題轉(zhuǎn)化為無約束優(yōu)化問題：求甲,乙兩個牌號的產(chǎn)量x1，x2，使總利潤z最大. 為簡化模型,先忽略成本,并令a12=0,a21=0,問

16、題轉(zhuǎn)化為求: 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)*x(1); y2=(2

17、80-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.計算結(jié)果: x=23.9025, 62.4977, z=6.4135e+003 即甲的產(chǎn)量為23.9025,乙的產(chǎn)量為62.4977,最大利潤為6413.5.To Matlab(wliti5)返回32實驗作業(yè)實驗作業(yè)1. 求下列函數(shù)的極小點： 1) 2123222118294xxxxxXf；2) 212122212223xxxxxxXf；3) 224121 xXf. 第1） ，2）

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