第二节_最速下降法

第二节_最速下降法 Page 1 § 3.3 最速下降法 (梯度下降法) ( )min nx R f x ∈ 求解 Page 2问题提出问题提出问题：在点 kx 处，沿什么方向 ,kd ( )xf 下降最快? 分析： ( ) ( ) ( ) ( )( ) 0k k k k T k kf x d f x f x d o dα α α α+ = + ∇ + > 由于： ( ) ( ) cosk T k k kf x d f x d θ∇ = ∇ 显然当 1cos −=θ 时， ( )k T kf x d∇ 取极小值．...

Page 1 § 3.3 最速下降法 (梯度下降法) ( )min nx R f x ∈ 求解 Page 2问题提出问题提出问题：在点 kx 处，沿什么方向 ,kd ( )xf 下降最快? 分析： ( ) ( ) ( ) ( )( ) 0k k k k T k kf x d f x f x d o dα α α α+ = + ∇ + > 由于： ( ) ( ) cosk T k k kf x d f x d θ∇ = ∇ 显然当 1cos −=θ 时， ( )k T kf x d∇ 取极小值．此时： ( )k kd f x= −∇ 结论：沿负梯度方向 ( )xf 下降最快，因此称为最速下降方向． Page 3一一算法：最速下降法算法：最速下降法 Step1:给出 0 , 0 1 , : 0nx R kε∈ ≤ < < = Step2:计算 ( ) ,kf x∇ 如果 ( ) ,kf x ε∇ ≤ 停．否则，令 ( ) .k kd f x= −∇ 一维搜索 kdStep3: 沿 .kα方向确定步长 Step4: 令 1 ,k k kkx x dα+ = + 转Step２.1,k k= + Page 4精确一维搜索的最速下降法精确一维搜索的最速下降法 1. 定义：若在上一页Step3确定的步长满足：kα ( ) 0 argmin k kk f x dα α α > = + 即经精确一维搜索得到，那么相应的算法称为精确一维(线)搜索的最速下降法. 称 kα 为精确步长因子。 2.特点： 1k kd d +与正交, 即相继两次迭代中搜索方向是正交的． ( ) ( )0m ink k k kkf x d f x dαα α>+ = +即 Page 5 Page 6 ( ) ( )1 0T Tk k k k kkf x d d f x dα +∇ + = ∇ =即 ( ) 0 arg min k kk f x dα α α > = +由于即正交。则 ( ) 0 k k kdf x d d α α α α = + = ( )1 1k kd f x+ += −∇又因此 ( )1 0Tk kd d+ = 证明：选读内容 Page 7例1：用最速下降法求解： ( ) ( )2 2 01 2min 4 , 1, 1 Tf x x x x= + =取解： ( ) ( )1 2 1 2 , = 2 , 8 T Tf ff x x x x x ⎛ ⎞∂ ∂∇ = ⎜ ⎟∂ ∂⎝ ⎠ 下面用精确线搜索求步长. ( )0 1, 1 :Tx = 得 ( ) ( ) ( ) ( ) 0 0 0 2, 8 2, 8 T T f x d f x ∇ = = −∇ = − − (1) 由要求迭代两次, 并验证相邻两个搜索方向正交. 分析：容易看出该函数的极小点是 (0,0) .Tx∗ = Page 8 0 0 1 2( ) 1 8 f x d f αα α −⎛ ⎞+ = ⎜ ⎟−⎝ ⎠因 1 0 0 0 1 2 0.73846 0.13077 1 8 0.04616 x x dα ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= + = − =⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 进而有: 令 0 0 0 ( ) 0 : 0.13077df x d d α αα + = =得由于较大, 因此还需迭代下去.( )1f x∇ ( ) ( ) ( ) 1 1 1.47692, 0.36923 , 1.52237 Tf x f x ∇ = − ∇ = 2 2(1 2 ) 4(1 8 )α α= − + − Page 9 2 1 1 1 0.73846 1.47692 0.11076 0.42500 0.04616 0.36923 0.11076 x x dα −⎛ ⎞ ⎛ ⎞ ⎛ ⎞= + = + =⎜ ⎟ ⎜ ⎟ ⎜ ⎟−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 进而有: (2) ( ) ( )1 1 1.47692, 0.36923 ,Td f x= −∇ = − 令 1 1 1 ( ) 0 : 0.42500df x d d α αα + = =得类似(1)中的做法, 用精确线搜索求步长, 即可见, 用最速下降法迭代两次并没有到达极小点. ( ) ( ) ( ) 2 2 0.22152, 0.88608 0.91335 Tf x f x ∇ = ∇ = Page 10 又注意到: 证毕. 2 1( ) ( 0.22152)( 1.47692) ( 0.88608)(0.36923) 0Td d = − − + − = ( ) ( )2 2 0.22152, 0.88608 Td f x= −∇ = − −由(2)得: 所以: 下面验证相邻两个搜索方向是正交的. ( ) ( )1 1 1.47692, 0.36923 ,Td f x= −∇ = − ( ) ( )0 0 2, 8 Td f x= −∇ = − − 1 0( ) ( 1.47692)( 2) (0.36923)( 8) 0Td d = − − + − = Page 11收敛性定理收敛性定理定理3.2 设 ( )f x 连续可微，且水平集有界 ( ) ( ){ }0nL x R f x f x= ∈ ≤ 则由精确线搜索的最速下降法产生的序列满足: 或者 ( )lim 0.kk f x→∞ ∇ = ,k 有 ( ) 0,kf x∇ =或者对某个 Page 12优缺点优缺点优点：程序设计简单，计算量小，存储量小。具有整体收敛性，对初始点没有特别要求。缺点：收敛速度慢，尤其在极小点附近，该方法产生的点列逼近函数的极小点越来越慢． ① ( )k kd f x= −∇ 仅反映 ( )xf 在 kx 处的局部性质; 原因： ② 1k kd d +与正交, 即相继两次迭代中搜索方向正交.

                    本文档为【第二节_最速下降法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第二节_最速下降法

你可能还喜欢