第二章優(yōu)化設(shè)計的理論與數(shù)學(xué)基礎(chǔ)

1、12.1 2.1 目標(biāo)函數(shù)的泰勒目標(biāo)函數(shù)的泰勒(Taylor)(Taylor)展開式展開式 2.2 2.2 目標(biāo)函數(shù)的等值線目標(biāo)函數(shù)的等值線( (面面) ) 2.3 2.3 無約束目標(biāo)函數(shù)極值點(diǎn)存在條件無約束目標(biāo)函數(shù)極值點(diǎn)存在條件2.4 2.4 凸集與凸函數(shù)凸集與凸函數(shù) 2.5 2.5 約束極值點(diǎn)存在條件約束極值點(diǎn)存在條件2 .6 優(yōu)化計算的數(shù)值解法及收斂條件優(yōu)化計算的數(shù)值解法及收斂條件2二元二次函數(shù)二元二次函數(shù) 2212112212()(,)abF XF x xxxcdxxxexf令令: : 12,xXx22,abAbc,dBe Cf則則: : 1()2TTF XXXCXAB梯度梯度: :(

2、)BF XXA11221222()22xaxbxdabdF XAXBxbxcxebce 驗(yàn)證驗(yàn)證: :二次函數(shù)的矩陣表示方法二次函數(shù)的矩陣表示方法(補(bǔ)充補(bǔ)充)其中：其中：: :1121222()2FxaxbxdF XbxcxeFx3二次函數(shù)的矩陣表示方法二次函數(shù)的矩陣表示方法(補(bǔ)充補(bǔ)充)例題例題:將將F(X)=x12-2-2x1x2+ +x22-8-8x1+9+9x2+10+10寫成矩陣表示式，并求其寫成矩陣表示式，并求其梯度。梯度。解解: :2222A89B10C 1()2TTF XX AXB XC1112222218910222xxxxxx 112212228228()229229xxxF

3、 XAXBxxx驗(yàn)證驗(yàn)證: :121122228()229xxxxFF XxxF42.1 2.1 目標(biāo)函數(shù)的泰勒目標(biāo)函數(shù)的泰勒(Taylor)(Taylor)展開式展開式 工程實(shí)際中的優(yōu)化設(shè)計問題，常常是多維且非線性函數(shù)形式，一般較為復(fù)雜。工程實(shí)際中的優(yōu)化設(shè)計問題，常常是多維且非線性函數(shù)形式，一般較為復(fù)雜。為便于研究函數(shù)極值問題，需用為便于研究函數(shù)極值問題，需用簡單函數(shù)簡單函數(shù)作作局部逼近局部逼近，通常采用泰勒展開，通常采用泰勒展開式式作為函數(shù)在某點(diǎn)附近的近似表達(dá)式，以近似于原函數(shù)。作為函數(shù)在某點(diǎn)附近的近似表達(dá)式，以近似于原函數(shù)。一元函數(shù)一元函數(shù)f( (x) )在在x(k)點(diǎn)的泰勒展開式：點(diǎn)的

4、泰勒展開式：二元函數(shù)二元函數(shù)F( (X)= F( (x1,x2)=在在X(k)=x1(k) x2(k) T點(diǎn)的泰勒展開式為：點(diǎn)的泰勒展開式為：5( )( )( )112222( )( )( )1 111 2122 22()()()()1()2()()2kkkxxkkkx xx xx xF XF XFXxFXxFXxFXxxFXx 2211221 111 2122 221()22kxxx xx xx xF XFFxFxFxFxxFx 矩陣矩陣形式形式111 11 21212222 12 21()2x xx xkxxx xx xxxFFF XFFFxxxxFF1()2TTkkF XFFXX HX

5、()1 11 22 12 2()Kx xx xx xx xFFH XFF海賽矩陣海賽矩陣 即即: :其中其中: :6多元函數(shù)多元函數(shù)F( (X)在在X(k)=x1(k) x2(k) xn(k) T點(diǎn)的泰勒展開式為：點(diǎn)的泰勒展開式為：1 11 21( )2 12 2212.().x xx xx xnkx xx xx xnkxnxxnxxnxnFFFFFFHH XFFF(二階偏導(dǎo)數(shù)矩陣二階偏導(dǎo)數(shù)矩陣)n nn n階的對稱方陣階的對稱方陣 xixjxjxiFF1()2TTkkF XFFXX HX 1212(),TnnFxFxFFFF XxxxFx同上：同上：一階偏導(dǎo)數(shù)矩陣一階偏導(dǎo)數(shù)矩陣稱為函數(shù)在稱為

6、函數(shù)在K K點(diǎn)的梯度：點(diǎn)的梯度：但其中：但其中：12,TnXxxx 7 稱為函數(shù)在稱為函數(shù)在 點(diǎn)的梯度點(diǎn)的梯度.梯度是一個向量梯度是一個向量,其方向是函其方向是函數(shù)在數(shù)在 點(diǎn)處數(shù)值增長最快的點(diǎn)處數(shù)值增長最快的方向方向.()()()()12()()()(),TKKKKnF XF XF XF Xxxx)()(KXF)(KX)(KX82.2 目標(biāo)函數(shù)的等值線目標(biāo)函數(shù)的等值線(面面) 910v函數(shù)的極值與極值點(diǎn)函數(shù)的極值與極值點(diǎn)2.3 2.3 無約束目標(biāo)函數(shù)極值點(diǎn)存在條件無約束目標(biāo)函數(shù)極值點(diǎn)存在條件11v極值點(diǎn)存在條件極值點(diǎn)存在條件一元函數(shù)的情況一元函數(shù)的情況極值點(diǎn)存在的必要條件極值點(diǎn)存在的必要條件

7、的點(diǎn)稱為駐點(diǎn)，極值點(diǎn)必為駐點(diǎn)，但駐的點(diǎn)稱為駐點(diǎn)，極值點(diǎn)必為駐點(diǎn)，但駐點(diǎn)不一定為極值點(diǎn)。點(diǎn)不一定為極值點(diǎn)。極值點(diǎn)存在的充分條件極值點(diǎn)存在的充分條件若在駐點(diǎn)附近若在駐點(diǎn)附近 0*)(xF0*)(xF點(diǎn)為極大點(diǎn)則 *0)(* xxF點(diǎn)為極小點(diǎn)則 *0)(* xxF12( (一一) )極值存在的必要條件極值存在的必要條件: : 各一階偏導(dǎo)數(shù)等于零各一階偏導(dǎo)數(shù)等于零1*200().0 xxxnFFF XF H駐點(diǎn)駐點(diǎn)二元函數(shù)的情況二元函數(shù)的情況多元函數(shù)的情況多元函數(shù)的情況:13( (二二) )極值存在的充分條件極值存在的充分條件: : 海賽矩陣海賽矩陣H(X*)正定正定點(diǎn)點(diǎn)X*為為極小點(diǎn)極小點(diǎn)海賽矩陣海

8、賽矩陣H(X*)負(fù)定負(fù)定點(diǎn)點(diǎn)X*為為極大點(diǎn)極大點(diǎn)海賽矩陣海賽矩陣H(X*)不定不定點(diǎn)點(diǎn)X*為為鞍點(diǎn)鞍點(diǎn)海賽矩陣海賽矩陣H(X*)正定正定點(diǎn)點(diǎn)X*為為極小點(diǎn)極小點(diǎn)證明證明: :*1()()()2 TTF XF XFXX H XX*1()()()2TTF XF XFXX H XX =0處處處處F(X) F(X*), 故故點(diǎn)點(diǎn)X*為為極小點(diǎn)極小點(diǎn)二次型二次型0若：若：14什么是矩陣正定、什么是矩陣正定、負(fù)定、不定？負(fù)定、不定？111212122212.nnnnnnaaaaaaAaaa若若各階主子行列式均大于零各階主子行列式均大于零正定正定11110aa11121122122121220aaaaaaa

9、a111212122212.0.nnnnnnaaaaaaaaa若若各階主子行列式如下各階主子行列式如下負(fù)定負(fù)定110a111221220aaaa1112132122233132330aaaaaaaaa.0不是不是正定正定或或負(fù)定負(fù)定不定不定152.3 2.3 無約束目標(biāo)函數(shù)極值點(diǎn)存在條件無約束目標(biāo)函數(shù)極值點(diǎn)存在條件函數(shù)極值函數(shù)極值必要條件必要條件充分條件充分條件極極 小小H(X*)正定極極 大大H(X*)負(fù)定一元函數(shù)一元函數(shù)二元函數(shù)二元函數(shù)*()F XH*()0fx*()0fx*()0fx*120()0 xxFF XF 21 12 21 20 x xx xx xFFF1 10 x xF1 10

10、 x xF高等數(shù)學(xué)高等數(shù)學(xué)：設(shè)函數(shù)：設(shè)函數(shù)F(X)=F(x1,x2)在點(diǎn)在點(diǎn)X*的某鄰域內(nèi)連續(xù)且有一階及二的某鄰域內(nèi)連續(xù)且有一階及二階連續(xù)偏導(dǎo)數(shù)，在階連續(xù)偏導(dǎo)數(shù)，在點(diǎn)點(diǎn)X*有有Fx1=0、 Fx2=0，令：，令：1 11 22 2,x xx xx xFA FBFC2000ABACBBCA1 11 22 12 21 100 x xx xx xx xx xFFFFF*1 11 22 12 2()x xx xx xx xFFH XFF正定正定16極值存在的必要條件極值存在的必要條件: : 各一階偏導(dǎo)數(shù)等于零各一階偏導(dǎo)數(shù)等于零1*200().0 xxxnFFF XF H駐點(diǎn)駐點(diǎn)極值存在的充分條件極值存

11、在的充分條件: : 海賽矩陣海賽矩陣H(XH(X* *) )正定正定點(diǎn)點(diǎn)X X* *為為極小點(diǎn)極小點(diǎn)1 11 21( )2 12 2212.().x xx xx xnkx xx xx xnxnxxnxxnxnFFFFFFH XFFF各階主子行列式均各階主子行列式均大于零大于零正定正定小結(jié)小結(jié): :無約束目標(biāo)函數(shù)極值點(diǎn)存在條件無約束目標(biāo)函數(shù)極值點(diǎn)存在條件17例題例題試判斷試判斷X0=2 4T是否為下面函數(shù)的極小點(diǎn)：是否為下面函數(shù)的極小點(diǎn)：4222112121()245F Xxx xxxx解：解：3111210221204424()022xxFxx xxF XFxx 滿足極值存在的必要條件滿足極值

12、存在的必要條件21 11 21202 12 234812424()824211x xx xx xx xFFxxxH XFFx348340,342( 8)( 8)4082 各階主子行列式均大于零各階主子行列式均大于零H(X0)正定正定X0是極小點(diǎn)是極小點(diǎn)18例：求解例：求解 極值點(diǎn)和極值極值點(diǎn)和極值解解 的極值點(diǎn)必須滿足的極值點(diǎn)必須滿足：解此聯(lián)立方程得：解此聯(lián)立方程得： 即點(diǎn)即點(diǎn) 為一駐點(diǎn)。再利用海賽矩陣的性質(zhì)來判斷為一駐點(diǎn)。再利用海賽矩陣的性質(zhì)來判斷此駐點(diǎn)是否為極值點(diǎn)。此駐點(diǎn)是否為極值點(diǎn)。 362252)(21332232221xxxxxxxxXf024)(311xxxXf06210)(322

13、xxxXf0222)(3213xxxxXf, 1, 121xx23xTX2,1 ,1 *362252)(21332232221xxxxxxxxXf192222100204)()()()()()()()()()(*)22(*)21(*)22(*)222(*)212(*)21(*)221(*)211(*)2(*)nnnnnnxxXfxxXfxxXfxxXfxxXfxxXfxxXfxxXfxxXfXH11121121224040,400010aaaaa則20因此，赫森矩陣是正定的。故駐點(diǎn)因此，赫森矩陣是正定的。故駐點(diǎn) 為極小點(diǎn)。為極小點(diǎn)。對應(yīng)于該極小點(diǎn)的函數(shù)極小值為對應(yīng)于該極小點(diǎn)的函數(shù)極小值為由由:

14、 :TX2, 1 , 1 *03161)2(2)2(12)2(1512)(222*Xf362252)(21332232221xxxxxxxxXf21設(shè)平面上有點(diǎn)的集合設(shè)平面上有點(diǎn)的集合 ，在該集合中任意取兩個設(shè)計點(diǎn)，在該集合中任意取兩個設(shè)計點(diǎn)x x1 1和和x x2 2，如果連接點(diǎn)如果連接點(diǎn)x x1 1與與x x2 2直線上的一切內(nèi)點(diǎn)均屬于該集合，則此集合稱直線上的一切內(nèi)點(diǎn)均屬于該集合，則此集合稱為為x x1 1oxox2 2平面上的一個凸集，平面上的一個凸集， 2.4 凸集與凸函數(shù)凸集與凸函數(shù)22凸集的數(shù)學(xué)定義如下：對某集合內(nèi)的任意兩點(diǎn)凸集的數(shù)學(xué)定義如下：對某集合內(nèi)的任意兩點(diǎn)x1與與x2連線

15、，如果連連線，如果連線上的任意點(diǎn)線上的任意點(diǎn)x均滿足均滿足xx1+(1- -)x2，則該集定義為一個凸集，則該集定義為一個凸集 23優(yōu)化設(shè)計總是期望得到全局最優(yōu)解優(yōu)化設(shè)計總是期望得到全局最優(yōu)解局部最優(yōu)解局部最優(yōu)解全局最優(yōu)解全局最優(yōu)解2.4.2 凸函數(shù)凸函數(shù)由前局部極小點(diǎn)與全局極小點(diǎn)由前局部極小點(diǎn)與全局極小點(diǎn): : 24 凸函數(shù)凸函數(shù) 函數(shù)的凸性函數(shù)的凸性(單峰性單峰性) 最優(yōu)值最優(yōu)值(最小值最小值)與極小值是有區(qū)別的與極小值是有區(qū)別的,在什么情況下極小點(diǎn)就在什么情況下極小點(diǎn)就是最小點(diǎn)是最小點(diǎn)?極小值就是最優(yōu)值極小值就是最優(yōu)值?函數(shù)的凸性：實(shí)質(zhì)就是單峰性。如果函數(shù)在定域內(nèi)是單峰的函數(shù)的凸性：實(shí)質(zhì)

16、就是單峰性。如果函數(shù)在定域內(nèi)是單峰的,即只有一個峰值即只有一個峰值,則其極大值就是全域內(nèi)的最大值則其極大值就是全域內(nèi)的最大值,則其極小值則其極小值就是全域內(nèi)的最小值就是全域內(nèi)的最小值25幾何解釋幾何解釋：如圖所示的一元函數(shù)如圖所示的一元函數(shù)f(x)，在定義域內(nèi)在定義域內(nèi)任取兩點(diǎn)任取兩點(diǎn)x1與與x2，函數(shù)曲線上的對應(yīng)點(diǎn)，函數(shù)曲線上的對應(yīng)點(diǎn)為為K1與與K2，連該兩點(diǎn)的直線方程設(shè)為，連該兩點(diǎn)的直線方程設(shè)為 。如在。如在x1，x2內(nèi)任取一點(diǎn)內(nèi)任取一點(diǎn)x，則該點(diǎn)，則該點(diǎn)對應(yīng)的對應(yīng)的f(x)與直線與直線 兩個函數(shù)值之關(guān)系兩個函數(shù)值之關(guān)系為為f(x) ，則稱，則稱f(x)為為a，b區(qū)間內(nèi)的區(qū)間內(nèi)的凸函數(shù)。凸

17、函數(shù)。 )(x)(x)(x數(shù)學(xué)定義：數(shù)學(xué)定義：設(shè)設(shè)F(x)為定義在為定義在n n維歐氏空間中一個凸集維歐氏空間中一個凸集 上的函數(shù)上的函數(shù)，x1與與x2為為 上的任意兩設(shè)計點(diǎn)，取任意實(shí)數(shù)上的任意兩設(shè)計點(diǎn)，取任意實(shí)數(shù)，0，1，將，將x1與與x2連線上連線上的內(nèi)點(diǎn)的內(nèi)點(diǎn)x表達(dá)為：表達(dá)為：xx1+(1- -)x2，如果恒有下式成立如果恒有下式成立 Fx1+(1- -)x20、0，則線性組合，則線性組合F(x)F1(x)+F2(x)也是域上的凸函也是域上的凸函數(shù)。數(shù)。 27函數(shù)的凸性與局部極值及全域最優(yōu)值之間的關(guān)系：函數(shù)的凸性與局部極值及全域最優(yōu)值之間的關(guān)系：若若F(x)為凸集為凸集 上的一個凸函數(shù)，

18、則上的一個凸函數(shù)，則 上的任何一個極值點(diǎn)，上的任何一個極值點(diǎn)，同時也是它的最優(yōu)點(diǎn)。同時也是它的最優(yōu)點(diǎn)。282122212141060)(xxxxxxXf)2 , 1(|ixXi2112)()()()()(222122212212xxXfxxXfxxXfxxXfAXH032112, 022221121111aaaaa令)(Xf 例：例： 判別函數(shù)判別函數(shù)在在 上是否為凸函數(shù)。上是否為凸函數(shù)。 解：利用海賽矩陣來判別：解：利用海賽矩陣來判別：因海賽矩陣是正定的，故因海賽矩陣是正定的，故 為嚴(yán)格凸函數(shù)。為嚴(yán)格凸函數(shù)。292.5 約束極值點(diǎn)存在條件約束極值點(diǎn)存在條件(p89) 在約束條件下求得的函數(shù)極

19、值點(diǎn)在約束條件下求得的函數(shù)極值點(diǎn), ,稱為約束極值點(diǎn)稱為約束極值點(diǎn). . K-TK-T條件條件( (約束極小點(diǎn)的必要條件約束極小點(diǎn)的必要條件 ): :如果有如果有n n個起作用的約束條件個起作用的約束條件, ,即即n n個約束函數(shù)交于一點(diǎn)個約束函數(shù)交于一點(diǎn), ,則該點(diǎn)成為約束極值點(diǎn)的必要條件是則該點(diǎn)成為約束極值點(diǎn)的必要條件是: :該點(diǎn)目標(biāo)函數(shù)的梯度方向應(yīng)處在由該點(diǎn)的該點(diǎn)目標(biāo)函數(shù)的梯度方向應(yīng)處在由該點(diǎn)的n n個約束函數(shù)梯度方個約束函數(shù)梯度方向所組成的錐形空間內(nèi)向所組成的錐形空間內(nèi). . 303132點(diǎn)的不等式約束面數(shù)在)(KXqK-T條件可以表示為條件可以表示為非負(fù)乘子33 對于凸規(guī)劃問題對于凸

20、規(guī)劃問題( (可行域?yàn)橥辜尚杏驗(yàn)橥辜? ,目標(biāo)函數(shù)為凸函目標(biāo)函數(shù)為凸函數(shù)數(shù)),),局部極值點(diǎn)和全域最優(yōu)點(diǎn)相重合局部極值點(diǎn)和全域最優(yōu)點(diǎn)相重合, ,但對于非凸規(guī)但對于非凸規(guī)劃問題則不然劃問題則不然. .如圖如圖: :34 K-T K-T條件只能檢驗(yàn)起作用約束的可行點(diǎn)條件只能檢驗(yàn)起作用約束的可行點(diǎn), ,如下圖中如下圖中X X* *是約束極值點(diǎn)是約束極值點(diǎn), ,但但K-TK-T條件對它不實(shí)用條件對它不實(shí)用. .35例例: 用用 條件檢驗(yàn)點(diǎn)條件檢驗(yàn)點(diǎn) 是否為目標(biāo)函數(shù)是否為目標(biāo)函數(shù) 在不等式約束在不等式約束 、 條件下的約束最優(yōu)點(diǎn)。條件下的約束最優(yōu)點(diǎn)。解：計算諸約束函數(shù)值解：計算諸約束函數(shù)值KTTKX0

21、 , 2)(2221)3()(xxXf04)(2211xxXg0)(22 xXg05 . 0)(13 xXg)(kX0)()(2kXg0044)()(1kXg05 . 15 . 02)()(3kXg 點(diǎn)是可行點(diǎn)，該點(diǎn)起作用約束函數(shù)為點(diǎn)是可行點(diǎn)，該點(diǎn)起作用約束函數(shù)為)(1Xg)(2Xg)(kX計算計算 點(diǎn)有關(guān)諸梯度點(diǎn)有關(guān)諸梯度022) 3(2)(0221)(21xxkxxXf36解得：解得： ，乘子均為非負(fù)，乘子均為非負(fù)，故滿足故滿足 條件，點(diǎn)條件，點(diǎn) 為約束極為約束極值點(diǎn)，參看左圖，亦得到證實(shí)。而且，值點(diǎn)，參看左圖，亦得到證實(shí)。而且，由于由于 是凸函數(shù)，可行域?yàn)橥辜?，是凸函?shù)，可行域?yàn)橥辜?，?/p>

22、以點(diǎn)所以點(diǎn) 也是約束最優(yōu)點(diǎn)。也是約束最優(yōu)點(diǎn)。1412)(021)(121xxkxXg1010)(02)(221xxkXg0)()()()(22)(11)(kkkXgXgXf0101402215 . 021TK TKX0 , 2)()(Xf)(kX代入式，求拉格朗日乘子代入式，求拉格朗日乘子372.6 優(yōu)化計算的數(shù)值解法及收斂條件優(yōu)化計算的數(shù)值解法及收斂條件v2.6.1 數(shù)值計算法的迭代過程數(shù)值計算法的迭代過程 選初始點(diǎn)選初始點(diǎn) x(0) 確定搜索方向確定搜索方向 S(0),沿沿S(0)搜索搜索,步長為步長為 (0) 求得第一個迭代點(diǎn)求得第一個迭代點(diǎn) x(1) (1)(0)(0)(1)(0)(0)F xx= x+aS, F x(2)(1)(1)(2)(1)(1)F xx= x+ aS, F x( )(1)( )( )(1)( ). . .kkkkkkx= x+F xF xS,ox1x2(1)x(2)x(0)x( )kx(0)(1)kx*x(0)S(1)S( )kS( )(1)( )( )kkkkx= x+S基本迭代公式基本迭代公式:(0)(1)(2*)( )(1)0121,.,.,.,.kkkkxxxxxFFFFFxF步長步長方向方向步步下步步下降降步步逼步步逼近近38