1、13. 優化優化設計的理論與數學基礎設計的理論與數學基礎2022-4-291 現代設計方法現代設計方法優化設計優化設計1 1）多元函數的）多元函數的TaylorTaylor展開式展開式2 2）二次齊次函數）二次齊次函數3 3）關于優化方法中搜索方向的理論基礎）關于優化方法中搜索方向的理論基礎4 4）凸集與凸函數）凸集與凸函數5 5）最優化問題的極值存在條件）最優化問題的極值存在條件 現代設計方法現代設計方法優化設計優化設計函數函數的的Taylor Taylor 展開式展開式nnkknkkkkkRxxxfnxxxfxxxfxfxf)(!1.)(21)()()()()()(2)()(/)()(/)

2、()(2)(/)(/)(,)(21)()()(kkkkxxxxxfxxfxfxf式中* * 在實際計算中在實際計算中, ,常取前三項常取前三項( (二次函數二次函數) )來近似原函數來近似原函數: :1)()1()()!1(1nknnxxfnR)()(之間與在點xxk式中式中,一一. .一元函數的一元函數的Taylor Taylor 展開式展開式 現代設計方法現代設計方法優化設計優化設計二二. .多元函數的多元函數的TaylorTaylor展開式展開式TnkkkkxXFxXFxXFXF)(.)()()()(2)(1)()(TnkxxxXXX.21)(令Tknnkkxxxxxx.2211jini

3、ninjjikiikkxxxxXFxxXFXFXF 111)(2)()()(21)()()(1)2)(22)(21)(22)(222)(212)(21)(221)(221)(2)(2)()(.)()(.)(.)()()(.)()()()(nknknknkkknkkkKKxXFxxXFxxXFxxXFxXFxxXFxxXFxxXFxXFXFXH(2)(3)XXHXXXFXFXFkTTkk)(21)()()()()()(梯度梯度海賽海賽(Hessian)(Hessian)矩陣矩陣對稱矩陣對稱矩陣 現代設計方法現代設計方法優化設計優化設計二二次齊次函數次齊次函數njijiijxxaXF1,)(nnn

4、nnnnnxxxaaaaaaaaaxxx.2121222211121121AXXT2221212)(cxxbxaxXF2121xxcbbaxx例：例：22212121cxxbxxbxax系數矩陣系數矩陣;, 0)(, 0) 1為正定矩陣則恒有對于根據線性代數AXFX.)(,)2稱為正定二次型則為正定若XFA 現代設計方法現代設計方法優化設計優化設計* * 矩陣矩陣A A為正定的充要條件為正定的充要條件-A A的各階主子式均大于零的各階主子式均大于零。0003332312322211312112221121111aaaaaaaaaaaaaa333231232221131211aaaaaaaaaA

5、如如 為正定，則必有為正定，則必有： 現代設計方法現代設計方法優化設計優化設計關于優化方法中搜索方向的理論基礎關于優化方法中搜索方向的理論基礎1.1.方向導數方向導數一一. .函數的最速下降方向函數的最速下降方向2.2.最速下降方向最速下降方向二二. .共軛方向共軛方向1.1.正定二次函數正定二次函數2.2.共軛方向的基本概念共軛方向的基本概念3.3.構成共軛方向的方法構成共軛方向的方法 現代設計方法現代設計方法優化設計優化設計XXXFXFSXFkkk)()()()()(lim)()(kXXSX)(kXS1. 定義定義-函數沿指定方向函數沿指定方向 的平均變化率的極限的平均變化率的極限。一一)

6、 ) 方向導數方向導數一一. .函數的最速下降方向函數的最速下降方向 現代設計方法現代設計方法優化設計優化設計2.2.方向余弦方向余弦 niXXxkii,.,2 , 1,cos)(121x2xoX)(kX1x2x1coscos:122122)(222)(212)(2221即XXxXXxXXxxkkk 現代設計方法現代設計方法優化設計優化設計3.3.方向導數的計算方向導數的計算nnkkkkxxXFxxXFxxXFXFXFF)(.)()()()()(22)(11)()()()()1212()()()coscos.coskkknnF XF XF XxxxXXXFXFSXFkkk)()()()()(l

7、im)()(kXX 現代設計方法現代設計方法優化設計優化設計二）最速下降方向二）最速下降方向TnKKKKxXFxXFxXFXF)(.)()()()(2)(1)()(因為因為SXFSXFTkk)()()()(于是于是單位矢量單位矢量TnScos.coscos21令令),cos()()(SFSXFk),cos(SFF 現代設計方法現代設計方法優化設計優化設計從上式可得出如下結論：從上式可得出如下結論：FSF最優點最優點* * 最速下降只是局部性質最速下降只是局部性質. .4 4）在與梯度垂直的方向（等值線的切）在與梯度垂直的方向（等值線的切 線方向）上，函數的變化率為零。線方向）上，函數的變化率為

8、零。2 2）梯度的模就是沿梯度方向的方向導數，）梯度的模就是沿梯度方向的方向導數，1 1）方向導數是梯度在指定方向上的投影；）方向導數是梯度在指定方向上的投影；3 3）最速下降方向為等值線（面）的）最速下降方向為等值線（面）的 法線方向法線方向；負梯度方向是函數的最速下降方向；負梯度方向是函數的最速下降方向；SXFk)()(),cos(SFF 也是最大的也是最大的 方向導數方向導數, , 現代設計方法現代設計方法優化設計優化設計二二. .共軛方向共軛方向CXBAXXXFTT21)(常數階正定對稱矩陣CxxxXbbbBnATnTn.2121* *當當n=2n=2時，時，fexdxcxxbxaxX

9、F21222121)(fxxedxxcbbaxx212121222112112222()22axbxdxabdF XAXBbxcxexbce C1 1）矩陣表示）矩陣表示一）正定二次函數一）正定二次函數也適于多元函數也適于多元函數AcbbaXF22)(2TB 現代設計方法現代設計方法優化設計優化設計2)2)正定二元二次函數的特點正定二元二次函數的特點fcxaxF2221. 0,caca且必同號故因是橢圓方程且有極小) F=f F=f 時有極小時有極小. .此時橢圓縮為一點此時橢圓縮為一點, ,即橢圓中心即橢圓中心.) F F的值只影響橢圓的大小的值只影響橢圓的大小, ,不影響其中心位置不影響其

10、中心位置-同心同心; 橢圓方程經坐標軸平移和轉動后可去掉一次項和交橢圓方程經坐標軸平移和轉動后可去掉一次項和交叉項叉項, , 故寫成下述形式不失一般性故寫成下述形式不失一般性: :. 04, 02acba因函數為正定因函數為正定，故故A A為正定為正定，即即： 由于由于判別式判別式00，無論無論F(X)F(X)取何值取何值, ,所得方程均為所得方程均為橢圓方程橢圓方程. .證：證：（1 1）正定二元二次函數的等值線是一族同心橢圓，）正定二元二次函數的等值線是一族同心橢圓，其中心坐標就是該函數的極小點。其中心坐標就是該函數的極小點。AcbbaXF22)(21)()(222221cfFxafFx

11、現代設計方法現代設計方法優化設計優化設計（2 2）過同心橢圓族的中心作任意直線與橢圓族中任意兩）過同心橢圓族的中心作任意直線與橢圓族中任意兩橢圓相交，再過兩交點所作相應橢圓的切線必相互平行。橢圓相交，再過兩交點所作相應橢圓的切線必相互平行。fcxaxF222121121221022cxaxdxdxdxdxcxaxckacxaxdxdx2112為常量為常量, ,說明該直線上各橢圓的斜率均相等說明該直線上各橢圓的斜率均相等. .)2() 1 (,XX)2() 1 (,XX逆命題逆命題: 設兩平行線與同心橢圓族中兩橢圓分別相切于設兩平行線與同心橢圓族中兩橢圓分別相切于 點點, ,則過則過 的直線必通

12、過橢圓族的中心的直線必通過橢圓族的中心.12kxx 設過中心的直線為設過中心的直線為 , 代入上式得代入上式得:1x就上式對就上式對 求導求導:證證: :) 1 (X) 1 (X)2(X 現代設計方法現代設計方法優化設計優化設計二）共軛方向的基本概念二）共軛方向的基本概念0324632422214* 幾何意義幾何意義: 經過線性變換經過線性變換A A后成了與后成了與 正交的向量正交的向量.1S2S例：例：021ASST21,SS21SS 和 設設A A為為n nn n階正定對稱矩陣階正定對稱矩陣， 是兩個是兩個n n維維向量向量，若存在若存在則稱則稱 對對A A共軛共軛。1)1)定義定義 現代

13、設計方法現代設計方法優化設計優化設計2)2)共軛方向的性質共軛方向的性質* * 這種性質稱為這種性質稱為有限步收斂性有限步收斂性（亦稱（亦稱二次收斂性二次收斂性）（2 2）從任意選定的初始點出發，只要依次沿從任意選定的初始點出發，只要依次沿n n個共軛方向進行一維搜索，一輪后便可達到個共軛方向進行一維搜索，一輪后便可達到n n元正定二次函數的極小點。元正定二次函數的極小點。( (證明見證明見席少霖席少霖: :最優化方法最優化方法，P P9797）nSSS,.,21（1 1）若矢量系若矢量系 彼此對正定對稱彼此對正定對稱矩陣矩陣A A共軛共軛，則它們組成線性無關的矢量系則它們組成線性無關的矢量系

14、； 現代設計方法現代設計方法優化設計優化設計三）構成共軛方向的方法三）構成共軛方向的方法21,ll1S)2() 1 (,XX) 1 () 2(2XXS1S 設設 為平行于為平行于 的兩條直線的兩條直線，則過這兩直線則過這兩直線上正定上正定 n n元二次目標函數的極小點元二次目標函數的極小點 的的向量向量 和和 對對HessionHession矩陣矩陣A A共軛共軛。 1S) 1 (X)2(X2S1l2l 現代設計方法現代設計方法優化設計優化設計證明證明： CXBAXXXFTT21)(二次函數二次函數BAXXF)(其梯度為其梯度為0)(0)()2(1)1(1XFSXFSTT因因 分別為兩直線上的

15、極小點分別為兩直線上的極小點，故有故有)2()1(, XX0)()()1()2(1XFXFST將上述兩式相減將上述兩式相減0)()1()2(1 XXAST0)1()2(1BAXBAXST021ASST1S)(XF 現代設計方法現代設計方法優化設計優化設計例例：對于目標函數對于目標函數 ，給給定定 ，試求出與試求出與 共軛的方向共軛的方向 ，并求并求出目標函數的極小點出目標函數的極小點。2122212)(xxxxXFTS 1011S2S 現代設計方法現代設計方法優化設計優化設計凸集凸集與凸函數與凸函數X XX X2 2X X1 1llllXXXX122凸集凸集非凸集非凸集凹集凹集* *若若X X

16、是是X X1 1和和X X2 2連線上的點，則有連線上的點，則有一一. .凸集凸集- - 若任意兩點若任意兩點 ，對于，對于 ， 恒有恒有 ， 則則 D D 為凸集為凸集。DXXX21)1 (DXX21,:10整理后即得整理后即得21X)1 (XX 現代設計方法現代設計方法優化設計優化設計y)(xfx2xx1xof1f2flxxlxx212,二二. .凸函數凸函數10:)()1 ()()1 (2121XfXfXXf 設設f(X)f(X)為定義在為定義在 R Rn n 內一個凸集內一個凸集D D上的函數上的函數，若對于若對于 及及D D上的任意兩點上的任意兩點X X1 1,X,X2 2, ,恒恒

17、有有 則則f(X)f(X)為定義在為定義在D D上的一個凸函數上的一個凸函數。1.1.定義定義llffyf12221)1 (ffy 現代設計方法現代設計方法優化設計優化設計2.2.凸函數的基本性質凸函數的基本性質)()1 ()()1 (2121XFXFXXF)()1 ()()1 (2121XFXFXXF兩邊乘上兩邊乘上 證證: : 由定義由定義 （1）設設 為定義在凸集為定義在凸集D D上的凸函數上的凸函數， 為任意為任意正實數正實數, ,則則 也是定義在也是定義在 D D上的凸函數上的凸函數。)(XF)(XF 現代設計方法現代設計方法優化設計優化設計)()1 ()()1 (2111211XF

18、XFXXF)()1 ()()1 (2212212XFXFXXF證證: : 由定義由定義（2）設設 、 均為定義在凸集均為定義在凸集D D上的凸函數上的凸函數，則則 + + 也是定義在也是定義在 D D上的凸函數上的凸函數。)(1XF)(2XF)(1XF)(2XF（3）設設 、 均為定義在凸集均為定義在凸集D D上的凸函數上的凸函數， 為任意正實數為任意正實數，則則 也是定義在也是定義在D D上的凸函數上的凸函數。)(2XF)(1XF)()(2211XFXF21, 兩式相加兩式相加, ,整理后可得證整理后可得證. 現代設計方法現代設計方法優化設計優化設計3.3.凸函數的判定凸函數的判定 )(mi

19、n,.,2,1,0)(piXgiXDXFnRDX 若若D D為凸集，為凸集，F(x)F(x)為定義在為定義在D D上的凸函數，上的凸函數，則此規劃為凸規劃。則此規劃為凸規劃。 對于數學規劃問題：對于數學規劃問題：4.4.凸規劃凸規劃 凸規劃的最凸規劃的最優點是唯一的優點是唯一的. .DX為凸函數的充要條件是對于任意的為凸函數的充要條件是對于任意的)X(F. 0)(2XF(D(D為凸集為凸集),), 現代設計方法現代設計方法優化設計優化設計2122212141060)(判斷函數xxxxxxXF.是否為凸函數 現代設計方法現代設計方法優化設計優化設計最優化最優化問題的極值存在條件問題的極值存在條件

20、0)(0)(/xfxf0)(0)(2XFXFxxfo梯度為零向量梯度為零向量海賽矩陣正定海賽矩陣正定2. 多元函數具有極小值的充要條件多元函數具有極小值的充要條件1. 一元函數具有極小值的充要條件一元函數具有極小值的充要條件一一. .無約束問題的極值存在條件無約束問題的極值存在條件 現代設計方法現代設計方法優化設計優化設計充分條件的簡易證明：充分條件的簡易證明：XXHXXXFXFXFTT)(21)()()(由線性代數可知由線性代數可知0)(XH0)(XF因因0)(21)()(XXHXXFXFT故故二次型正定二次型正定 現代設計方法現代設計方法優化設計優化設計例例：求求 的極小點的極小點。4445)(1222121xxxxxXF 現代設計方法現代設計方法優化設計優化設計qXhXFXL1)()(),(（LagrangeLagrange函數）函數） LagrangeLagrange乘子乘子0)()(1qXhXF* 必須有解必須有解可表示為各約束函數梯度的線性組合?？杀硎緸楦骷s束函數梯度的線性組合。)(XFFhX0hF1h2hX01h02h1