最速下降法课件.ppt

1、n4.1 非线性规划数学模型非线性规划数学模型n4.2 凸函数和凸规划凸函数和凸规划n4.3 一维搜索一维搜索n4.4 无约束优化问题的解法无约束优化问题的解法第四章第四章 无约束最优化问题无约束最优化问题第四节第四节 无约束优化问题的解法无约束优化问题的解法n最速下降法最速下降法nNewton法法n拟拟Newton法法n共轭梯度法共轭梯度法 第四章第四章 无约束最优化问题无约束最优化问题一一.最速下降法最速下降法n收敛性问题的基本概念收敛性问题的基本概念n最速下降法的迭代原理最速下降法的迭代原理n最速下降法的迭代步骤最速下降法的迭代步骤n最速下降法的举例最速下降法的举例n最速下降法的收敛结论

2、最速下降法的收敛结论 )(minXfnRX)(NP无约束问题无约束问题4-41.1.收敛性问题的基本概念收敛性问题的基本概念定义定义4-94-9若序列若序列 ，对于，对于 ，存在正整数，存在正整数()kX0 (),N 当当 时，有时，有 ，即，即kN()kXX ()0,kkXX ().kkXX 则称则称 收敛于收敛于 ，记为，记为()kXX 无约束问题无约束问题4-4X 0X1X2X3X4XkXmin()nXRf X()kf X()kkXX 定义定义4-104-10,0)(kkXX若若.)(XXkk则则1.1.收敛性问题的基本概念收敛性问题的基本概念若若 收敛于收敛于 ，且满足，且满足()kX

3、X(1)()lim,kpkkXXXX 则则 p 称为称为 收敛于收敛于 的阶。的阶。()kXX 当当 p=1 时，称为时，称为一阶收敛一阶收敛；当当 p=2 时，称为时，称为二阶收敛二阶收敛；当当 时，称为时，称为超线性收敛超线性收敛；12p 无约束问题无约束问题4-4 当当 时，时，当当 p=2 时，时，同阶无穷小同阶无穷小若若 收敛于收敛于 ，且满足，且满足()kXX(1)()lim,kpkkXXXX 则则p称为称为 收敛于收敛于 的阶。的阶。()kXX,0)(kkXX若若.)(XXkk则则2(1)()kkXXXX 与与 XXk)(XXk)1(1.001.00001.0810 XXk)2(

4、XXk)3(XXk)4(1610 1.1.收敛性问题的基本概念收敛性问题的基本概念1,k 2(1)()kkXXXX定义定义4-104-10无约束问题无约束问题4-4 当当 时，时，当当 p=1 时，时，同阶无穷小同阶无穷小若若 收敛于收敛于 ，且满足，且满足()kXX(1)()lim,kpkkXXXX 则则p称为称为 收敛于收敛于 的阶。的阶。()kXX,0)(kkXX若若.)(XXkk则则(1)()kkXXXX 与与 XXk)(XXk)1(1.00.090.050.02 XXk)2(XXk)3(XXk)4(0.011.1.收敛性问题的基本概念收敛性问题的基本概念1,k (1)()kkXXXX

5、 定义定义4-104-10无约束问题无约束问题4-4定义定义4-104-10,0)(kkXX若若.)(XXkk则则1.1.收敛性问题的基本概念收敛性问题的基本概念若若 收敛于收敛于 ，且满足，且满足()kXX(1)()lim,kpkkXXXX 则则p称为称为 收敛于收敛于 的阶。的阶。()kXX 当当 p=1 时，称为时，称为一阶收敛一阶收敛；当当 p=2 时，称为时，称为二阶收敛二阶收敛；当当 时，称为时，称为超线性收敛超线性收敛；12p 无约束问题无约束问题4-4最速下降法最速下降法Newton法法拟拟Newton法法定义定义4-124-12 若某算法对于任意正定二次目标函数若某算法对于任

6、意正定二次目标函数,从任意初始点从任意初始点出发出发,都能经过都能经过有限次迭代有限次迭代达到其极小点达到其极小点,则该算法称则该算法称为具有为具有二次终止性二次终止性的算法或二次收敛算法的算法或二次收敛算法.1.1.收敛性问题的基本概念收敛性问题的基本概念),(21nxxxfcXbQXXTT 21结论：结论：1()2TTf XX QXb Xc bQX1 当当 Q 为正定阵时，称为正定阵时，称 f(X)为正定二次函数。为正定二次函数。正定二次函数正定二次函数 有唯一有唯一全局极小点：全局极小点：无约束问题无约束问题4-4一一.最速下降法最速下降法n收敛性问题的基本概念收敛性问题的基本概念n最速

7、下降法的迭代原理最速下降法的迭代原理n最速下降法的迭代步骤最速下降法的迭代步骤n最速下降法的举例最速下降法的举例n最速下降法的收敛结论最速下降法的收敛结论 )(minXfnRX)(NP无约束问题无约束问题4-4是是X(k)处函数值下降最快的方向。处函数值下降最快的方向。当当 时，时，p(k)是是 f(X)在在X(k)处的处的下降方向下降方向。函数函数f(X)在在X(k)处的负梯度方向处的负梯度方向)()(kXf 梯度的性质：梯度的性质：2.2.迭代原理迭代原理)()()()()()()()()(kTkkkkpXfXfpXf证明：证明：)()()()(kTkpXf充充分分小小时时)()()()(

8、)()()(hhxfxfhxfkkk 0 0)()()()()()()()()(kTkkkkpXfXfpXf结论：结论：()()()0kTkf Xp )()(kXf)(kP)(kP)(kX)(kP)(kP一元函数泰勒公式：一元函数泰勒公式：1cos()kX()()kkXp ()kp 无约束问题无约束问题4-42.2.迭代原理迭代原理),(00Xfp 0 0 0p0X000pX )(min000pXf 0001pXX )()(10XfXf)(minXfnRX),(000pXf ,0X最优步长最优步长无约束问题无约束问题4-4,0X),(00Xfp 0 0p0X)(min000pXf 0001pX

9、X )(minXfnRX),(000pXf 最速下降法迭代原理：最速下降法迭代原理：0(1,1),TX 42122xx 312()(4,2)Tf Xxx 00()(4,2)Tpf X 00141 4121 2Xp 0042()(1 4)(1 2)2()f XpF 000min()()f XpF 一维搜索找极小点一维搜索找极小点 ：1)确定确定0,1,精度精度0.10 2)用用0.618法得到法得到00.34375 1X040.53184()F 无约束问题无约束问题4-4,0X),(00Xfp 0 0p0X)(min000pXf 0001pXX )(minXfnRX),(000pXf 最速下降法

10、迭代原理：最速下降法迭代原理：0(1,1),TX 42122xx 312()(4,2)Tf Xxx 00()(4,2)Tpf X 00141 4121 2Xp 0042()(1 4)(1 2)2()f XpF 000min()()f XpF 00.34375 1(1,1)0.34375(4,2)(0.375,0.3125)TTTX 10()2.11743()4f Xf X 1X无约束问题无约束问题4-4,0X),(00Xfp 0 0p0X1X)(min000pXf 0001pXX )()(10XfXf)(minXfnRX),(000pXf 1p,1X),(11Xfp )(min110pXf )

11、,(111pXf 1112pXX 111pX 1)(2Xf 1 2.2.迭代原理迭代原理0 最优步长最优步长最优步长最优步长无约束问题无约束问题4-4,0X),(00Xfp 0 0p0X1X)(min000pXf 0001pXX )()(10XfXf)(minXfnRX),(000pXf 1p,1X),(11Xfp )(min110pXf ),(111pXf 1112pXX 2X)(2Xf,kX),(kkXfp )(min0kkpXf ),(kkkpXf kkkkpXX 11()()kkf Xf X XXkk)(411)Th 线性收敛线性收敛2.2.迭代原理迭代原理1 1 0 最优步长最优步长

12、最优步长最优步长,)()(严严格格kXf(410),Th 得到一个点列：得到一个点列：01(),kXXX可以证明：可以证明：无约束问题无约束问题4-4,0X),(00Xfp )(min000pXf 0001pXX )(minXfnRX),(000pXf ,1X),(11Xfp )(min110pXf ),(111pXf 1112pXX ,kX),(kkXfp )(min0kkpXf ),(kkkpXf kkkkpXX 1,:)(10kXXX得得到到一一个个点点列列2.2.迭代原理迭代原理()()kf X 严严格格证明：证明：)()()()()()()()()(kTkkkkpXfXfpXf)()

13、()()(kTkpXf充充分分小小时时0 0)()()()()()()()()(kTkkkkpXfXfpXf0,)()(严严格格kXf XXkk)(0)(2)(kXf)()()()()()()(kTkkTkXfXfpXf ()()()()()0kkkkf Xpf X 1kX 无约束问题无约束问题4-4一一.最速下降法最速下降法n收敛性问题的基本概念收敛性问题的基本概念n最速下降法的迭代原理最速下降法的迭代原理n最速下降法的迭代步骤最速下降法的迭代步骤n最速下降法的举例最速下降法的举例n最速下降法的收敛结论最速下降法的收敛结论 )(minXfnRX)(NP无约束问题无约束问题4-4无约束问题无约

14、束问题4-43.3.迭代步骤迭代步骤0:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp )()(min:4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 0 k),(00Xfp )(min000pXf 0001pXX ),(000pXf ),(11Xfp )(min110pXf ),(111pXf 1112pXX 否否则则若若是是取取,?)0()0(XXp 1

15、k否否则则若若是是取取,?)1()1(XXp 2 k),(22Xfp 否否则则若若是是取取,?)2()2(XXp )(min220pXf ),(222pXf 2223pXX 3.3.迭代步骤迭代步骤0:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp )()(min:4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释：,)(时时当当 XXk)()()(X

16、fXfk0 0)()()(XfXfk )()(kXf )(kp(一阶必要条件一阶必要条件)(minXfnRX 10 停机准则：停机准则：设设 连续连续(即即 f(X)连续可微连续可微)()f X 无约束问题无约束问题4-4()0kXX 0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp 0:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算)()(min,4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释

17、：)()(min)()()()(0kkkkkpXfpXf )()(k ()()()()()kkTkf Xpp )(0k )()1()(kTkpXf (4 11)k)(kp)1(kX)(kX)()1(kXf3.3.迭代步骤迭代步骤一维搜索最优解的梯度一维搜索最优解的梯度 与搜索方向与搜索方向 正交正交(1)()kf X ()kp20 结论：结论：证明：证明：()()()()()kkTkkkf Xpp 无约束问题无约束问题4-40)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp 0:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0k

18、kXfp 计计算算)()(min,4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释：最速下降法的任何两个相邻搜索方向最速下降法的任何两个相邻搜索方向正交正交(垂直垂直)()(min)()()()(0kkkkkpXfpXf )()(k ()()()()()kkTkf Xpp )(0k )()1()(kTkpXf (4 11)0)()1(kTkppk)(kp)1(kX)1(kp)(kX)()1(kXf3.3.迭代步骤迭代步骤30 结论：结论：无约束问题无约束问题4-40:,0)(,1)0(

19、0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp )()(min,4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释：cXbQXXXfTT 21)()()()()(kTkkTkkQpppg (4 13)()()(kkXfg 令令3.3.迭代步骤迭代步骤40 将一维搜索用于正定二次函数：将一维搜索用于正定二次函数：则可以得到则可以得到 的表达式：的表达式：k 无约束问题无约

20、束问题4-4(4 13)证明：证明：bQXXfgkkk )1()1()1()(bQXk )(bpXQkkk )()()(bQpQXkkk )()()()()(kkXfg )()(kkkQpg )()()()(kTkkkpQpg )()()()(kTkkkTkQpppg )()1(0kTkpg )()()()(kTkkTkkQpppg 0)()()1(kTkpXf)()()1(kkkkpXX 3.3.迭代步骤迭代步骤cXbQXXXfTT 21)()()()(kkXfg 令令40 将一维搜索用于正定二次函数：将一维搜索用于正定二次函数：则可以得到则可以得到 的表达式：的表达式：k()f XQXb

21、注释：注释：该公式具有普遍性该公式具有普遍性无约束问题无约束问题4-40:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp )()(min,4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释：cXbQXXXfTT 21)()()()()(kTkkTkkQpppg (4 13)()()(kkXfg 令令3.3.迭代步骤迭代步骤40 将一维搜索用于正定二次函

22、数：将一维搜索用于正定二次函数：则可以得到则可以得到 的表达式：的表达式：k)(minXfnRX 无约束问题无约束问题4-40:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp )()(min,4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释：cXbQXXXfTT 21)()()()()(kTkkTkkQpppg )133()()(kkgp )143(

23、)()()()(kTkkTkkQgggg)()()(kkXfg 令令3.3.迭代步骤迭代步骤50 将最速下降法用于正定二次函数：将最速下降法用于正定二次函数：则可以得到则可以得到 的表达式：的表达式：k 无约束问题无约束问题4-40:,0)(,1)0(0 kX令令精精度度容容许许误误差差取取初初始始点点)(2)()(0kkXfp 计计算算0)()(04,?3否否则则转转取取若若是是迭迭代代终终止止检检验验kkXXp )()(min,4)()()()(00一一维维搜搜索索求求最最优优步步长长kkkkkkpXfpXf 0)()()1(02,1:,5转转令令令令 kkpXXkkkk 注释：注释：3.

24、3.迭代步骤迭代步骤50 最速下降法，最速下降法，Newton法，拟法，拟Newton法，共轭梯度法的区别法，共轭梯度法的区别就是就是搜索方向搜索方向p(k)取得不同。取得不同。()()()kkpf X ()()1()()()kkkpG Xf X ()()()()kkkpHf X ()()(1)1()kkkkpf Xp 无约束问题无约束问题4-4一一.最速下降法最速下降法n收敛性问题的基本概念收敛性问题的基本概念n最速下降法的迭代原理最速下降法的迭代原理n最速下降法的迭代步骤最速下降法的迭代步骤n最速下降法的举例最速下降法的举例n最速下降法的收敛结论最速下降法的收敛结论 )(minXfnRX)

25、(NP无约束问题无约束问题4-44.4.举例举例例例4-104-10解：解：用最速下降法求用最速下降法求 的极小点，的极小点，2212()4f Xxx 4)0(10,)1,1(TX迭代两次。迭代两次。(0,0)TX 无约束问题无约束问题4-44.4.举例举例例例4-104-10解：解：QXXxxXfT21)82(21)(2221 8002Q 2182)()(xxXfXg用最速下降法求用最速下降法求 的极小点，的极小点，2212()4f Xxx 4)0(10,)1,1(TX迭代两次。迭代两次。无约束问题无约束问题4-4(0,0)TX )0()()2kkpf X ()()00?,43kkpXX 若

26、若是是否否则则转转(1)()()00,:125,kkkkXXpkk 转转()()0()()0,min()()()4kkkkkkf Xpf Xp 求求一一维维搜搜索索()()()()04k Tkkk TkgppQp 解：解：8002Q 2182)()(xxXfXg1 82)2()0()0(gp)(68 太太大大 22)0()8()2()3(p(0)(0)0(0)(0)(4)TTgppQp 13077.052068 828002)8,2(82)8,2(QXXxxXfT21)82(21)(2221 (0)4(1,1),10TX 0k 无约束问题无约束问题4-44)0(10,)1,1(TX)0()()

27、2kkpf X ()()00?,43kkpXX 若若是是否否则则转转(1)()()00,:125,kkkkXXpkk 转转()()0()()0,min()()()4kkkkkkf Xpf Xp 求求一一维维搜搜索索()()()()04k Tkkk TkgppQp 解：解：8002Q 2182)()(xxXfXg1 82)2()0()0(gp)(68 太太大大 22)0()8()2()3(p13077.0)4(0 04616.073846.0)0(0)0()1()5(pXX 8213077.011QXXxxXfT21)82(21)(2221 0k 1k 无约束问题无约束问题4-4)0()()2k

28、kpf X ()()00?,43kkpXX 若若是是否否则则转转(1)()()00,:125,kkkkXXpkk 转转()()0()()0,min()()()4kkkkkkf Xpf Xp 求求一一维维搜搜索索()()()()04k Tkkk TkgppQp 解：解：8002Q 2182)()(xxXfXg2 39623.047692.1)2()1()1(gp52237.1)3()1(p 04616.073846.0)1(X(1)(1)1(1)(1)(4)0.425TTgppQp )1(1)1()2()5(pXX 39623.047692.1425.004616.073846.0 11076.

29、011076.0QXXxxXfT21)82(21)(2221 1k 2k 无约束问题无约束问题4-4)0()()2kkpf X ()()00?,43kkpXX 若若是是否否则则转转(1)()()00,:125,kkkkXXpkk 转转()()0()()0,min()()()4kkkkkkf Xpf Xp 求求一一维维搜搜索索()()()0)(4k Tkkk TkgggQg 解：解：8002Q 2182)()(xxXfXg3 88608.022152.0)2()2()2(gp91335.0)3()2(p)2(X 11076.011076.0（太大）继续迭代。（太大）继续迭代。最速下降法收敛速度很

30、慢。最速下降法收敛速度很慢。注释：注释：QXXxxXfT21)82(21)(2221 2k 无约束问题无约束问题4-4例例4-104-10注释：注释：本例的计算结果如图本例的计算结果如图4-14(P156).迭代点在向极小点靠迭代点在向极小点靠近的过程中形成一条锯齿折线近的过程中形成一条锯齿折线,这种现象称为这种现象称为锯齿现象锯齿现象.这是由于最速下降法的这是由于最速下降法的任何两个相邻搜索方向正交任何两个相邻搜索方向正交.因因此此,从直观上可以看到从直观上可以看到,在远离极小点的地方在远离极小点的地方,每次迭代每次迭代可使目标函数值有较大的下降可使目标函数值有较大的下降,但但越接近极小点越

31、接近极小点,由于锯由于锯齿现象齿现象,函数值下降速度显著变慢函数值下降速度显著变慢.优点：优点：计算简单计算简单,存储量小存储量小.缺点：缺点：由于锯齿现象由于锯齿现象,迭代后期收敛速度变慢迭代后期收敛速度变慢.4.4.举例举例用最速下降法求用最速下降法求 的极小点，的极小点，2212()4f Xxx 4)0(10,)1,1(TX迭代两次。迭代两次。无约束问题无约束问题4-4一一.最速下降法最速下降法n收敛性问题的基本概念收敛性问题的基本概念n最速下降法的迭代原理最速下降法的迭代原理n最速下降法的迭代步骤最速下降法的迭代步骤n最速下降法的举例最速下降法的举例n最速下降法的收敛结论最速下降法的收

32、敛结论 )(minXfnRX)(NP无约束问题无约束问题4-45.5.最速下降法的收敛结论最速下降法的收敛结论 XXkk)(线性收敛线性收敛最速下降法所产生的迭代点列最速下降法所产生的迭代点列是是 的局部最优解的局部最优解X min()nXRf X 无约束问题无约束问题4-4(411)Th (410)Th 一一.最速下降法最速下降法n收敛性问题的基本概念收敛性问题的基本概念n最速下降法的迭代原理最速下降法的迭代原理n最速下降法的迭代步骤最速下降法的迭代步骤n最速下降法的举例最速下降法的举例n最速下降法的收敛结论最速下降法的收敛结论 )(minXfnRX)(NP作业：作业：P245 14P245 14作业：作业：P155 14P155 14