牛顿法最优化例题_牛顿法最优化例题

牛顿法最优化例题_牛顿法最优化例题最优化方法总结——梯度下降法、最速下降法、牛顿法、高斯牛顿法、LM法、拟牛顿法

目录

1 最优化方法的结构

2 常用最优化方法对比分析

3 相关计算公式


1 最优化方法的结构

        最优化问题的一般形式为:

min f(x)
s.t. x\in X

其中x为决策变量,f(x)是目标函数,X为约束集或可行域。特别地,如果X=R^n,则最优化问题成为无约束最优化问题。

        最优化方法通常采用迭代法求它的最优解,其基本思想是:给定一个初始点x_0,按照某一迭代规则产品一个点列{
x_n},使得当{
x_n}是有穷点列时,其最后一个点是最优化模型问题的最优解。迭代规则由迭代公式决定,迭代公式的基本表示形式如下:

x_{k+1}=x_k+\alpha _kd_k

        式中,\alpha _k为步长因子,d_k为搜索方向。在最优化算法中,搜索方向d_kfx_k点处的下降方向,即:

f(x_k+\alpha _kd_k)<f(x_k)

        最优化方法的基本结构如下:

  • 给定初始点x_0
  • 确定搜索方向d_k,即按照一定规则,构造 fx_k点处的下降方向作为搜索方向;
  • 确定步长因子\alpha _k,使目标函数有某种意义的下降;
  • 令 x_{k+1}=x_k+\alpha _kd_k,若x_{k+1}满足某种终止条件,则停止迭代,得到近似最优解x_{k+1}.否则,重复以上步骤。

2 常用最优化方法对比分析

        从迭代公式可知,最优化方法求解时的关键就是构造搜索方向d_k和步长因子\alpha _k。不同的搜索方向和不同的步长因子构成了不同的方法,常见的最优化方法有梯度下降法、最速下降法、牛顿法、高斯牛顿法、LM法、拟牛顿法,对应的迭代公式总结如下表:

迭代公式
梯度下降法 x^{k+1}=x^k- \alpha \triangledown f(x^k)
最速下降法 x^{k+1}=x^k- \alpha_k \triangledown f(x^k)
牛顿法 x^{k+1}=x^k- \alpha_kH(x^k)^{-1} \triangledown f(x^k)
高斯牛顿法 x^{k+1}=x^k- \alpha_kG(x^k)^{-1} \triangledown f(x^k)
LM法 x^{k+1}=x^k- \alpha_kJ(x^k)^{-1} \triangledown f(x^k)
拟牛顿法 x^{k+1}=x^k- \alpha_kB(x^k)^{-1} \triangledown f(x^k)

对比分析:

梯度下降法 最速下降法 牛顿法 高斯牛顿法 LM法 拟牛顿法
步长因子 \alpha \alpha _k \alpha _k \alpha _k

 \alpha _k

 \alpha _k

搜索方向 -\triangledown f(x^k) -\triangledown f(x^k) -H(x^k)^{-1}\triangledown f(x^k) -G(x^k)^{-1}\triangledown f(x^k) -J(x^k)^{-1}\triangledown f(x^k) -B(x^k)^{-1}\triangledown f(x^k)
参数说明

 ① 步长因子\alpha为一个固定值,工程师预先设定;② 搜索方向为梯度方向 \triangledown f(x^k)的反方向

步长因子是一个变化的常数\alpha _k,每一次迭代需要重新计算。通过一位搜索算法得到 H为二阶偏导矩阵,即海塞矩阵

G矩阵用来近似替代H矩阵,G=\triangledown f\triangledown f^T

J矩阵替代G矩阵,J=G+uI,u为常数,I为单位矩阵 B矩阵用来近似替代H矩阵,B矩阵的形式有多种
目的 求解最优化问题的基本方法 梯度下降法的一种具体的实现方式 提高收敛速度 减小计算量 解决G矩阵不正定的问题 减小计算量以及H矩阵不正定的问题

 几种算法之间的关系总结如下:

牛顿法最优化例题_牛顿法最优化例题

  • 最速下降法是梯度下降法的一种具体实现方式。梯度下降法的步长因子是固定值,最速下降法的步长因子 是一个变化的常数\alpha _k ,即由一位搜索得到步长因子\alpha _k,使得

牛顿法最优化例题_牛顿法最优化例题0″>

  • 牛顿法可以看成相对于梯度下降法的改进,提高了收敛速度。梯度下降法/最速下降法在确定搜索方向的时候,只用到了一阶导数,因此它的收敛速度是一阶收敛,收敛速度较慢。而牛顿法用到了二阶偏导,它的收敛速度是二阶收敛,收敛速度比梯度下降法快。
  • 高斯牛顿法是相对于牛顿法改进,简化了计算。牛顿法中的H矩阵需要计算目标函数的二阶偏导,计算量巨大,高斯牛顿法采用G矩阵替代H矩阵,大大减小了计算量。
  • LM法是相对于高斯牛顿法的改进,解决G矩阵正定问题。高斯-牛顿法的逼近步长由矩阵G的逆矩阵决定,如果矩阵G非正定,那么其逆矩阵不一定存在,即使存在逆矩阵,也会导致逼近方向出现偏差,严重影响优化方向。LM法正是为了解决矩阵G的正定问题而提出的,其将矩阵G加上单位矩阵I的倍数来解决正定问题。
  • LM法相当于最速下降法和高斯牛顿法的结合体。当u很小时,矩阵J接近矩阵G,其相当于高斯-牛顿法,此时迭代收敛速度快,当u很大时,其相当于梯度下降法,此时迭代收敛速度慢。因此LM算法即具有高斯-牛顿法收敛速度快、不容易陷入局部极值的优点,也具有梯度下降法稳定逼近最优解的特点。
  • 拟牛顿法是相对于牛顿法的改进。牛顿法虽然收敛速度快,但是需要计算海塞矩阵的逆矩阵 H^{-1} ,而且有时目标函数的海塞矩阵无法保持正定,从而使得牛顿法失效。为了克服这两个问题,人们提出了拟牛顿法。这个方法的基本思想是:不用二阶偏导数而构造出可以近似海塞矩阵(或海塞矩阵的逆)的正定对称阵。不同的构造方法就产生了不同的拟牛顿法,常用的拟牛顿算法有:DFP算法、BFGS算法、L-BFGS算法。严格意义上讲高斯牛顿法和LM法都属于拟牛顿法。

3 相关计算公式

牛顿法最优化例题_牛顿法最优化例题

牛顿法最优化例题_牛顿法最优化例题

牛顿法最优化例题_牛顿法最优化例题

参考链接:

最优化算法之牛顿法、高斯-牛顿法、LM算法_萌萌哒程序猴的博客-CSDN博客

梯度下降法和最速下降法的细微差别_TimingSpace的博客-CSDN博客_最速下降法

今天的文章牛顿法最优化例题_牛顿法最优化例题分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/82033.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注