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

1、非线性第五章§5.11的导出设 f (x) 是二次可函数,x Î Rn .又设x(k ) 是 f (x) 的极小点的一个估计, 即把 x(k ) 做为f (x) 的近似极小点。把 f (x) 在 x(k ) 展成Taylor级数，并取近似：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)的极小点做为的近似极小点。(x) 的极小点。下面求为了求f (x) 的平稳点，令Ñf (x) = 0Ñf (x(k ) )+ Ñ2 f (即(k ) )= 0(x) 的极小点f (x(k ) )可逆，则得到设Ñ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 ) )这个点作为 f (x) 的近似极小点，作为第k+1 个迭代点，即= 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 ) 后，算出在这一点处目标函数的梯度和Hesse矩阵的逆，代入的迭代公式，便得到后继点 x

4、 (k +1)k + 1 代替k ，再用用的迭代公式计算，又得到 x(k +1) 的后继点。依此类推，产生序列x(k )下，这个序列收敛。在适当的条件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停机准> 0 ，当对于给定的精度Ñf

5、(x(k ) ) < ef (x) 的近似极时，停止迭代。此时的 x(k )小点。作为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，转步2º置例5.1.1用求解

6、下列问题：min f ( x ) = (x1 - 1) + x422取x(1) = é0ùêë1úû解： 在点 x 处，目标函数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 û继续迭代下去，得到é 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úû解： 计算目标函数的梯度和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