《无约束优化算法：牛顿算法》由会员分享，可在线阅读，更多相关《无约束优化算法：牛顿算法（7页珍藏版）》请在金锄头文库上搜索。
1、牛顿算法1. 算法原理牛顿算法的基本思想是利用二次函数近似目标函数，比快速下降法的一次函数更进一步 将次二次函数的极小值点作为新的迭代点。设 f (x) 二次连续可微，求解无约束问题m in f ( x )f : Rn R若已知求得解x*得一个近似点x(k)，对f (x(k) + s)的泰勒展开式取前三项，得到1q( k)( s) = f (x(k) + V f (x(k) t s + sT V 2 f (x(k) s2其中，s = x - x(k)， q(k)(s)为f (x)在x(k)点附近的二次近似。设Vf (x(k)正定，q(k)(s)有唯一极小值点，也是驻点，使得V q(k) (x)
2、 = V f (x(k) + V2 f (x(k) s = 0得s(k) = - V2 f (x(k)-1V f (x(k)取x(k + 1 = x k( +)s 或 x(k+i)= x(k) 一 V2 f (x(k)-1Vf (x(k)由于 x(k+1) = x(k) -V2 f(x(k)-1Vf(x(k) 中秋矩阵逆计算复杂，可以通过解方程V2 f(x(k)s(k) = -V f(x(k)求解s (k)。2. 算法步骤给定控制误差 0步骤1：取初始点x()，令k = 0步骤 2：计算 Vf (x(k)，V2f (x(k)。解 V 2 f(x(k)s(k) = -V f(x(k)得解 s(k
3、) ， x(k+1) = x(k) + s(k)。步骤3：若s(k) ,贝I停机，x* = x(k+1);否则k = k + 1，转步骤2.牛顿算法收敛速度为二阶，是其最大优点，牛顿算法对正定二次函数一迭代即达最优解， 因此具有二次终结性。3. 拟牛顿算法3.1 算法原理 拟牛顿算法对牛顿算法有两个重要的改进：一是选用对称正定矩阵可以对搜索方向保证 下降性质；二是改进尺度矩阵，通过逐步迭代修正产生，从而避开逐点计算二阶偏导数的大 量计算。Hesse阵的修正方法有：DFP法与BFGS法。设 s(k)= x(k +i) - x(k), y(k)= g(k+i) - g(k)，其中 g(k)为目标函
4、数 f (x)在 x(k)点处的梯度量，则 DFP 修正公式为：H(k)y(k)y(k)TH (k) s(k)s(k)TH (k+1)= H (k) +y(k)T H (k)y(k)y(k)T s(k)BFGS修正公式可由DFP修正公式加上下列修正项的乘积w(k)w(k)t :w(k)=(y (k) TH( k) y (k )/2s(k)y(k)Ts(k)3.2 算法步骤 步骤1给定初始点X(0)、初始矩阵H(0)(通常取单位矩阵)，计算g (0)，令k = 0。步骤 2：令 p(k) = H (k)g(k)。步骤3：由一维搜索确定步长a。kf (x(k) + a p(k) = kmin f
5、(x(k) + a p(k)a o步骤4：若|g (k +1) | w ,则停机，X* = X(k +1)；否则令s(k) = X(k+1) X(k)， y(k) = g(k+1) g(k)步骤 5：由 DFP 修正公式H(k)y(k)y(k)TH (k) s(k)s(k)TH (k+1) = H (k) +y(k)T H (k)y(k) y(k)Ts(k)或由 BFGS 修正公式w(k)=(y (k) TH (k) y (k) )/2S(k)y(k)Ts(k)y (k)TH (k)y (k)丿H (k)y(k)y(k)TH(k) s(k)s(k)TH (k +1) = H (k ) + w
6、(k ) w (k ) T得到H(k+i)。令k = k + 1，转步骤2.4. 程序示例MATLAB 实现拟牛顿算法的函数为 f min unc 。MATLAB 函数使用方法：1. 目标函数程序 B anaF un .m 与 B anaF unW ithG rad .mfunctionf = BanaFun (x)(不含导数解析式)f = 100 * (x (2) x (1)人 2)人 2 + (1 x (1)人 2function f, g = BanaFunWithGrad (x)(含导数解析式)f = 100 * (x (2) x (1) A 2) A 2 + (1 x (1) A 2
7、g = 100 *(4 * x (1)人 3 4* x (1)* x (2) + 2* x (1) 2;100 * (2 * x (2) 2* x (1)人 2)2. 参数设置 quasi _ newton .mDFP ( Davidon Fletcher Powell ) 方法：options = optimset ( L arg eScale , off , HessUpdate , dfp , gradobj ,on ,M axFunEva, 2ls50, InitialHes,sType ,iyd e int teirt y, displaBFGS ( Broyden Fletcher
8、 Goldfarb Shanno ) 方法：options = optimset ( L arg eScale , off , HessUpdate , bfgs , g radobj ,on , MaxFunEvals , 250, InitialHessType , identity , display , iter )3. 函数计算1) DFP ( Davidon Fletcher Powell ) 方法options = optimset ( L arg eScale , off , HessUpdate , dfp , gradobj ,on ,M axFunEva, 2ls50,
9、InitialHes,sType ,iyd e int teirt y, displa x = 1.9, 2; 初始迭代点 x, fval , exitflag , output = f min unc ( BanaFunWithGrad, x, options )计算结果为：First-orderIterationFunc-countf(x)Step-sizeoptimality01267.621.23e+00312214.4160.000813405519271.427240.02278427.46391.244390.1682532.484121.06017912.145140.9577
10、040.319297.376150.94833514.947160.94197215.498170.93439316.419180.92990716.6510190.91868717.7611210.881801107.7412220.81436919.5713230.80719218.9614240.79984118.4515250.78859317.516260.78087316.8117270.7715215.8418280.76420315.0319290.75640914.03First-orderIterationFunc-countf(x)Step-sizeoptimality2
11、0300.74995913.1621310.7434312.1922320.73772211.3523330.7317911.5924340.72629711.8225350.72031112.0926360.71447912.3727370.7077513.1128380.70040314.1229390.68957515.4430440.2195543.963612.0831450.2193711.8332480.191631910.81533490.13305911.8934500.058604213.2135520.05779740.3248322.4136550.0418895911
12、.8337560.021157412.4238570.015035712.5239580.0083075212.23First-orderIterationFunc-countf(x) Step-sizeoptimality40590.0033715611.4541600.00071229810.39942610.00011849310.13143626.82877e-00610.071944638.52203e-00810.0021945641.27563e-00910.00115Local minimum found.Optimization completed because the s
13、ize of the gradient is less than the default value of the function tolerance. x =1.0000 1.0000fval =1.2756e-009exitflag =1output =iterations: 45 funcCount: 64 stepsize: 1 firstorderopt: 0.0011 algorithm: medium-scale: Quasi-Newton line search message: 1x468 char2) BFGS (Broyden 一 Fletcher 一 Goldfarb 一 Shanno )options = optimset ( L arg eScale , off , HessUpdate ,bfgs , g radobj , on ,x = -1.9, 2;初始迭代点First-orderx, fval , exitflag , output = f
