手机网站制作良心服务,香山网站建设,做网站服务器空间,企业网站建设 邮箱拟牛顿法分为五部分来讲#xff0c;本文这部分作为引言#xff0c;第二部分讲Hessian矩阵逆矩阵的近似#xff0c;第三部分秩1修正公式#xff0c;第四部分为DFP算法#xff0c;最后BFGS算法。 牛顿法是一种具有较高实用性的优化问题的求解方法。牛顿法如果收敛… 拟牛顿法分为五部分来讲本文这部分作为引言第二部分讲Hessian矩阵逆矩阵的近似第三部分秩1修正公式第四部分为DFP算法最后BFGS算法。 牛顿法是一种具有较高实用性的优化问题的求解方法。牛顿法如果收敛收敛阶数至少是2。但是当目标函数为一般性的非线性函数时牛顿法就不能保证从任意起始点x(0)\boldsymbol{x}^{(0)}收敛到函数的极小点。也就是说如果初始点x(0)\boldsymbol{x}^{(0)}不足够接近极小点那么牛顿法可能不具备下降性。 牛顿法的基本思路是在每次迭代中利用二次型函数的局部近似目标函数ff，并求解近似函数的极小点作为下一个迭代点，迭代公式为：
x(k+1)=x(k)−F(x(k))−1g(k)
\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} - \boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1}\boldsymbol{g}^{(k)}对上式进行适当修正可以保证牛顿法具有下降性
x(k1)x(k)−αkF(x(k))−1g(k)\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} - \alpha_k\boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1}\boldsymbol{g}^{(k)}其中αk\alpha_k为步长合理确定步长使得 f(x(k1))f(x(k))f(\boldsymbol{x}^{(k+1)} ) 牛顿法的另外一个缺陷是必须计算Hessian矩阵F(x(k))\boldsymbol{F}(\boldsymbol{x}^{(k)})和求解方程F(x(k))d(k)−g(k)\boldsymbol{F}(\boldsymbol{x}^{(k)})\boldsymbol{d}^{(k)}=-\boldsymbol{g}^{(k)},即d(k)−F(x(k))−1g(k)\boldsymbol{d}^{(k)}=-\boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1}\boldsymbol{g}^{(k)},为了避免求解F(x(k))(−1)\boldsymbol{F}(\boldsymbol{x}^{(k)})^{(-1)}这种矩阵求逆运算可以通过设计F(x(k))(−1)\boldsymbol{F}(\boldsymbol{x}^{(k)})^{(-1)}的近似矩阵来代替这就是拟牛顿法的基本思路。 命题 函数ff是一阶连续可微f∈C1,x(k)∈Rn,g(k)=∇f(x(k))≠0,Hkf \in \mathcal{C}^1, \boldsymbol{x}^{(k)} \in \mathbb{R}^n, \boldsymbol{g}^{(k)}=\nabla f(\boldsymbol{x}^{(k)}) \ne \boldsymbol{0}, \boldsymbol{H}_k是n×nn \times n对称正定实矩阵 如果令x(k1)x(k)−αkHkg(k)\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} - \alpha_k\boldsymbol{H}_k\boldsymbol{g}^{(k)},其中αkargminα≥0f(x(k)−αkHkg(k))\alpha_k =\arg \min_{\alpha \ge 0}f(\boldsymbol{x}^{(k)}-\alpha_k\boldsymbol{H}_k\boldsymbol{g}^{(k)}),那么有αk0,f(x(k1))f(x(k))\alpha_k > 0, f(\boldsymbol{x}^{(k+1)}) 。 在拟牛顿法中构造Hessian矩阵逆矩阵的近似矩阵时只需要用到目标函数值和梯度。因此只要确定了合适的近似矩阵Hk\boldsymbol{H}_k的构造方法那么迭代过程中不需要任何涉及Hessian矩阵以及现行方程求解的计算工作。
