1、非線性第二章無(wú)約束最優(yōu)化方法的結(jié)構(gòu)§2.1無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)性條件考慮非線性問(wèn)題：minf ( x ),x Î Rnmin f ( x )xÎRnf ( x ) 是定義在 Rn 上的實(shí)函數(shù)。（1）或其中,1必要條件f ( x ) 在定理 2.1.1 （下降條件 ）設(shè)函數(shù)點(diǎn) x 可微，如果存在方向 d ，使Ñf ( x )T d < 0Î ( 0 ,d )> 0，使得對(duì)每個(gè)，則存在數(shù)f ( x + ld ) <f ( x )證明：根據(jù)函數(shù)可微性的定義，有f ( x + ld ) = f ( x ) + l Ñf (

2、 x )T d + ld a ( x,ld )= f ( x ) + l Ñf ( x )T d + ld a ( x,ld )l（2）® 0 時(shí)，a ( x,ld ) ® 0其中，當(dāng)由于Ñf ( x )T d < 0充分小時(shí)，在(2)中有當(dāng) lÑf ( x )T d + ld a ( x,ld ) < 0l> 0Î ( 0 ,d ) 時(shí)，有因此存在，使得當(dāng)l Ñf ( x )T d + ld a ( x,ld ) < 0l從而，由（2）得到f ( x + ld ) <f ( x )f ( x

3、)定理2.1.2（一階必要條件）設(shè)函數(shù)x可微，若 x 是局部極小點(diǎn)，則梯度在點(diǎn)= 0Ñf ( x )證明：用反證法。設(shè)¹ 0Ñf ( x )令方向 d = -Ñf ( x ) ,則有Ñf ( x )T d = - Ñf ( x )T Ñf ( x )= - Ñf ( x ) 2 < 0> 0根據(jù)定理2.1.1（下降條件），存在數(shù)Î ( 0 ,d )時(shí)，成立使得當(dāng)f ( x + ld ) < f ( x ),= 0x 是局部極小點(diǎn)Ñf ( x )所以這與定義2.1.1滿足

4、9;f ( x )= 0的點(diǎn)稱(chēng)為穩(wěn)定點(diǎn)（或平穩(wěn)點(diǎn)，或駐點(diǎn)）.f ( x )定理2.1.3（二階必要條件）設(shè)函數(shù)在點(diǎn) x 處二次可微，若x 是局部極小點(diǎn)，則梯度= 0Ñf ( x )，并且Hessian矩陣Ñ2f ( x )是半正定的。證明： 設(shè) d是任意一個(gè)n維向量，由于 f ( x )在 x 處二次可微，且Ñf ( x )因此= 0，f ( x + ld ) = f ( x ) + l Ñf ( x )T d+ 1 l 2 dT Ñ22a ( x,ld )f ( x )d + l 2d2= f ( x ) + 1 l 2 dT Ñ2

5、 f ( x )d + l 22a ( x,ld )（3）d2® 0 時(shí)，a ( x,ld ) ® 0f ( x ) 移至等號(hào)左端，并兩端除以其中，當(dāng)把式(3)中，得到l 2f ( x + ld ) - f ( x ) = 1 dT Ñ22a ( x,ld )f ( x )d + dl 22l 充分小時(shí)，必有由于 x 是局部極小點(diǎn)，當(dāng)f ( x + ld ) ³® 0 時(shí)a ( x,ld ) ® 0f ( x )以及當(dāng)因此，由（3）可推得d T Ñ2f ( x )d ³ 0Ñ2f ( x ) 是半正定的。

6、即2二階充分條件設(shè) f ( x )定理 2.1.4（二階充分條件）x 處二次可微，若梯度在點(diǎn)= 0f ( x )Ñ且Hessian矩陣Ñ2f ( x ) 正定，則 x 是局部極小點(diǎn)。證明：根據(jù)函數(shù)二次可微的定義，有f ( x ) = f ( x ) + Ñf ( x )T (x - x )+ 1 (x - x )T Ñ2f ( x )(x - x ) + (x - x ) 2a ( x,(x - x ) )(4)2時(shí)，a ( x ,(x - x ) ) ® 0x ® x其中，當(dāng)現(xiàn)在用反證法證明。設(shè) x 不是局部極小點(diǎn)， 則存在收斂于

7、x 的點(diǎn)列 x( k ) ，使得對(duì)于每一個(gè)k，有f ( x( k ) ) <f ( x )（5）把 x( k )代入(4)，得到f ( x( k ) ) = f ( x ) + Ñf ( x )T ( x( k ) - x )+ 1 ( x( k ) - x )T Ñ2f ( x )( x( k ) - x )2+ ( x( k ) - x ) 2a ( x,( x( k ) - x ) )將 f ( x ) 移至等號(hào)左端，兩端除以2( x( k ) - x )，并注意到= 0f ( x )Ñ得出f ( x( k ) ) - f ( x ) =2( x( k

8、 ) - x )1 ( x( k ) - x )T( x( k )- x )Ñ2f ( x )2 ( x( k ) - x )( x( k ) - x )+ a ( x,( x( k ) - x ) )(6)x( k )- x( k ) =d（7）令( x( k ) - x )帶入(6)。由于此式左端小于零，因此有把 d ( k )1( k )2 d2+ a ( x, ( x) < 0T( k )( k )( k )Ñf ( x )d- x ) d(8)由 d ( k ) 的定義可知，= 1d( k )d ( k j)d ( k ) 為有界點(diǎn)列，因此存在收斂子序列&#

9、174; ¥當(dāng)時(shí)，有d( k jk j) ® d，= 1。這樣，由(8)得到d且2f ( x )d< 0TÑd這個(gè)結(jié)果與Ñ2f ( x ) 是正定矩陣相。3充要條件定理 2.1.5凸函數(shù)，xÎRn是設(shè) f ( x ) 是定義在 Rn 上的可微，則 x 為整體極小點(diǎn)的充要條件= 0Ñf ( x )證明：必要性是顯然的。若 x 是整體極小點(diǎn)，自然是局部極小點(diǎn)，由定理（一階必要條件） 可知，= 0Ñf ( x )現(xiàn)在證明充分性。xÎRnÑf ( x ) = 0 ，則對(duì)任意的Ñf ( x )T (

10、x - x ) = 0設(shè)，有f ( x ) 是可微凸函數(shù)，所以由于f(x) ³ f( x ) + Ñf ( x )T (x - x ) =即 x 是整體極小點(diǎn)。f( x )例 2.1.1利用極值條件解下列問(wèn)題：2minf(x) =+-2122221(-1)xxxx1解：先求駐點(diǎn)。由于¶f=- 2- 2314xx1¶ x1¶f= 2 x2¶ x2= 0令Ñf ( x )即- 2 x- 2 = 02 x2 = 0314x1解此方程組，得到駐點(diǎn)x = ( 1,0 )Tx 是否為極小點(diǎn)。再利用極值條件由于目標(biāo)函數(shù)的Hessian矩陣

11、為-æ0 ö21122x= çè÷2 øÑ2f ( x )0由此可知，在點(diǎn) x = ( 1,0 )T 的Hessian陣為= æ 100 öçè 0÷2 øÑ2f ( x )Ñ2顯然f ( x ) 為正定矩陣，所以，駐點(diǎn)x = ( 1,0 )T是局部極小點(diǎn)。例 2.1.2利用極值條件解下列問(wèn)題1313minf(x) =+31x1解：根據(jù)f ( x ) 的定義，有¶f= x2 - 11¶ x1¶f= x2 - 2 x2

12、2¶ x2= 0Ñf ( x )令即x2 - 1 = 01x2 - 2 x= 022解此方程組，得到駐點(diǎn)x(3) = é- 1ùx(4) = é- 1ùx(1) = é1ùx(2) = é1ùëê 0 úûëê 2 úûëê0úûêë2úû計(jì)算Hessian陣æö02x0çè1÷=

13、9;2f ( x )2 x1 - 2 ø將上面每個(gè)點(diǎn)代入Hessian陣，得= æ 20öÑ2f ( x(1) )çè 0÷- 2 ø= æ 20 öÑ2f ( x(2) )çè 0÷2 ø= æ - 20öÑ2f ( x(3) )çè 0÷- 2 ø= æ - 20 öÑ2 f ( x(4) )çè 0÷2 

14、8;由于矩陣Ñ2f ( x(1) )Ñ2f ( x(4) )不定，根據(jù)定理（二階充分條件），x(1) 和 x(4)不是極小點(diǎn)。矩陣 Ñ2 f ( x(3) ) 負(fù)定，因此 x(3)也不是極小點(diǎn)，實(shí)際上它是極大點(diǎn)。矩陣 Ñ2f ( x(2) ) 正定，根據(jù)定理，x(2)是局部極小點(diǎn)。非線性第二章無(wú)約束最優(yōu)化方法的結(jié)構(gòu)§2.2無(wú)約束最優(yōu)化方法的結(jié)構(gòu)1引例考慮無(wú)約束最優(yōu)化問(wèn)題minf ( x ) = 2 x2 + x212給定初始點(diǎn) x(1) = êé1ë1û第1次迭代用某種方法尋找搜索方向d( 1 ) = &

15、#233;- 4ùëê- 2úûùú 出發(fā)，沿d ( 1 )方向進(jìn)行一維搜索，從 x(1) = êé1ë1û求步長(zhǎng)l 1minj ( l ) =f( x(1) + l d (1) )即l ³0ùé- 4ùé1 - 4lú + lú =x(1) + l d (1) = êé1ëê- 2ûëê1 - 2l ûë1ûj (

16、l ) = 2 (1 - 4l )2 + (1 - 2l )2j ¢( l ) = -16 (1 - 4l )- 4 (1 - 2l )j ¢( l ) = 0令5=l解得118x(2) = x(1) + l1 d (1)= éê1ùú + lé- 4ê1ë- 2ûë1ûé1ù= ê- 9ú= é1ù +é- 4ù5ê 4 úêë1úû1

17、8 êë- 2úûëê 9 úûx(2)得到新的點(diǎn)x(2)f ( x(2) ) 比 x(1)對(duì)應(yīng)的目標(biāo)函數(shù)值對(duì)應(yīng)的目標(biāo)函數(shù)值 f ( x(1) ) 小，因此，有理由認(rèn)為 x(2)距最優(yōu)解進(jìn)了一步。第2次迭代用某種方法尋找搜索方向éù4d( 2 ) = êú9ê8ú-êë9úû從x(2) 出發(fā)沿 d( 2 ) 進(jìn)行一維搜索：minj ( l ) =l ³0f( x(2) + l d (2) )é-

18、1ùé4ùé- 1 + l 4 ùêêëê9ú + l êú = ê9 ú99+ l=(2)(2)xdúúûê8ú-êëêúúû494 - l 8ëê9úû992 (-1 + 4l )2 + 16 (1 - 2l )2j ( l ) =8181j ¢( l ) = 16 (-1 + 4l )- 64

19、 (1 - 2l )8181j ¢( l ) = 0令5=l得到212x(3) = x(2) + l 2 d (2)é1ùê ú2=27 ë1û得到新的點(diǎn) x(3)x(3) 對(duì)應(yīng)的目標(biāo)函數(shù)值f ( x(3) ) 比 x(2) 對(duì)應(yīng)的目標(biāo)函數(shù)值 f ( x(2) ) 小，因此，有理由認(rèn)為距最優(yōu)解進(jìn)了一步。x(3)第3次迭代：用某種方法尋找搜索方向é - 2 ù4d( 3 ) =27 ëê- 1úû再?gòu)?x(3)出發(fā)，沿d ( 3 ) 作一維搜索：minj ( l )

20、=l ³0f( x(3) + l d (3) )é1êùú + lé- 2ê24x(3) + l d (3) =27 ë1û27 ë- 1ûé1 - 4l ù2=27 ëê1 - 2l úû84j ( l ) =(1 - 4l )2 +(1 - 2l )227 227 2j ¢( l ) = 0令5=l解得318x(4) = x(3) + l 3 d (3)é- 1ùé- 1ù

21、2 ê9ú =2=27 êúúû243 êë 4 úû49êëx(4)得到新的點(diǎn)x(4)f ( x(4) ) 比 x(3)對(duì)應(yīng)的目標(biāo)函數(shù)值對(duì)應(yīng)的目標(biāo)函數(shù)值 f ( x(3) ) 小，因此，有理由認(rèn)為距最優(yōu)解進(jìn)了一步。x(4)2無(wú)約束最優(yōu)化方法的結(jié)構(gòu)考慮無(wú)約束最優(yōu)化問(wèn)題min f(x)xÎRnx( 1 )給定初始點(diǎn)第1次迭代：用某種方法尋找搜索方向 d( 1 ),出發(fā)，沿 d( 1 )作一維搜索：再?gòu)?x( 1 )minj( ) =f( x( 1 ) + d( 1 )

22、>0=f( x( 1 ) + d( 1 )1即,求j( ) =f( x( 1 ) + d( 1 )的極小點(diǎn)1求出之后，便可得到新的迭代點(diǎn)x( 2 ) = x( 1 ) + 1 d( 1 )1第2次迭代：用某種方法尋找搜索方向d( 2 ) ,出發(fā)，沿 d( 2 ) 作一維搜索：再?gòu)膞( 2 )minj( ) =f( x( 2 ) + d( 2 )>0=f( x( 2 ) + d( 2 )2即,求 j( ) =f( x( 2 ) + d( 2 ) 的極小點(diǎn)2求出2 之后，便可得到新的迭代點(diǎn)x3 = x( 2 ) + 2 d( 2 )第k次迭代：用某種方法尋找搜索方向 d(k)出發(fā)，沿

23、d(k) 作一維搜索：再?gòu)膞(k),minj( ) =f( x(k) + d(k)d(k)>0=f( x(k) + 1即,求 j( ) =f( x(k) + d(k) 的極小點(diǎn)k求出k 之后，便可得到新的迭代點(diǎn)x(k +1 ) = x(k) + 1 d(k)按照上述方法，可得一點(diǎn)列 x(k) 我們希望這一點(diǎn)列會(huì)越來(lái)越接近無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)解。上述方法就是無(wú)約束最優(yōu)化方法的結(jié)構(gòu)。問(wèn)題：搜索方向 d (k)如何確定？12j ( l) =+x (k)d (k)f()min如何求l ³ 0的極小點(diǎn)k點(diǎn)列 x(k) 會(huì)越來(lái)越接近無(wú)約束最優(yōu)化問(wèn)題的最優(yōu)解嗎？3問(wèn)題1將在第4，5，6,7

24、章中討論。問(wèn)題2將在第3章中討論。問(wèn)題3是方法的收斂性，討論的內(nèi)容是 x(k) 的極限是否趨于最優(yōu)解。在下一節(jié)中將給出收斂性概念。非線性第二章無(wú)約束最優(yōu)化方法的結(jié)構(gòu)§2.3算法的收斂性1算法收斂性概念求解最優(yōu)化問(wèn)題的基本方法是迭代算法。給定初始點(diǎn) x( 1 ) ，并在得出 x(k)之后按照某種規(guī)則產(chǎn)生一個(gè)新的點(diǎn) x(k +1 )去，得到一個(gè)點(diǎn)列x(k).如此迭代下若某個(gè)x(k)是最優(yōu)化問(wèn)題的最優(yōu)解，或者x(k)（的一個(gè)子列）的極限是最優(yōu)化問(wèn)題的最優(yōu)解，則稱(chēng)算法產(chǎn)生的點(diǎn)列是收斂的，或稱(chēng)算法是收斂的。具體定義如下。定義2.3.1某算法產(chǎn)生點(diǎn)列x(k)若存在 x*使得(k ® &

25、#165;)，簡(jiǎn)稱(chēng)x(k) 收斂于x(k) - x*® 0,則稱(chēng) x(k) 依范數(shù)收斂到 x* x*2算法收斂速度概念定義2.3.2設(shè) x(k)的極限為 x*設(shè)x(k +1 ) - x*= qlimk ®¥x(k)- x*其中， > 0 ,q > 0是與 k 無(wú)關(guān)的常數(shù)。 = 1,q > 0時(shí)，點(diǎn)列 x(k) 稱(chēng)為(1)當(dāng)具有線性收斂速度；當(dāng)1 < < 2 ,q > 0, = 1,q = 0時(shí)，點(diǎn)列(2) x(k) 稱(chēng)為具有超線性收斂速度。當(dāng) = 2 ,q > 0時(shí)，點(diǎn)列 x(k) 稱(chēng)為（3）具有二階收斂速度。正定、負(fù)定矩

26、陣正、負(fù)定二次型的概念n ) = XAXT設(shè) f是一個(gè)實(shí)二次型， 若對(duì)于任意的非零向量X ,X T AX > 0、X T AX < 0、X T AX ³ 0、X T AX £ 0,則稱(chēng)二次型分別為正定的、負(fù)定的、半正定的、都有半負(fù)定的,否則稱(chēng)為不定的.相應(yīng)的矩陣分別稱(chēng)為正定矩陣、負(fù)定矩陣、半正定矩陣、半負(fù)定矩陣、不定矩陣.例題:f (是正定二次型。3) =23僅當(dāng)X0時(shí)，f0"f (X ¹ 03) =理由：> 023或者1)f (3) =2 ³ 03æ x öç1 ÷2)f (3) =2

27、 = 0 Þ ç x2 ÷ = 03ç x3 ÷èø二次型3) =23f (的矩陣æ 10400öç÷0÷A = ç 0ç 07 ÷èø稱(chēng)為正定陣。例題:f ( x1 , x2 ,是正定二次型。2 + 424僅當(dāng)X0時(shí)，f01"X ¹ 0理由：2 + 4> 024f ( x1 , x2 ,1或者1)f ( x1 , x2 ,2 + 42 ³ 014æ x1 öç

28、÷2)f (x1 , x2 ,2 + 42 = 0Þ ç x2 ÷ = 014ç x ÷ç3 ÷è x4 ø二次型27+x2,33x34的矩陣1æ04000070ö0003ç÷÷÷÷øA0ç= ç00çè稱(chēng)為正定陣。例題:f ( x1 ,4) = 1223是半正定二次型。理由：1)f ( x1 ,4) = 122 ³ 03例如æ x1 öç

29、;÷f (0,0,0,1) = 1202 + 402 + 402 + 012 = 0 Þç x2 ÷ = 0ç x3 ÷ç÷è x4 øf的值非負(fù)，但對(duì)某些X0，f0二次型(的矩陣23,4 x312æö040000400000ç÷÷÷÷øA 0 ç= ç0 ç0 è稱(chēng)為半正定陣。例題:3) = -23f (是負(fù)定二次型。僅當(dāng)X0時(shí)，f0"X ¹ 03) =

30、-理由：f (< 023或者1) f (3) = -2 £ 03æ x öç1 ÷2) f ( x1 , x2 , x3 ) = -2 = 0Þ ç x2 ÷ = 03ç÷è x3 ø二次型3) = -23f (的矩陣æ - 10- 400öç÷A = ç000÷ç- 7 ÷èø稱(chēng)為負(fù)定陣。2 - 4例題:24f ( x1 , x2 ,1是負(fù)定二次型。僅當(dāng)X0時(shí)，f0"X ¹ 0理由：2 - 4< 024f ( x1 , x2 ,1或者1)f ( x ,) = -2 - 3 £ 01432)f ( x1 , x2 ,2 - 42 = 014æ x1 öç÷Þ ç x2 ÷ = 0ç x3 ÷ç÷è x4