2022年无约束优化算法：牛顿算法参考 .pdf

《2022年无约束优化算法：牛顿算法参考 .pdf》由会员分享，可在线阅读，更多相关《2022年无约束优化算法：牛顿算法参考 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、牛顿算法1. 算法原理牛顿算法的基本思想是利用二次函数近似目标函数，比快速下降法的一次函数更进一步，将次二次函数的极小值点作为新的迭代点。设()fx二次连续可微，求解无约束问题min():nfxfRR若已知求得解*x得一个近似点()kx，对()()kfxs的泰勒展开式取前三项，得到()()()2()1()()()()2kkkTTkqsfxfxssfxs其中，()ksxx，()( )kqs为()fx在()kx点附近的二次近似。设()()kfx正定，()( )kqs有唯一极小值点，也是驻点，使得()()2()()()()0kkkqxfxfxs得()2()1()()()kkksfxfx取(1 )()

2、(kkkxxs或(1)()2()1()()()kkkkxxfxfx由于(1)()2()1()()()kkkkxxfxfx中秋矩阵逆计算复杂，可以通过解方程2()()()()()kkkfxsfx求解()ks。2. 算法步骤给定控制误差0步骤 1：取初始点(0 )x，令0k步骤 2：计算()()kfx，2()()kfx。解2()()()()()kkkfxsfx得解()ks，(1)()()kkkxxs。步骤 3：若()ks，则停机，*(1)kxx；否则1kk，转步骤2. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

3、 - - - - - - 第 1 页，共 7 页 - - - - - - - - - 牛顿算法收敛速度为二阶，是其最大优点， 牛顿算法对正定二次函数一迭代即达最优解，因此具有二次终结性。3. 拟牛顿算法3.1 算法原理拟牛顿算法对牛顿算法有两个重要的改进：一是选用对称正定矩阵可以对搜索方向保证下降性质； 二是改进尺度矩阵，通过逐步迭代修正产生，从而避开逐点计算二阶偏导数的大量计算。H esse阵的修正方法有：D FP法与BF GS法。设()(1)()kkksxx，()(1)()kkkygg，其中()kg为目标函数()fx在()kx点处的梯度量，则D FP修正公式为：()()()()()()(1

4、)()()()()()()kkk Tkkk TkkkTkkk TkHyyHssHHyHyysBF G S修正公式可由D FP修正公式加上下列修正项的乘积()()kk Tww：()()()1/ 2()()()()()()()()()kkkkkTkkkTkk TkksHywyHyysyHy3.2 算法步骤步骤 1：给定初始点( 0)x、初始矩阵( 0)H（通常取单位矩阵） ，计算(0 )g，令0k。步骤 2：令()()()kkkpHg。步骤 3：由一维搜索确定步长k。()()()()0()min()kkkkkfxpfxp步骤 4：若(1)kg，则停机，*(1)kxx；否则令()(1)()kkksx

5、x，()(1)()kkkygg步骤 5：由D FP修正公式()()()()()()(1)()()()()()()kkk Tkkk TkkkTkkk TkHyyHssHHyHyys或由BFG S修正公式()()()1/ 2()()()()()()()()()kkkkkTkkkTkk TkksHywyHyysyHy()()()()()()(1)()()()()()()()()kkkTkkkTkkkkTkTkkkTkHyyHssHHwwyHyys名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

6、第 2 页，共 7 页 - - - - - - - - - 得到(1)kH。令1kk，转步骤2. 4. 程序示例MATLAB实现拟牛顿算法的函数为minfunc。MATLAB函数使用方法：1.目标函数程序.BanaF un m与.BanaF unW ithG radm()()functionfBanaFunx不 含 导 数 解 析 式100 * (2)(1) 2) 2(1(1) 2fxxx,()()functionfgBanaFunWithGradx含 导 数 解 析 式100 * (2)(1) 2) 2(1(1) 2fxxx100 * (4 *(1) 34 *(1) *(2)2 *(1)2;

7、100 * (2 *(2)2 *(1) 2)gxxxxxx2.参数设置_.quasinewton m()DFPDavidonFletcherPowell方法：(arg, , ,optionsoptimsetLeScaleoffHessUpdatedfpgradobjon , 2 5 0 , , , ,M a x F u n E v a l sI n i t i a l H e s s T y p ei d e n t i t yd i s p l ayi t e r()BFGSBroydenFletcherGoldfarbShanno方法：(arg, , , ,optionsoptimsetL

8、eScaleoffHessUpdatebfgsgradobjon,250, , , )MaxFunEvalsInitialHessTypeidentitydisplayiter3.函数计算1）()DFPDavidonFletcherPowell方法(arg, , ,optionsoptimsetLeScaleoffHessUpdatedfpgradobjon , 2 5 0 , , , ,M a x F u n E v a l sI n i t i a l H e s s T y p ei d e n t i t yd i s p l ayi t e r1.9, 2;x初始迭代点,min(,)

9、xfvalexitflagoutputfuncBanaFunWithGradx options名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 计算结果为：First-order Iteration Func-count f(x) Step-size optimality 0 1 267.62 1.23e+003 1 2 214.416 0.000813405 519 2 7 1.42724 0.0227842 7.46 3 9

10、1.24439 0.168253 2.48 4 12 1.06017 91 2.14 5 14 0.957704 0.31929 7.37 6 15 0.948335 1 4.94 7 16 0.941972 1 5.49 8 17 0.934393 1 6.41 9 18 0.929907 1 6.65 10 19 0.918687 1 7.76 11 21 0.881801 10 7.74 12 22 0.814369 1 9.57 13 23 0.807192 1 8.96 14 24 0.799841 1 8.45 15 25 0.788593 1 7.5 16 26 0.780873

11、 1 6.81 17 27 0.77152 1 5.84 18 28 0.764203 1 5.03 19 29 0.756409 1 4.03 First-order Iteration Func-count f(x) Step-size optimality 20 30 0.749959 1 3.16 21 31 0.74343 1 2.19 22 32 0.737722 1 1.35 23 33 0.73179 1 1.59 24 34 0.726297 1 1.82 25 35 0.720311 1 2.09 26 36 0.714479 1 2.37 27 37 0.70775 1

12、3.11 28 38 0.700403 1 4.12 29 39 0.689575 1 5.44 30 44 0.219554 3.96361 2.08 31 45 0.21937 1 1.83 32 48 0.191631 91 0.815 33 49 0.133059 1 1.89 34 50 0.0586042 1 3.21 35 52 0.0577974 0.324832 2.41 36 55 0.0418895 91 1.83 37 56 0.0211574 1 2.42 38 57 0.0150357 1 2.52 名师资料总结 - - -精品资料欢迎下载 - - - - - -

13、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 39 58 0.00830752 1 2.23 First-order Iteration Func-count f(x) Step-size optimality 40 59 0.00337156 1 1.45 41 60 0.000712298 1 0.399 42 61 0.000118493 1 0.131 43 62 6.82877e-006 1 0.0719 44 63 8.52203e-008 1 0.00219 45 64 1.2

14、7563e-009 1 0.00115 Local minimum found.Optimization completed because the size of the gradient is less than the default value of the function tolerance. x = 1.0000 1.0000 fval = 1.2756e-009 exitflag = 1 output = iterations: 45 funcCount: 64 stepsize: 1 firstorderopt: 0.0011 algorithm: medium-scale:

15、 Quasi-Newton line search message: 1x468 char 2）()BFGSBroydenFletcherGoldfarbShanno(arg, , , ,optionsoptimsetLeScaleoffHessUpdatebfgsgradobjon名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - , 250, , , , )MaxFunEvalsInitialHessTypeidentitydi

16、splayiter1.9, 2;x初始迭代点,min(,)xfvalexitflagoutputfuncBanaFunWithGradx options计算结果为：First-order Iteration Func-count f(x) Step-size optimality 0 1 267.62 1.23e+003 1 2 214.416 0.000813405 519 2 7 1.42881 0.0226339 7.5 3 9 1.24422 0.168155 2.48 4 12 1.05985 91 2.14 5 14 0.924515 0.352138 7.59 6 15 0.76

17、9915 1 2.89 7 16 0.587502 1 6.08 8 17 0.449275 1 1.59 9 19 0.357454 0.596324 4.42 10 20 0.268067 1 3.14 11 21 0.182997 1 0.767 12 23 0.151329 0.295687 4.54 13 24 0.112102 1 1.41 14 25 0.0641365 1 2.4 15 26 0.0365927 1 1.99 16 27 0.01879 1 1.01 17 29 0.00945537 0.348436 1.89 18 30 0.00552269 1 1.05 1

18、9 31 0.00168654 1 1.25 First-order Iteration Func-count f(x) Step-size optimality 20 32 0.000869826 1 0.966 21 33 2.87501e-005 1 0.06 22 34 4.97449e-006 1 0.0607 23 35 1.1747e-008 1 0.000357 Local minimum found.Optimization completed because the size of the gradient is less than the default value of

19、 the function tolerance. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - x = 0.9999 0.9998 fval = 1.1747e-008 exitflag = 1 output = iterations: 23 funcCount: 35 stepsize: 1 firstorderopt: 3.5671e-004 algorithm: medium-scale: Quasi-Newton line search message: 1x468 char 两种算法比较：BFGS法其迭代次数、目标函数的计算次数都小于D FP法，相比较而言BF G S法在bana函数上效果优于D FP法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -