運(yùn)籌學(xué)課件非線性規(guī)劃第五章

1、非線性第五章§5.11的導(dǎo)出設(shè) f (x) 是二次可函數(shù),x Î Rn .又設(shè)x(k ) 是 f (x) 的極小點(diǎn)的一個估計, 即把 x(k ) 做為f (x) 的近似極小點(diǎn)。把 f (x) 在 x(k ) 展成Taylor級數(shù)，并取近似：f ( x ) » f ( x ) = f (x(k ) )+ Ñf (x(k ) )T ( x - x(k ) )+ 1 ( x - x(k )T Ñ2 f (k ) )2)f (x(k ) ) 是f (x)在 x(k )其中， Ñ2矩陣。處的Hessian(x) 約等于由于f(x) ，所以，可以

2、將(x)f (x)的極小點(diǎn)做為的近似極小點(diǎn)。(x) 的極小點(diǎn)。下面求為了求f (x) 的平穩(wěn)點(diǎn)，令Ñf (x) = 0Ñf (x(k ) )+ Ñ2 f (即(k ) )= 0(x) 的極小點(diǎn)f (x(k ) )可逆，則得到設(shè)Ñ2Ñf (x(k ) )+ Ñ2 f (k ) )= 0Ñ2 f (k ) )= -Ñf (x(k ) )(Ñ 2 f (x(k ) )-1 Ñ 2 f (k ) ) =- (Ñ 2 f (x(k )-1 Ñf (x(k ) )-1 Ñf (

3、x(k ) )(x - x(k ) )= - (Ñ2f (x(k )x= x(k ) - Ñ2 f (x(k ) )-1 Ñf (x(k ) )這個點(diǎn)作為 f (x) 的近似極小點(diǎn)，作為第k+1 個迭代點(diǎn)，即= x(k ) - Ñ2 f (x(k ) )-1 Ñf (x(k ) )x(k +1 )這個公式就是的迭代公式。其中， Ñ2 f (x(k ) )-1 是Hessian矩陣 Ñ2 f (x(k ) )的逆矩陣。這樣，知道 x(k ) 后，算出在這一點(diǎn)處目標(biāo)函數(shù)的梯度和Hesse矩陣的逆，代入的迭代公式，便得到后繼點(diǎn) x

4、 (k +1)k + 1 代替k ，再用用的迭代公式計算，又得到 x(k +1) 的后繼點(diǎn)。依此類推，產(chǎn)生序列x(k )下，這個序列收斂。在適當(dāng)?shù)臈l件2的迭代公式的迭代公式x(k +1 ) = x(k ) - Ñ2 f (x(k ) )-1 Ñf (x(k ) )注意，的迭代公式中不用一維搜索。在的迭代公式中，- Ñ2 f (x(k ) )-1 Ñf (x(k ) )可以看作是一搜索方向，這個方向d (k ) = -Ñ2 f (x(k ) )-1 Ñf (x(k ) )叫做方向。3停機(jī)準(zhǔn)> 0 ，當(dāng)對于給定的精度Ñf

5、(x(k ) ) < ef (x) 的近似極時，停止迭代。此時的 x(k )小點(diǎn)。作為4計算步驟x(1) Î Rnk = 1> 01º給定，置，誤差計算 Ñf (x(k ) )2ºÑf (x(k ) ) < e3º若，則停止計算，輸出f (x(k ) )x(k )；否則，計算 Ñ2，求出f (x(k ) )-1Ñ24º計算x(k +1 )f (x(k ) )-1 Ñf (x(k ) )= x(k ) - Ñ2k := k + 1，轉(zhuǎn)步2º置例5.1.1用求解

6、下列問題：min f ( x ) = (x1 - 1) + x422取x(1) = é0ùêë1úû解： 在點(diǎn) x 處，目標(biāo)函數(shù)f (x ) = (x1 - 1) + x242的梯度和Hessian矩陣分別為4(x - 1) ùéê3Ñf (x) =12 x2úëû12(x- 1)é0ù2f (x) =和Ñ210ê2úëû第1次迭代：Ñf (x(1) )= é- 4ù

7、ëêúû2f (x(1) )= êé1202ûÑ2ë 0取x(1) = êé0ùúë1ûf (x(1) )-1 Ñf (x(1) )x(2 ) = x(1) - Ñ20ù-1 é- 4ùé0ùé12= êë1úû - êë 0é1ù2úûêë

8、0;û2= ê3úëê0 úû第2次迭代：éêêë=32ù(x)=-()27 úÑf2úû0é480ù()(2 )ê 9ú2úûÑ2fxêë 0f (x(2 ) )-1 Ñf (x(2 ) )x(3 ) = x(2 ) - Ñ2ù-1 éé1ùé4832 ùê

9、- 27 ú0ú2úû= ê3ú - ê 9êë0 úûêë 0éêëúû0éùê3úë0 û12ù-êëê9 ú=-0ûé5 ù= ê9 úë0 û繼續(xù)迭代下去，得到é 19 ùé65 ù(4 )(

10、5 )= ê27 ú , x= ê81ú ,Lxëê 0 úûëê 0 úû例5.1.2用求解下列問題：22min f(x) = x1+ 2 x2- 4 x1- 2 x1 x2取x(1) = é1ùêë1úû解： 計算目標(biāo)函數(shù)的梯度和Hessian陣2 - 4ùÑfú4 x2- 2ëûx1f (x) = êé2Ñ 2ë- 24&

11、#251;解： 第1次迭代：Ñf (x(1) )= é- 4ùëê 2 úû- 2ùf (x(1) )= é2Ñ2ëê- 2úû1ö4Ñ2 f (x(1) )-1= 1 æ 2ç÷1ø2 è 1由的迭代公式f (x(1) )-1 Ñf (x(1) )x(2 ) = x(1) - Ñ2- 2ù-1 é- 4ùé1ù

12、33;2= êë1úû - êë- 2úûêëúû42ù é- 4ú ê= éê1ù1ú -é2ê12 ë11û2ë1ûëûé4ê=ë2û由于Ñf (x(2 ) )= é0ùëê0úûÑf (x(2 ) ) = 0 < e即所以， x