[互聯(lián)網(wǎng)]第5講 無約束優(yōu)化

1、無約束最優(yōu)化無約束最優(yōu)化數(shù)學建模與數(shù)學實驗數(shù)學建模與數(shù)學實驗教學目的教學目的教學內(nèi)容教學內(nèi)容2、掌握用數(shù)學軟件包求解無約束最優(yōu)化問題。、掌握用數(shù)學軟件包求解無約束最優(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)化工具箱簡介 無約束最優(yōu)化問題無約束最優(yōu)化問題求解無約束最優(yōu)化問題的的基本思想求解無約束最優(yōu)化問題的的基本思想*無約束最優(yōu)化問題的基本算法無約束最優(yōu)化問題的基本算法返回 xfnexmi

2、n 其中 1:eefn標準形式：標準形式：求解無約束最優(yōu)化問題的基本思想求解無約束最優(yōu)化問題的基本思想求解的基本思想求解的基本思想 ( 以二元函數(shù)為例 )1x2x)(21xxf01x2x05310x1x2x)(0xf)(1xf)(2xf連續(xù)可微 xfnexmax = minxfnex 多局部極小298.0f0f298.0f 唯一極小(全局極小)2122212121322)(xxxxxxxxf搜索過程搜索過程21221221)1 ()(100)(minxxxxxf最優(yōu)點 (1 1)初始點 (-1 1)1x2xf-114.00-0.790.583.39-0.530.232.60-0.180.001

3、.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.90 0.0030.990.991e-40.9990.9981e-50.9997 0.9998 1e-8返回無約束優(yōu)化問題的基本算法無約束優(yōu)化問題的基本算法 最速下降法是一種最基本的算法，它在最優(yōu)化方法中占有重要地位.最速下降法的優(yōu)點是工作量小，存儲變量較少,初始點要求不高；缺點是收斂慢，最速下降法適用于尋優(yōu)過程的前期迭代或作為間插步驟，當接近極值點時，宜選用別種收斂快的算法. 1 1最速下降法（共軛梯度法）算法步驟：最速下降法（共軛梯度法）算法步驟：最速下降法求解示例：最速下降

4、法求解示例：2 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ù)在極值點附近和二次函數(shù)很近似,因此牛頓法的收斂速度還是很快的. 牛頓法的收斂速度雖然較快，但要求hessian矩陣要可逆，要計算二階導數(shù)和逆矩陣，就加大了計算機計算量

5、和存儲量.牛頓法求解示例牛頓法求解示例3 3擬牛頓法擬牛頓法 通常采用迭代法計算1kg，1kh，迭代公式迭代公式為:bfgsbfgs（boryden-fletcher-goldfarb-shanno）公式 kktkktkkkktktkkkkxgxgxxgxfffgg)()()()(1 ktktkkktkkktkkkxfxxxffhfhh)()()()(11 ktktkkkktkkxfxfhhfx)()()(返回matlabmatlab優(yōu)化工具箱簡介優(yōu)化工具箱簡介1.matlab1.matlab求解優(yōu)化問題的主要函數(shù)求解優(yōu)化問題的主要函數(shù)類 型模 型基本函數(shù)名一元函數(shù)極小min f（x）s.t.

6、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)=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不是最終解

7、,它只是迭代制止時優(yōu)化過程的值所有優(yōu)化函數(shù)fval解x處的目標函數(shù)值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出條件: exitflag0,表目標函數(shù)收斂于解x處 exitflag=0,表已達到函數(shù)評價或迭代的最大次數(shù) exitflag0,表目標函數(shù)不收斂output包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu). iterations:迭代次數(shù) algorithm:所采用的算法 funccount:函數(shù)評價次數(shù)所有優(yōu)化函數(shù)4 4控制參數(shù)控制參數(shù)optionsoptions的設(shè)置的設(shè)

8、置 (3) maxitermaxiter: 允許進行迭代的最大次數(shù),取值為正整數(shù).optionsoptions中常用的幾個參數(shù)的名稱、含義、取值如下中常用的幾個參數(shù)的名稱、含義、取值如下: : (1)displaydisplay: 顯示水平.取值為off時,不顯示輸出; 取值為iter時,顯示每次迭代的信息;取值為final時,顯示最終結(jié)果.默認值為final.(2)maxfunevalsmaxfunevals: 允許進行函數(shù)評價的最大次數(shù),取值為正整數(shù).例：opts=optimset(display,iter,tolfun,1e-8) 該語句創(chuàng)建一個稱為opts的優(yōu)化選項結(jié)構(gòu),其中顯示參數(shù)設(shè)

9、為iter, tolfun參數(shù)設(shè)為1e-8. 控制參數(shù)控制參數(shù)optionsoptions可以通過函數(shù)可以通過函數(shù)optimsetoptimset創(chuàng)建或修改。命創(chuàng)建或修改。命令的格式如下：令的格式如下：(1) options=optimset(optimfunoptions=optimset(optimfun) 創(chuàng)建一個含有所有參數(shù)名,并與優(yōu)化函數(shù)optimfun相關(guān)的默認值的選項結(jié)構(gòu)options.（2）options=optimset(param1,value1,param2,value2,.)options=optimset(param1,value1,param2,value2,.)

10、創(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的參數(shù)的拷貝,用指定的參數(shù)值修改oldops中相應(yīng)的參數(shù).返回用用matlabmatlab解無約束優(yōu)化問題解無約束優(yōu)化問題 1. 一元函數(shù)無約束優(yōu)化問題一元函數(shù)無約束優(yōu)化問題: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右邊可選用

11、（1）或（2）的等式右邊。 函數(shù)fminbnd的算法基于黃金分割法和二次插值法，它要求目標函數(shù)必須是連續(xù)函數(shù)，并可能只給出局部最優(yōu)解。常用格式如下：常用格式如下：（1）x= fminbndx= fminbnd ( (fun,xfun,x1 1,x,x2 2) )（2）x= fminbndx= fminbnd ( (fun,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，ex

12、itflagexitflag，output= fminbndoutput= fminbnd（.）運行結(jié)果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448to matlab(wliti1) 例例 1 1 求 f = 2xexsin在 0 x 0，且a11 a12；同理， p2 = b2 - a21 x1- a22 x2 ，b2，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 同理

13、， 0,22222222crcerqx 模型建立模型建立 若根據(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,問題轉(zhuǎn)化為求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的極值. 顯然其解為x1 = b1/2a11 = 50, x2 = b2/2a22 = 70,我們把它作為原問題

14、的初始值.總利潤為：總利潤為： 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 2 模型求解模型求解 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=(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.

15、計算結(jié)果: x=23.9025, 62.4977, z=6.4135e+003 即甲的產(chǎn)量為23.9025,乙的產(chǎn)量為62.4977,最大利潤為6413.5.to matlab(wliti5)返回作作 業(yè)業(yè)2. 2. 梯子長度問題梯子長度問題一樓房的后面是一個很大的花園. 在花園中緊靠著樓房有一個溫室,溫室伸入花園 2m,高 3m,溫室正上方是樓房的窗臺. 清潔工打掃窗臺周圍,他得用梯子越過溫室,一頭放在花園中,一頭 靠在樓房的墻上. 因為溫室是不能承受 a 梯子壓力的,所以梯子太短是不行的. 現(xiàn)清潔工只有一架 7m 長的梯子, b 你認為它能達到要求嗎? 能 滿足要求的梯子的最小 長度為多少

16、? 3. 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)值.)并填下表：第一種方案：將酒現(xiàn)在出售，所獲 50 萬元本金存入銀行；第二種方案：將酒窖藏起來，待第 n 年出售。（1） 計算 15 年內(nèi)采用兩種方案，50 萬元增值的數(shù)目并 填入表 1，2 中；（2） 計算 15 年內(nèi)陳酒出售后總收入 r（n）的現(xiàn)值填入 表 3 中。表 1 第一種方案第 1 年第 2