最優(yōu)化理論第1次new

1、最優(yōu)化基本知識最優(yōu)化基本知識最優(yōu)化理論與方法最優(yōu)化理論與方法應(yīng)用性最強應(yīng)用性最強的數(shù)學(xué)分支的數(shù)學(xué)分支 -在眾多方案在眾多方案最優(yōu)方案最優(yōu)方案應(yīng)用領(lǐng)域應(yīng)用領(lǐng)域 -工程設(shè)計、資源分配、生產(chǎn)安排、原料配比、城建規(guī)劃、軍事領(lǐng)域、工程設(shè)計、資源分配、生產(chǎn)安排、原料配比、城建規(guī)劃、軍事領(lǐng)域、現(xiàn)代網(wǎng)絡(luò)等等現(xiàn)代網(wǎng)絡(luò)等等學(xué)科歷史學(xué)科歷史 1717世紀，世紀，NewtonNewton提出極值問題提出極值問題 LagrangeLagrange乘數(shù)法乘數(shù)法 18471847 CauchyCauchy最速下降法最速下降法 19391939 蘇聯(lián)數(shù)學(xué)家提出了線性規(guī)劃蘇聯(lián)數(shù)學(xué)家提出了線性規(guī)劃- -解決下料、運輸問題解決下料

2、、運輸問題 20 20世紀世紀4040年代，年代，DantzigDantzig提出單純型方法提出單純型方法獨立學(xué)科獨立學(xué)科例例1 1 生產(chǎn)計劃問題生產(chǎn)計劃問題某工廠用某工廠用 4種資源種資源 3種產(chǎn)品種產(chǎn)品jijcaij 利潤種資源產(chǎn)品需要第每單位jdji b i產(chǎn)品產(chǎn)量不超過，種資源總量不超過第如何生產(chǎn)利潤最大如何生產(chǎn)利潤最大?求解求解: x,x, 3321x種產(chǎn)品的產(chǎn)量分別為：設(shè) xxc 332211ccx目標函數(shù)（總利潤）：約束約束:3 , 2 , 1 03 , 2 , 1 x1,2,3,4i b xxji332211jxjdaaxajjiii使目標函數(shù)最大求解：, )x,x,(x x*

3、3*2*1*例例1 1 生產(chǎn)計劃問題生產(chǎn)計劃問題某工廠用某工廠用 4種資源種資源 3種產(chǎn)品種產(chǎn)品jijcaij 利潤種資源產(chǎn)品需要第每單位jdji b i產(chǎn)品產(chǎn)量不超過，種資源總量不超過第數(shù)學(xué)描述：數(shù)學(xué)描述：3 , 2 , 1 , 0 3 , 2 , 1 , x 1,2,3,4i , b xx s.t.maxji33221131jxjdaaxaxcjjiiijjj )x,x,(x x*3*2*1*例例2 2 結(jié)構(gòu)設(shè)計問題結(jié)構(gòu)設(shè)計問題兩個構(gòu)件組成的對稱桁架兩個構(gòu)件組成的對稱桁架HxEy上限容許應(yīng)力：彈性模量：材料比重：2求解求解:2/12221)(Tx2 xLG目標函數(shù)（總重量）：約束約束1:H

4、x 2使桁架重量最?。胯旒芨叨却_定鋼管直徑, 21xx2P2xL2YYY-Y剖面1xT約束約束2:2121222122122221)()(),(xTxxLPTxxxLPSFxx例例2 2 結(jié)構(gòu)設(shè)計問題結(jié)構(gòu)設(shè)計問題2P2xL2YYY-Y剖面1xT約束約束2:yxTxxLP2121222)(約束約束3:)(8)(2222212xLTxEl鋼管不彎曲，即壓應(yīng)力不鋼管不彎曲，即壓應(yīng)力不超過臨界應(yīng)力超過臨界應(yīng)力)(8)()(22222122121222xLTxExTxxLP使重量最輕求解：, )x,(x x*2*1*數(shù)學(xué)描述：數(shù)學(xué)描述：2/12221)(Tx2in xLGm,. .2Hxts,)(212

5、1222yxTxxLP,)(8)()(22222122121222xLTxExTxxLP0,21xx2.1 2.1 問題描述問題描述 )(minxfnRxIixCixCTSii0)(0)(.00. .) 1()2min(212212221xxxxtsxx例例1x12x1x1C2C)(xf*x2221) 1()2()(xxxf2.2 2.2 連續(xù)優(yōu)化與離散優(yōu)化連續(xù)優(yōu)化與離散優(yōu)化 )(minxfnRxIixCixCtsii0)(0)(. .a 有約束優(yōu)化有約束優(yōu)化離散優(yōu)化：有限集合連續(xù)優(yōu)化：無限集合2.3 2.3 有約束優(yōu)化與無約束優(yōu)化有約束優(yōu)化與無約束優(yōu)化 根據(jù)目標函數(shù)及約束方程根據(jù)目標函數(shù)及約

6、束方程:*線性、非線性、凸優(yōu)化線性、非線性、凸優(yōu)化*變量個數(shù)：變量個數(shù)：Large or Small*方程光滑性：可微、不可微方程光滑性：可微、不可微求解方法求解方法:二次規(guī)劃、罰函數(shù)、置信域等二次規(guī)劃、罰函數(shù)、置信域等)(minxfnRxnRxts. .b 無約束優(yōu)化無約束優(yōu)化求解方法求解方法:一維搜索、牛頓法、共軛梯度法等一維搜索、牛頓法、共軛梯度法等2.4 2.4 全局優(yōu)化與局部優(yōu)化全局優(yōu)化與局部優(yōu)化 難題難題上的全局最小點在為稱有對每個鄰域的，局部優(yōu)化：上的全局最小點在為稱有對每個，全局優(yōu)化：S)()()(),(|),(,0S)(S)()()(,S)(*xfxxfxfxNSxxxxxN

7、SxxfxfxxfxfSxSxxf非線性問題的非線性問題的解一般為局部解一般為局部解解2.5 2.5 隨機優(yōu)化與確定性優(yōu)化隨機優(yōu)化與確定性優(yōu)化 多出現(xiàn)于經(jīng)濟、金融行業(yè)，用統(tǒng)計及概率論預(yù)測多出現(xiàn)于經(jīng)濟、金融行業(yè)，用統(tǒng)計及概率論預(yù)測確定確定性優(yōu)化：模型的值隨機優(yōu)化：模型不確定2.6 2.6 優(yōu)化算法優(yōu)化算法 迭代迭代-要求具有：魯棒性，效率，精度要求具有：魯棒性，效率，精度實值函數(shù)：實值函數(shù)：3.1 3.1 向量范數(shù)和矩陣范數(shù)向量范數(shù)和矩陣范數(shù) 為向量范數(shù)則當且僅當nnnRyxyxyxRxRxxxxRxx,)3(,)2(00;0) 1 (定義：定義： 向量范數(shù)向量范數(shù)則則x的常用范數(shù)有：的常用范數(shù)

8、有：pnjpjpjjnjjnjjxxxxxxxx112112211)(max)(nTnRxxxx),.,(21設(shè)滿足：RRn :范數(shù)LLL,21A為為mXn矩陣矩陣3.1 3.1 向量范數(shù)和矩陣范數(shù)向量范數(shù)和矩陣范數(shù) DAADBABAAAxAAx)3(,)3(,)2(,) 1 (定義：定義： 矩陣范數(shù)矩陣范數(shù)則則A的常用范數(shù)有：的常用范數(shù)有：njijiTmiijjaxAAAaA121211max)(maxAxARRxnm1max: :向量范數(shù)向量范數(shù)，范數(shù)AAA,21矩陣范數(shù)性質(zhì)矩陣范數(shù)性質(zhì)3.2 3.2 序列的極限序列的極限 定義定義1 *k*k*lim,x, , 0,xxxxxKkKRxR

9、xkknnk記作：收斂到稱序列有時，使得存在任給中的向量序列，是定義定義2 的一個聚點是則稱，使得在一個子序列中的向量序列，如果存是kKKKnkxxxxxRxjjjlim,定義定義3 序列為稱序列有時，使得存在中的向量序列，任給是CauchyxxKlmKRxlnkkmx, , 0定理定理1 的聚點必為極限點序列，則中的是jnjxCauchyRx緊集：有界的閉集鄰域的，使得存在開集：均屬于中每個收斂序列的極限中的集合，為閉集：SxNxSxSSRSn),(, ;3.3 3.3 梯度、梯度、HesseHesse矩陣、矩陣、TaylorTaylor展開展開 非空實函數(shù)nRSxf),(（1）梯度：）梯度

10、：Tnxxfxxfxxfxf)(.)(,)()(21)()(,.1,)()(,.1, 221SCfxxxfnjiSxSCfxxfnjSxSfjij存在且連續(xù)，記作二次連續(xù)可微：存在且連續(xù)，記作連續(xù)可微：的每一點上連續(xù)在連續(xù)：（2）Hesse矩陣：矩陣：nnnnnxxfxxxfxxfxxxfxxxfxxfxxxfxxxfxxfxf22222222222222122121222)(.)(,)(.)(.)(,)()(.)(,)()(3.3 3.3 梯度、梯度、HesseHesse矩陣、矩陣、TaylorTaylor展開展開 SxSCfRSxfn*2),(,),(非空實函數(shù)（3）Taylor展開：展開

11、：)()()(21)()()()(2*2*xxxxxfxxxxxfxfxfT4.1 4.1 凸集凸集 為凸集則稱：有設(shè)SSxxSxxifRSn1 , 0,)1 (, ,2121凸集定義：凸集定義：1x2x1x2x的凸組合稱為2121,)1 (xxSxx是定點為非零向量，其中，為凸集，驗證：例000, 1xddxxL4.1 4.1 凸集凸集 為凸集為凸集為凸集為凸集則有：為實數(shù)，設(shè)2121211121)4() 3()2() 1 ( ,SSSSSSSxxSRSSn凸集性質(zhì)：凸集性質(zhì)：為凸錐為凸集，則稱若為錐，則有取任何非負數(shù)時，當中每一點，若設(shè)集合CCCCxxCRCn,凸錐定義：凸錐定義：bAxx

12、多面集有限個半空間的交稱為多面集定義：多面集定義：0, 0, 1, 42212121xxxxxxxS例：1x2x4.1 4.1 凸集凸集 中的極點是稱必有為非空凸集設(shè)SxxxxSxxxxxifSxS, ,)1 , 0( ,)1 ( ,212121極點定義：極點定義：的極方向為線性組合，則的正的不能表示成兩個方向的方向若的方向。為則都有中每一個為非零向量，對于為閉凸集，SddddSSdSdxxSdS21,0 極方向定義：極方向定義：1x2x3x7x5x4x6x4.2 4.2 凸函數(shù)凸函數(shù) 嚴格凸函數(shù)凸函數(shù)為非空凸集設(shè))()1 ()()1 ()()1 ()()1 () 1 , 0(,2121212

13、121xfxfxxfxfxfxxfSxxS定義：定義：1x2xx21)1 (xxx1x2xx21)1 (xxx1x2xx21)1 (xxx凸函數(shù)凸函數(shù)凹函數(shù)凹函數(shù)非凸凹函數(shù)非凸凹函數(shù)4.2 4.2 凸函數(shù)凸函數(shù) 為凸函數(shù)為凸函數(shù)，定理miiifffff121, 1凸函數(shù)定理凸函數(shù)定理SxxxxxfxffffRSTn2112112,),()()()(x ,2為凸函數(shù)可微定理矩陣半正定的每一點上在為凸函數(shù)二次可微定理Hesse,3SfffRSn是否是凸函數(shù)函數(shù)例題122),(121222121xxxxxxxf5.1 5.1 無約束問題的最優(yōu)性條件無約束問題的最優(yōu)性條件 nRxxf),(min定義定

14、義1的嚴格局部極小點為則稱的和如果對于所有的局部極小點為則稱的和對于所有fxxffxxxRxfxxffxxxRxnn*),()(x),()(x, 0定義定義2的總體極小點為則稱對于所有fxxffRxn*),()(x 一般情況下一般情況下,可行解是局部極小點可行解是局部極小點,問題是凸性問題時問題是凸性問題時,局部極小點等于總體極小點局部極小點等于總體極小點5.1 5.1 無約束問題的最優(yōu)性條件無約束問題的最優(yōu)性條件 ）（二階導(dǎo)數(shù)存在連續(xù)，而且一階導(dǎo)數(shù)、)()(),()(2xfxGxfxgf) 1 , 0(,)(21)()()()()()() 1 , 0(,)()()(2102tptpxfppx

15、fxfpxfpdttpxfxfpxftptpxfxfpxfTTT二階連續(xù)則有下式成立則有下式成立:5.1 5.1 無約束問題的最優(yōu)性條件無約束問題的最優(yōu)性條件 0)(:*1xfDxRRDfn上局部極小點，則是在開集上連續(xù)可微，若設(shè)定理定理1（一階必要條件）（一階必要條件）:)(0)(0)(:*2*1半正定，則上局部極小點，是，若在開集上二階連續(xù)可微設(shè)xfxfDxRRDfn定理定理2（二階必要條件）（二階必要條件）:)(0)(0)(:*2*1正定，的充分條件是：為一嚴格局部極小點，則在開集上二階連續(xù)可微設(shè)xfxfxRRDfn定理定理3（二階充分條件）（二階充分條件）:0)(,:*11xfxCfR

16、RDfn的充要條件是：是總體極小點則是凸函數(shù)，且設(shè)定理定理4:5.2 5.2 最優(yōu)化問題的結(jié)構(gòu)最優(yōu)化問題的結(jié)構(gòu) )(*0在可行域內(nèi)xxRxknkkkkkkkpxxkpkx1 則為步長次搜索方向，為第次迭代點，為第設(shè)0)(:kTkkkpxfxfp點的下降方向，即在但一定是）頓、共軛梯度方向，（最速下降、牛如果滿足條件則停止重復(fù)令在某種意義下下降使確定步長方向處的下降方向作為搜索在依一定規(guī)則，構(gòu)造確定方向4-2,)4(,) 3(,)2() 1 (10kkkkkkkpxxfxfpx最優(yōu)化問題的基本流程：最優(yōu)化問題的基本流程：）插值步長，（不同方法，,618. 0:Fibonaccik5.3 5.3

17、兩種搜索策略：線性搜索與置信域法兩種搜索策略：線性搜索與置信域法 kkkpx)(min 0kkkkkkpxfp，再用以下公式求解先確定5.3.1 線性搜索線性搜索位于信賴域內(nèi)方向先確定信賴域，再求解pkkkpkxpxmp),(min 5.3.2 信賴域方法信賴域方法kxkpfmk新求解下降，減小信賴域，重如果解無法使f也可以為橢球，盒型域信賴域為球，一般情況，, 0,2ppBpfpfpxmkTkTkkk21)(標量標量 向量向量 矩陣（矩陣（Hesse或其它）或其它）5.3 5.3 兩種搜索策略：線性搜索與置信域法兩種搜索策略：線性搜索與置信域法 kkkpp再步長（信賴域半徑），信賴域法：先確

18、定最大再線性搜索：先,5.3.3 二者區(qū)別二者區(qū)別下降最快方向選擇kf-), 0(,)()()(,2221tptpxfpfpxfpxfpfkTkTkk步長方向kTkfppxf 和的變化點沿方向在5.4 5.4 線性搜索中的搜索方向線性搜索中的搜索方向 (1) 最速下降方向最速下降方向:問題求解問題求解5.4 5.4 線性搜索中的搜索方向線性搜索中的搜索方向 (1) 最速下降方向最速下降方向:在單位方向在單位方向p,求解下面問題可以獲得最快下降速度求解下面問題可以獲得最快下降速度kkkkTkTpffpffpfpptsfp/ -1)cos()cos( )cos(1. . min其解為時最小，即當*

19、xkxpkf缺點缺點: 有時收斂速度很慢有時收斂速度很慢,求解困難求解困難!5.4 5.4 線性搜索中的搜索方向線性搜索中的搜索方向 (2) 牛頓方向牛頓方向:)()(221pmfppfpfpxfkdefTkTkk缺點缺點:kxkpkfkfkkkNkffpppm120)(其顯示表達式為：為牛頓方向，求得求導(dǎo)并因此需要修正不存在，必須正定，否則-122kkff5.4 5.4 線性搜索中的搜索方向線性搜索中的搜索方向 (3) 擬牛頓方向擬牛頓方向:10222102)()()()( )()()(pdtxftpxfpxfxfpdttpxfxfpxf問題推導(dǎo)問題推導(dǎo):矩陣種方法，不求解在擬牛頓法中，構(gòu)造一，并求逆牛頓法中需要求解Hesse2kf加、減項加、減項kkkxxpxx1,設(shè)則有：則有：)(0)(1121kkkkkkkxxxxfffkkkkkffxxf112)(kSky則有：則有：kkkySf25.4 5.4 線性搜索中的搜索方向線性搜索中的搜索方向 (3) 擬牛頓方向擬牛頓方向:人為給定保持低的秩，使得一般通過限制則有矩陣來代替矩陣的近似矩陣選擇01, HesseHesseBBBBySBBkkkkkkkkkkySf2kTkTkkkkTkkTkkkkKkTkkKTkkkkkkkKSyyySBSBSSBBBBFGSSSBySBy