58°

02(d)多元无约束优化问题-拟牛顿法

此部分内容接《02(a)多元无约束优化问题-牛顿法》!!!

第三类:拟牛顿法(Quasi-Newton methods)

拟牛顿法的下降方向写为:

${{\mathbf{d}}_{k}}=-{{\mathbf{S}}_{k}}\cdot \nabla f({{\mathbf{x}}_{k}})$

关键就是这里的${{\mathbf{S}}_{k}}$,主要有两拨人对拟牛顿法做出了贡献他们分别针对${{\mathbf{S}}_{k}}$,提出了两种不同的方法;注:下式中的${{\mathbf{\delta }}_{k}}={{\mathbf{x}}_{k+1}}-{{\mathbf{x}}_{k}}$,${{\mathbf{\gamma }}_{k}}=\nabla f({{\mathbf{x}}_{k+1}})-\nabla f({{\mathbf{x}}_{k}})$。

第一拨人:Davidon-Fletcher-Powell (DFP),初始值${{\mathbf{S}}_{0}}=\mathbf{E}$,且

\[{{\mathbf{S}}_{k+1}}={{\mathbf{S}}_{k}}+\frac{{{\mathbf{\delta }}_{k}}\mathbf{\delta }_{k}^{T}}{\mathbf{\delta }_{k}^{T}{{\mathbf{\gamma }}_{k}}}-\frac{{{\mathbf{S}}_{k}}{{\mathbf{\gamma }}_{k}}\mathbf{\gamma }_{k}^{T}{{\mathbf{S}}_{k}}}{\mathbf{\gamma }_{k}^{T}{{\mathbf{S}}_{k}}{{\mathbf{\gamma }}_{k}}}\]

第二拨人:Broyden-Fletcher-Goldfarb-Shanno(BFGS)初始值${{\mathbf{S}}_{0}}=\mathbf{E}$,且

\[{{\mathbf{S}}_{k+1}}={{\mathbf{S}}_{k}}+\left( 1+\frac{\mathbf{\gamma }_{k}^{T}{{\mathbf{S}}_{k}}{{\mathbf{\gamma }}_{k}}}{\mathbf{\gamma }_{k}^{T}{{\mathbf{\delta }}_{k}}} \right)\frac{{{\mathbf{\delta }}_{k}}\mathbf{\delta }_{k}^{T}}{\mathbf{\gamma }_{k}^{T}{{\mathbf{\delta }}_{k}}}-\frac{{{\mathbf{\delta }}_{k}}\mathbf{\gamma }_{k}^{T}{{\mathbf{S}}_{k}}+{{\mathbf{S}}_{k}}{{\mathbf{\gamma }}_{k}}\mathbf{\delta }_{k}^{T}}{\mathbf{\gamma }_{k}^{T}{{\mathbf{\delta }}_{k}}}\]

由于这两拨人所构造${{\mathbf{S}}_{k+1}}$的目的就是,在计算量小的情况下去接近${{H}^{-1}}({{\mathbf{x}}_{k}})$,如果${{H}^{-1}}({{\mathbf{x}}_{k}})$不好(不是正定的),这个两拨人提出的这种近似的方法,也会规避这种情况,保证${{\mathbf{S}}_{k+1}}$是正定的。

我们如何直观的验证,${{\mathbf{S}}_{k+1}}$是接近${{H}^{-1}}({{\mathbf{x}}_{k\text{+1}}})$的呢?我们先拿一个一元函数来试试,对于一元函数来说,它的Hessian阵可以写为:

\[H({{x}_{k+1}})={f}''({{x}_{k+1}})=\frac{{f}'({{x}_{k+1}})-{f}'({{x}_{k}})}{{{x}_{k+1}}-{{x}_{k}}}=\frac{{{\gamma }_{k}}}{{{\delta }_{k}}}\Rightarrow H({{x}_{k+1}})=\frac{{{\gamma }_{k}}}{{{\delta }_{k}}}\]

这里的${{\gamma }_{k}},{{\delta }_{k}}$和前面多元函数的含义一样,Hessian阵的逆矩阵${{H}^{-1}}({{x}_{k+1}})$可以写为:

\[{{H}^{-1}}({{x}_{k+1}})=\frac{{{\delta }_{k}}}{{{\gamma }_{k}}}\Rightarrow {{H}^{-1}}({{x}_{k+1}}){{\gamma }_{k}}={{\delta }_{k}}\]

由式(20)可见,Hessian阵的逆矩阵和${{\gamma }_{k}},{{\delta }_{k}}$之间有这样的关系,那么类比到${{\mathbf{S}}_{k+1}}$和${{\mathbf{\gamma }}_{k}},{{\mathbf{\delta }}_{k}}$之间的关系,如果${{\mathbf{S}}_{k+1}}$是非常接近${{H}^{-1}}({{\mathbf{x}}_{k\text{+1}}})$,那么一定有${{\mathbf{S}}_{k+1}}{{\mathbf{\gamma }}_{k}}={{\mathbf{\delta }}_{k}}$成立。(在工程上大多数情况下第二拨人的方法的效果比第一拨人好)。

可以自行验证${{\mathbf{S}}_{k+1}}{{\mathbf{\gamma }}_{k}}={{\mathbf{\delta }}_{k}}$:………….

 Step3:通过Step2确定下降方向${{\mathbf{d}}_{k}}$之后,$f({{\mathbf{x}}_{k}}+{{\alpha }_{k}}{{\mathbf{d}}_{k}})$可以看成${{\alpha }_{k}}$的一维函数,这一步的主要方法有(Dichotomous search, Fibonacci search, Goldensection search, quadratic interpolation method, and cubic interpolation method);所确定一个步长${{\alpha }_{k}}>0$,${{\mathbf{x}}_{k+1}}={{\mathbf{x}}_{k}}+{{\alpha }_{k}}{{\mathbf{d}}_{k}}$;

Step4: if走一步的距离$\left\| {{\alpha }_{k}}{{\mathbf{d}}_{k}} \right\|<\varepsilon $,则停止并且输出解${{\mathbf{x}}_{k+1}}$;else $k:=k+1$并返回Step2,继续迭代。 

原文链接:https://www.cnblogs.com/duyiExplorer/p/11177231.html

全部评论: 0

    我有话说: