运筹学课件非线性规划第四章

1、非线性第四章最速下降法§4.1基本思想最速下降法1最速下降法的基本思想是：每次用目标函数在迭代点的下降最快方向进行一维搜索，逐步向极小点逼近。因为每次用的方向是负梯度，所以，又称为梯度法.2理论准备f(x) 在 x 点处的负梯度定理4.1.1函数方向是 f(x) 在该点处的下降最快方向。下降最快方向称为最速下降方向。f(x) 在 x 点处的方向导数证：考虑函数¶f (x)¶d由方向导数的性质，有¶f (x) = Ñf(x)T d¶d再由schwatz 不等式Ñf(x)T d£ Ñf(x)d等号成立当且仅当

2、 Ñf(x) 与 d 线性相关，即d = Ñf(x)d = -Ñf(x)或d = -Ñf(x) 时,当¶f (x) = Ñf(x)T d¶d=Ñf(x)T ( -Ñf(x)= - Ñf(x) 2¶f (x) 的值最小。d = -Ñf(x) 时,即,当¶d因此，d = -Ñf(x) 是快方向。f(x)在该点处的下降最3最速下降算法的迭代公式最速下降算法的迭代公式为d (k) = -Ñf ( x(k) )x(k +1) = x(k) + l k d(

3、k)是从 x(k) 出发的搜索方向，这里取在点其中 d(k)x(k)处的最速下降方向，即d (k) = -Ñf ( x(k) )x(k)出发，沿方向 d(k) 进行一维搜索l k是从的步长，即：l k满足f( x(k) + l k d (k) ) = min f( x(k) + l d (k) )l ³04最速下降算法的计算步骤x(1) Î Rn ，> 01°给定初点误差k = 1，置2° 计算搜索方向d (k) = -Ñf ( x(k) )£ ed (k)3°若，则停止计算；否则，从x(k) 出发，沿 d(

4、k)，使进行一维搜索，求lkf( x(k) + l k d (k) ) = min f( x(k) + l d (k) )l ³04° 令x(k +1) = x(k) + l k d(k)置 k := k + 1，转步2°例4.1.1用最速下降法解下列问题：minf ( x ) = 2 x2 + x212x(1) = êé1ùú，e =1初始点ë1û10解：第1次迭代：目标函数 f ( x ) 在点 x(1)处的梯度Ñf ( x ) = é4 x1ùê2 x 

5、50;ë2ûÑf ( x(1) ) = é4ùëê2úû令搜索方向d (1) = -Ñf ( x(1) ) = éê- 4ë- 2û1=16 + 4 = 25 >d10不满足精度要求，还要继续计算。从 x(1) = éê1ùú 出发，沿( 1 ) 方向进行一维搜dë1û索，求步长l 1即minj ( l ) =f( x(1) + l d (1) )l ³0ùé-

6、 4ùé1 - 4lú + lú =x(1) + l d (1) = êé1ëê- 2ûëê1 - 2l ûë1ûj ( l ) = 2 (1 - 4l )2 + (1 - 2l )2j ¢( l ) = -16 (1 - 4l )- 4 (1 - 2l )5令j ¢( l ) = 0=,解得 l118在直线上的极小点x(2) = x(1) + l1 d(1)= êé1ùú + lé-

7、4ê1ë- 2ûë1ûé1ù= ê- 9ú= é1ù +é- 4ù5ê 4 úêë1úû18 êë- 2úûëê 9 úû第2次迭代：f ( x ) 在点 x(2)处的最速下降方向为éù4d (2) = -Ñf ( x(2) ) = êú9ê8ú-ë

8、9ûæ 4 ö28 ö2æ491=+ ç-=5 >d (2)ç÷÷è 9 øè9 ø10不满足精度要求，还要继续计算。从 x(2)出发沿d ( 2 )minj ( l ) =l ³0进行一维搜索：f( x(2) + l d (2) )é- 1ùé4ùé- 1 + l 4 ùêêëê9ú + l êú = ê9 &

9、#250;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 (1 - 2l )81令 j ¢( l ) = 0815=，得到 l212x(3) = x(2) + l 2 d (2)é1ù2=27 ëê1ú

10、;û第3次迭代：d (3) = -Ñf ( x(3) )é - 2ê4=27 ë- 1û41=5 >d (3)2710不满足精度要求，还要继续计算。从 x(3)出发沿 d( 3 )minj ( l ) =l ³0进行一维搜索：f( x(3) + l d (3) )é1êùú + lé- 224x(3) + l d (3) =27 ëê- 1û27 ë1ûé1 - 4l ù2=27 ë

11、4;1 - 2l úû84j ( l ) =(1 - 4l )2 +(1 - 2l )2272272令j ¢( l ) = 0，解得5=l318x(4) = x(3) + l 3 d(3)é- 1ù2é- 1ù243 êë 4 úû2 ê9ú =27 êúúû49êë这时有81=- Ñf ( x(4) ) =5 <d (4)24310已经满足精度要求，得到近似解2é- 1ù

12、;243 ëê 4 úûx =实际上，问题的最优解x* = êé0ùë0úû例4.1.2用最速下降法解下列问题：1312minf ( x ) =+2122xxé3êùú，迭代3次。初始点 x(1) =ë2ûf ( x ) 的梯度解：目标函数é2ù1úúûxê3Ñf ( x ) =êëx2第1次迭代：在点 x(1)处的梯度Ñf ( x(1)

13、 ) = êé2ë2û令搜索方向d (1) = -Ñf ( x(1) ) = éê- 2ë- 2ûé3êùú 出发，沿 d( 1 ) 方向进行一维搜从 x(1) =ë2û索，求步长l 1minj ( l ) =l ³0f( x(1) + l d (1) )ùé- 2ùé3 - 2lú + l êú = êx(1) + l d (1) = ê

14、3;3ë2 - 2l ûë2ûë- 2ûj ( l ) =f( x(1) + l d(1) )= 1 (3 - 2l )2 + 1 (2 - 2l )23102- 8 l=+ 5l23j ¢( l ) = 20 l- 83，解得令j ¢( l ) = 0= 6l15在直线上的极小点x(2) = x(1) + l1 d(1)= êé3ùú + lé- 2ê1ë- 2ûë2û= êé3ù6

15、é- 2ú +ê5 ë- 2ûë2ûé3ù= êú5ê2ú-êë5 úû第2次迭代：x(2)在点处的梯度é2 ´ 3ùé2ùÑf ( x(2) ) = ê35 ú = êú5ê2 ú-ê2ú-ëêúûêë5 úû

16、;5令搜索方向é- 2ùêêêë5 ú= -Ñ) =(2)(2)f (dxúúû25é3ùx(2) = êú5出发，沿 d( 2 ) 方向进行一维搜索从ê2ú-úë5 û，求步长l 2minj ( l ) =l ³0f( x(2) + l d (2) )é3ùé- 2ùé3 - l 2ùx(2) + l d (2) = 

17、4;ú + l ê5 ú = êú555ê2ú-êêëúúûê22ú-+ l25ëê5 úûêë5 úû5j ( l ) =f( x(2) + l d (2) )2 ö22 ö21 æ 31 æ2=ç- l÷355+ç-+ l÷255èøèø= 10

18、 l 2 - 8l + 175255j ¢( l ) = 20 l -875令j ¢( l ) = 0 ，解得25= 6l25在直线上的极小点x(3) = x(2) + l 2 d (2)é3ùé- 2ù= êú + lê2 êêë5 ú5ê2ú-úúû25ëêé5 úûùé- 2ùé 3 ù3= ê

19、0; + 6 ê5 ú= ê25 ú5ê2ú-5 êúúûê 2 ú25ëê5 úûêëëê25 úû第3次迭代：x(3)在点处的梯度é2 ´ 3 ùé 2 ù) = ê325ú = ê25úÑf( x( 3 )êúê 2 ú2ê

20、úêúëûë25û25令搜索方向é-2 ùd (3) = -Ñf ( x(3) ) = ê25 úê-2 úêë25 úûé 3 ùêú25=(3)( 3 )从 x出发，沿方向进行一维搜索ê 2 údêë25 úû，求步长 l 3minj ( l ) =l ³0f( x(3) + l d (3) )é

21、; 3 ùé- 2ùé 32 ù- l- lx(3) + l d (3) = ê25 ú + l ê5 ú = ê2525 úê 2 úê2ú-ê 22 úêë25 úûêë5 úûêë2525 úûj ( l ) =f( x(3) + l d(3) )2 ö22 ö21 æ 3

22、1 æ 2=ç- l÷32525+ç- l÷22525èøèøl +5=-´20- 8j ¢( l ) =l3 ´ 5454令 j ¢( l ) = 0，解得= 6l35在直线上的极小点x(4) = x(3) + l 3 d(3)é 3 ùé-2 ù= ê25 ú + lê25 úê 2 úë25 û3 ê-2 ú25 

23、1;êëé 3 ùé-2 ùéùúú3= ê25 ú + 6 ê25 ú= ê125ê 2 úë25 û5 ê-2 ú25 ûê-2êëêë125 û非线性第四章最速下降法§4.2最速下降法的收敛性1算法的收敛性定理4.2.1：设 l*是一维搜索步长，即f( x(k) + l* d (k)minf( x(k) + ) =d (k)f( x(k) + a d (k) ) £ MÑ2且，则) - f( x(k) + l) ³f( x(k)d (k)1) 2 cos2Ñf( x(k)d(k) ,-Ñf( x(k)2Mf( x) 二次连续可微，且定理4.2.2f( x ) £ M设函数x( 0 ) ，用最Ñ2,则对任意的初始点速下降法产生的点列 x(k) 或有限终止，或) = -¥f( x(k)limk