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

1、1第第5章章 無約束優(yōu)化無約束優(yōu)化目的目的內(nèi)容內(nèi)容2、掌握用、掌握用MATLAB求解無約束優(yōu)化問題求解無約束優(yōu)化問題1、了解無約束優(yōu)化基本算法、了解無約束優(yōu)化基本算法2、無約束優(yōu)化的基本方法、無約束優(yōu)化的基本方法3、用、用MATLAB求解無約束優(yōu)化問題求解無約束優(yōu)化問題1、實際問題中的無約束優(yōu)化模型、實際問題中的無約束優(yōu)化模型2 優(yōu)化問題的數(shù)學(xué)模型可行域目標函數(shù)，決策變量，fxnxRxxfz),(min 可行解可行解（只滿足（只滿足(2)）與）與 最優(yōu)解最優(yōu)解（滿足（滿足(1),(2)） 無約束優(yōu)化無約束優(yōu)化（只有（只有(1)）與）與 約束優(yōu)化約束優(yōu)化（(1),(2)）)2(, 2 , 1,

2、0)(. .)1 ()(minmixgtsxfzix 實際問題一般總有約束，何時可用無約束優(yōu)化處理？實際問題一般總有約束，何時可用無約束優(yōu)化處理？3實例實例1 1 產(chǎn)銷量的最佳安排產(chǎn)銷量的最佳安排某廠生產(chǎn)甲、乙兩個牌號的同一種產(chǎn)品，在產(chǎn)銷平某廠生產(chǎn)甲、乙兩個牌號的同一種產(chǎn)品，在產(chǎn)銷平衡的情況下，如何確定各自產(chǎn)量使利潤最大？衡的情況下，如何確定各自產(chǎn)量使利潤最大？注：產(chǎn)銷平衡指工廠的產(chǎn)量等于市場上的銷量。注：產(chǎn)銷平衡指工廠的產(chǎn)量等于市場上的銷量。目標：利潤目標：利潤銷量、（單件）價格銷量、（單件）價格產(chǎn)量、（單件）成本產(chǎn)量、（單件）成本4規(guī)律規(guī)律 1甲價格甲價格p1隨其銷量隨其銷量x1增長而降低

3、；增長而降低；乙銷量乙銷量x2的增長使的增長使p1下降下降假設(shè)假設(shè)1 價格與銷量呈線性關(guān)系價格與銷量呈線性關(guān)系0,1211121211111aabxaxabp0,2221222212122aabxaxabp乙的價格也有同樣的規(guī)律乙的價格也有同樣的規(guī)律522211121,)()(),(max21xqpxqpxxzxx目目 標標利潤最大利潤最大0,0,2222221111112211crcerqcrcerqxx成本隨其產(chǎn)量增加而降低，且有一漸進值成本隨其產(chǎn)量增加而降低，且有一漸進值假設(shè)假設(shè) 2 成本與產(chǎn)量呈負指數(shù)關(guān)系成本與產(chǎn)量呈負指數(shù)關(guān)系規(guī)律規(guī)律 2無約束無約束(非線性非線性)規(guī)劃規(guī)劃x1, x2

4、 0 ?60yx點點2 2x=629, y=375309.00 (1.30)864.3(2.0)飛機飛機x x=?,=?,y y=?=?點點1 1x=764, y=1393161.20 (0.80)點點3 3x=1571, y=25945.10 (0.60)北北點點4 4x=155, y=987飛機與監(jiān)控臺（圖中坐標和測量距離的單位是飛機與監(jiān)控臺（圖中坐標和測量距離的單位是“千米千米”）實例實例2 飛機精確定位問題飛機精確定位問題 7）飛機位置坐標（要求計算：，距離誤差為記測量距離為，角度誤差為記測量線傾斜角為分別為已知數(shù)據(jù)：監(jiān)控臺坐標yxdiiyxiiii, . ; 3,.,1, 1,.4;

5、),(44xiyi原始觀測角度原始觀測角度 (或或d4）誤差誤差點點120（2.81347弧度）弧度）0.80（0.0140弧度）弧度）點點2 262937545.10 （0.78714弧度）弧度）0.60（0.0105弧度）弧度）點點3 31571259309.00（5.39307弧度）弧度）1.30（0.0227弧度）弧度）點點4 4155987d4=864.3（km）2.0（km）8242424312)()(tan dyyxxxxyyMiniiiix,y42424)()()3 , 2 , 1(tandyyxxixxyyiii不考慮誤差因素不考慮誤差因素超定方程組

6、，超定方程組，非線性最小二乘！非線性最小二乘！量綱不符！量綱不符！ ？ 2442424312)()(tantan ddyyxxxxyyMiniiiiix,y9考慮誤差因素考慮誤差因素Min x; Min y; Max x; Max y.非線性規(guī)劃！非線性規(guī)劃！不等式組？不等式組？)2()()() 1)(3 , 2 , 1)(tan()tan(44242444dyyxxdixxyyiiiiii誤差非均勻分布！誤差非均勻分布！ ？ 10 以距離為約束，優(yōu)化角度誤差之和（或平方和）以距離為約束，優(yōu)化角度誤差之和（或平方和）或以角度為約束，優(yōu)化距離誤差或以角度為約束，優(yōu)化距離誤差 有人也可能會采用其他

7、目標，如：有人也可能會采用其他目標，如：僅部分考慮誤差僅部分考慮誤差! 角度與距離的角度與距離的“地位地位”不應(yīng)不同！不應(yīng)不同！312tan iiiix,yxxyyMin242424)()( dyyxxMinx,y44242444)()(s.t.dyyxxd)3 , 2 , 1)(tan()tan(s.t.ixxyyiiiiii11誤差一般服從什么分布？誤差一般服從什么分布？正態(tài)分布！正態(tài)分布！不同的量綱如何處理？不同的量綱如何處理？無約束非線性最小二乘模型無約束非線性最小二乘模型歸一化處理！歸一化處理！2442424231)()(tantan),( dyyxxxxyyyxEMiniiiii隨

8、著思考的深入，模型趨于合理隨著思考的深入，模型趨于合理2442424312)()(tantan ddyyxxxxyyMiniiiiix,y12 優(yōu)化問題的數(shù)學(xué)模型可行域目標函數(shù)，決策變量，fxnxRxxfz),(min 可行解可行解（只滿足（只滿足(2)）與）與 最優(yōu)解最優(yōu)解（滿足（滿足(1),(2)） 無約束優(yōu)化無約束優(yōu)化（只有（只有(1)）與）與 約束優(yōu)化約束優(yōu)化（(1),(2)）)2(, 2 , 1, 0)(. .)1 ()(minmixgtsxfzix 實際問題一般總有約束，何時可用無約束優(yōu)化處理？實際問題一般總有約束，何時可用無約束優(yōu)化處理？135.1 無約束優(yōu)化的基本方法無約束優(yōu)化

9、的基本方法)(minxfx給定一個函數(shù)給定一個函數(shù) f( (x),),尋找尋找 x* 使得使得 f( (x*)最小，即最小，即nTnRxxxx),(21其中其中無約束非線性規(guī)劃無約束非線性規(guī)劃 多元函數(shù)無條件極值問題多元函數(shù)無條件極值問題 極值問題的解（極值點），都是極值問題的解（極值點），都是局部最優(yōu)解局部最優(yōu)解 全局最優(yōu)解全局最優(yōu)解從局部最優(yōu)解的比較中得到從局部最優(yōu)解的比較中得到 以后所謂最優(yōu)解均指以后所謂最優(yōu)解均指局部最優(yōu)解局部最優(yōu)解145.1.1 預(yù)備知識預(yù)備知識一、梯度（一階導(dǎo)數(shù)）一、梯度（一階導(dǎo)數(shù)）)(xfnTnRxxxx),(21其中其中TxxTnnffxfxfxf),(),()

10、(11 梯度方向是使函數(shù)梯度方向是使函數(shù)f(x)在在x處增長最快的方向，處增長最快的方向，即函數(shù)變化率最大的方向；即函數(shù)變化率最大的方向； 梯度的模是函數(shù)梯度的模是函數(shù)f(x)沿梯度方向的變化率；沿梯度方向的變化率； 滿足梯度滿足梯度 的點稱為的點稱為駐點駐點。0)(xf15二、黑賽（二、黑賽（Hessian）矩陣（二階導(dǎo)數(shù)）矩陣（二階導(dǎo)數(shù)）nnjixxfxf22)( 當當f在點在點x處的所有二階偏導(dǎo)數(shù)連續(xù)時，有處的所有二階偏導(dǎo)數(shù)連續(xù)時，有), 1,(22njixxfxxfijji此時，此時， 是是n階對稱矩陣；階對稱矩陣；)(2xf 當當f(x)是二次函數(shù)：是二次函數(shù)：cxbAxxxfTT2

11、1)(AxfbAxxf)(,)(216三、多元函數(shù)的泰勒展開式三、多元函數(shù)的泰勒展開式1、一階展開式、一階展開式|)*(|*)(*)(*)()(xxoxxxfxfxfT2、二階展開式、二階展開式)|*(|*)*)(*)(21*)(*)(*)()(22xxoxxxfxxxxxfxfxfTT近似計算近似計算17四、正定、負定、半定矩陣四、正定、負定、半定矩陣設(shè)實對稱陣設(shè)實對稱陣Ann，各階主子式為，各階主子式為Ai，i=1,2,n正定矩陣：正定矩陣： Ai 0, i=1,2,n半正定矩陣：半正定矩陣：Ai 0, i=1,2,n負定矩陣：負定矩陣： Ai 0, i為偶數(shù)為偶數(shù)半負定矩陣：半負定矩陣：

12、 Ai 0, i為奇數(shù)為奇數(shù) Ai 0, i為偶數(shù)為偶數(shù)185.1.2 最優(yōu)解條件最優(yōu)解條件1、必要條件、必要條件設(shè)設(shè)f在點在點x處可微。若處可微。若x是最優(yōu)解，則是最優(yōu)解，則2、充分條件、充分條件設(shè)設(shè)f在點在點x處處Hessian矩陣存在。若矩陣存在。若則則x是最優(yōu)解。是最優(yōu)解。注：對于有實際意義的極值問題，我們通常只用注：對于有實際意義的極值問題，我們通常只用必必要條件要條件，理論上只需求解方程組，理論上只需求解方程組 即可。即可。0)(xf正定并且)(0)(2xfxf0)(xf195.1.3 數(shù)值迭代法的基本思路數(shù)值迭代法的基本思路在在nR中某一點，確定一個中某一點，確定一個搜索方向搜索

13、方向及沿該方向的搜索及沿該方向的搜索步長步長，得到使目標函數(shù)下降的新的點，得到使目標函數(shù)下降的新的點基本思想基本思想x*xf(x)f(x*)20迭代步驟迭代步驟Step 1 初始化：初始點初始化：初始點x0，終止條件等，終止條件等Step 2 迭代改進：搜索方向迭代改進：搜索方向pk，步長，步長 tkkkkkptxx1Step 3 若若 xk+1 滿足終止條件，則停止迭代；滿足終止條件，則停止迭代； 否則，令否則，令 k:=k+1 轉(zhuǎn)轉(zhuǎn) Step2 不同的算法在于不同的算法在于pk , tk選擇不同選擇不同 算法的關(guān)鍵在于尋找搜索方向算法的關(guān)鍵在于尋找搜索方向p pk k基本迭代格式基本迭代格

14、式21終止迭代條件終止迭代條件（1）根據(jù)相繼兩次迭代的）根據(jù)相繼兩次迭代的絕對誤差絕對誤差 |xk+1-xk| e1 |f(xk+1)-f(xk)| e2（2）根據(jù)相繼兩次迭代的）根據(jù)相繼兩次迭代的相對誤差相對誤差 |xk+1-xk| / |xk| e3 |f(xk+1)-f(xk)| / |f(xk)| e4（3）根據(jù)目標函數(shù)）根據(jù)目標函數(shù)梯度的模梯度的模足夠小足夠小5| )(|exfk其中其中e1, e2, e3, e4, e5為給定足夠小的正數(shù)為給定足夠小的正數(shù)22線性（一維）搜索線性（一維）搜索 (Line Search) 確定步長方法確定步長方法問題問題已知當前點已知當前點 xk 和

15、搜索方向和搜索方向 pk, 確定步長確定步長tk, 使得使得)(min)(minttpxftkkt優(yōu)化優(yōu)化算法算法近似黃金分割近似黃金分割(0.618)法、法、Fibonacci法、法、Newton法、法、2次或次或3次插值法次插值法等等 一維優(yōu)化問題一維優(yōu)化問題0)(kktkTkktdtdptpxfdtdf5.1.4 搜索步長的確定搜索步長的確定23一、一、0.618法（近似黃金分割法）法（近似黃金分割法）單谷函數(shù)與單谷區(qū)間單谷函數(shù)與單谷區(qū)間若存在一個若存在一個t*a,b，使得，使得f(t)在在 a,t* 上嚴格遞減上嚴格遞減, 且且在在 t*,b 上嚴格遞增上嚴格遞增f(t) a,b上的單

16、谷函數(shù)上的單谷函數(shù)a,b f(t)的單谷區(qū)間的單谷區(qū)間a t* b24性質(zhì)性質(zhì)在在a,b內(nèi)任取兩點內(nèi)任取兩點t1, t2 (t10收斂收斂, 0達到最大迭代次數(shù)達到最大迭代次數(shù), 0不收斂不收斂output 包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu)包含優(yōu)化結(jié)果信息的輸出結(jié)構(gòu) iterations 實際迭代次數(shù)實際迭代次數(shù) funcCount 實際函數(shù)調(diào)用次數(shù)實際函數(shù)調(diào)用次數(shù) algorithm 實際采用的算法實際采用的算法38例例5-1 求求f=2e-xsinx在在0,8上的最小值與最大值上的最小值與最大值39xmin = 3.9270 fmin = -0.0279xmax = 0.7854 fmax =

17、0.644840例例5-2 對邊長為對邊長為3m的正方形鐵板，在四個角剪去相的正方形鐵板，在四個角剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？槽的容積最大？解：設(shè)剪去的正方形的邊長為解：設(shè)剪去的正方形的邊長為x，則水槽的容積為，則水槽的容積為(3-2x)2x。建立無約束優(yōu)化模型為：。建立無約束優(yōu)化模型為：min y=- (3-2x)2x, x0,1.5fexm0502.m41xmax = 0.5000ymax = 2.0000剪掉正方形邊長為剪掉正方形邊長為0.5m時，水槽容積最大為時，水槽容積最大為2m342二、多元函數(shù)無約束優(yōu)

18、化問題二、多元函數(shù)無約束優(yōu)化問題nxRxxf),(min模型：fminunc, fminsearch輸輸入入項項x=fminunc(fun,x0)x=fminsearch(fun,x0)x=fminunc(fun,x0,options)x=fminsearch(fun,x0,options)fun 同同fminbnd用法用法x0 初始點初始點; x 最優(yōu)解最優(yōu)解中間輸入項缺省用中間輸入項缺省用 占位占位43控制參數(shù)控制參數(shù)options的設(shè)置的設(shè)置(2) MaxIter: : 允許進行迭代的最大次數(shù)允許進行迭代的最大次數(shù), ,取值取值為正整數(shù)；為正整數(shù)；options中常用的幾個參數(shù)的名稱、含

19、義、取值如下中常用的幾個參數(shù)的名稱、含義、取值如下: :(1) Display: : 顯示水平。取值為顯示水平。取值為off時時, ,不顯不顯示輸出示輸出; ; 取值為取值為iter時時, ,顯示每次迭代的信息顯示每次迭代的信息; ;取值為取值為final時時, ,顯示最終結(jié)果。默認值顯示最終結(jié)果。默認值為為final；(3) TolFun: : 函數(shù)值的控制精度。函數(shù)值的控制精度。44控制參數(shù)控制參數(shù)options可以通過函數(shù)可以通過函數(shù) optimset 創(chuàng)建或創(chuàng)建或修改。命令的格式如下：修改。命令的格式如下：(1) options = optimset (optimfun)創(chuàng)建一個含有所

20、有參數(shù)名創(chuàng)建一個含有所有參數(shù)名, ,并與優(yōu)化函數(shù)并與優(yōu)化函數(shù)optimfun有有相同默認值的選項結(jié)構(gòu)相同默認值的選項結(jié)構(gòu)options。（2）options = optimset (param1, value1, param2, value2,.)創(chuàng)建一個名稱為創(chuàng)建一個名稱為options的優(yōu)化選項參數(shù)的優(yōu)化選項參數(shù), ,其中指定的其中指定的參數(shù)具有指定值參數(shù)具有指定值, ,所有未指定的參數(shù)取默認值。所有未指定的參數(shù)取默認值。45例：例：opts = optimset(Display,iter,TolFun,1e-8) 該語句創(chuàng)建一個名稱為該語句創(chuàng)建一個名稱為opts的優(yōu)化選項結(jié)構(gòu)的優(yōu)化選項結(jié)

21、構(gòu), ,其中顯其中顯示參數(shù)設(shè)為示參數(shù)設(shè)為iter, TolFun參數(shù)設(shè)為參數(shù)設(shè)為1e-8。(3)options=optimset (oldops, param1, value1, param2, value2,.)創(chuàng)建名稱為創(chuàng)建名稱為oldops的參數(shù)選項的拷貝的參數(shù)選項的拷貝, ,用指定的參數(shù)值用指定的參數(shù)值修改修改oldops中相應(yīng)的參數(shù)。中相應(yīng)的參數(shù)。46 使用使用fminunc和和fminsearch可能會得到局部最優(yōu)解可能會得到局部最優(yōu)解 fminsearch是用單純形法尋優(yōu)；是用單純形法尋優(yōu)； fminunc的算法見以下幾點說明：的算法見以下幾點說明：（1）fminunc 提供了大

22、型和中型優(yōu)化算法，由提供了大型和中型優(yōu)化算法，由options中的參數(shù)中的參數(shù) LargeScale 控制：控制： LargeScale=on（默認值）默認值）, ,使用大型算法使用大型算法 LargeScale=off , ,使用中型算法使用中型算法算法選擇：算法選擇：optimset 中參數(shù)控制中參數(shù)控制47（2）fminunc 為中型優(yōu)化算法的為中型優(yōu)化算法的搜索方向搜索方向提供了以下提供了以下算法，由算法，由options中的參數(shù)中的參數(shù)HessUpdate控制：控制： HessUpdate=bfgs( (默認值默認值),),擬牛頓法的擬牛頓法的BFGS公式公式 HessUpdate=

23、dfp, 擬牛頓法的擬牛頓法的DFP公式公式 HessUpdate=steepdesc, 最速下降法最速下降法（3）fminunc為中型優(yōu)化算法的為中型優(yōu)化算法的步長一維搜索步長一維搜索提供了提供了兩種算法，由兩種算法，由options中參數(shù)中參數(shù)LineSearchType控制：控制： LineSearchType = quadcubic(默認值默認值) ) 混合的混合的2、3多項式插值；多項式插值； LineSearchType = cubicpoly，3次多項式插值次多項式插值48輸輸出出項項 x,fval= fminunc() x,fval= fminsearch() x,fval,e

24、xitflag,output = fminunc() x,fval,exitflag,output = fminsearch()Output iterations 實際迭代次數(shù)實際迭代次數(shù) funcCount 實際函數(shù)調(diào)用次數(shù)實際函數(shù)調(diào)用次數(shù) algorithm 實際采用的算法實際采用的算法 cgiterations 實際實際PCG迭代次數(shù)（大型優(yōu)化算法）迭代次數(shù)（大型優(yōu)化算法） stepsize 最后迭代步長（中型優(yōu)化模算法）最后迭代步長（中型優(yōu)化模算法） firstorderopt 一階最優(yōu)條件（梯度的模）一階最優(yōu)條件（梯度的模） message 收斂信息等收斂信息等49例例5-3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)fexm0503.m50 x = 0.5000 -1.0000f = 1.3028e-010例例5-4 Rosenbrock函數(shù)（香蕉函數(shù)）函數(shù)（香蕉函數(shù)）f(x1,x2) = 100(x2-x12)2 + (1-x1)2的精確極小點為的精確極小點為x*=(1,1)，極小值為，極小值為f*=0。試用不同算法（搜索方向和搜索步長）求數(shù)值最優(yōu)試用不同算法（搜索方向和搜索步長）求數(shù)值最優(yōu)解。初值選