最优化方法(最速下降、牛顿法、高斯牛顿法、LM算法)

简介: 最优化方法(最速下降、牛顿法、高斯牛顿法、LM算法)

前言

最优化方法应用广泛,但在实现原理上大同小异。作者在学习高翔博士的视觉SLAM十四讲的过程中对其第六章非线性最小二乘求解所涉及到的最优化方法(最速下降、牛顿法、高斯牛顿法、LM算法)进行了简要总结如下:

最速下降法(梯度下降/一阶导数法)

作者在最速下降法解析(理解笔记)中曾经介绍过最速下降法的实现过程,并列举了一个小例子。在这里,为了文章整体的完整性,我们再重新叙述一下,大家也可以参考。

假设我们希望求解一个最小二乘问题:

                                 image.png

把上式在x处进行泰勒展开:

                      image.png

式中 J ( x )与H(x)分别为关于变量 x的雅克比矩阵(一阶导数)和海塞矩阵(二阶导数)。

在梯度下降法中,我们只考虑在 x处的一阶梯度。则上式变为:


                        image.png

认为沿着一阶梯度反方向下降最快,当然,在迭代过程中每一步走多长也是一个需要考虑的问题,我们可以设计一个定长 λ \lambda λ。当然这种方式有着明显的不合理之处,一个较大的步长会导致我们在优化过程中走出锯齿状路线,而一个较小的步长则会导致我们收敛速度过慢。这种设置为固定步长 λ 的方式为梯度下降法。很多时候认为梯度下降与最速下降是等价的,这并不十分准确,最速下降法对步长λ进行选取一个最优的 λ ∗

其把 λ代入: x ( 1 ) = x ( 0 ) − λ J ( x ) ,然后求取在 f ( x ( 1 ) )处取得最小值的 λ作为λ∗

牛顿法(二阶导数法)

这里我们保留在x处的二阶展开项:


                     image.png


首先明确一下我们的目的是找到一个最优的 Δ x ∗使得上式取得最小值:


                   image.png


将上式视为 Δ x的函数,对 Δ x进行求导,得到如下形式:


                                        J(x)+H(x)Δx

令其导数为0:

                                     J(x)+H(x)Δx=0

则取得极小值,解出增量为:

                                 image.png

还有另外一种理解方式是把牛顿法看成是对一阶导数法的求根过程,即使用牛顿法求解原函数一阶导数为零的 Δ x


牛顿法需要计算目标函数的二阶导数 H ( x ),这在遇到规模较大的问题时,会比较困难,因此我们常常避免 H ( x )矩阵的运算。

后续的高斯牛顿法和LM算法解决了这个问题。

高斯牛顿法

高斯牛顿法是对函数 f ( x )进行一阶展开(注意不是 f ( x ) 2,展开形式如下:

                                     f(x+Δx)f(x)+J(x)Δx

这里的J(x)也是雅克比矩阵,与前述不同的是这里是 f ( x )对变量 x的导数。

由此,当前我们的目标变成了:寻找一个增量Δ x ,使得image.png

                       image.png

展开上式:

                            image.png

上式关于Δ x 求导,并令其为0:

                         image.png

即:

                         image.png

上式是一个线性方程组,被称为增量方程,也可以称为高斯牛顿方程或者正规方程。把左边的系数即为H,右侧记为g,则上式转换为:

                                       image.png

这里的H即为牛顿法里海塞矩阵的近似,省略了计算二阶导数的过程。

上述过程中我们使用了image.png 的逆,但是image.png 是半正定的,不能保证其为非奇异性。

Levenberg-Marquadt(LM算法)

LM算法是一种信赖域方法,我们使用一个参数 ρ来根据我们的近似模型跟实际函数之间的差异来确定这个范围,如果 ρ的值较小,则差异较小,让范围继续扩大,而如果ρ的值很大,则差异较大,则缩小范围:                                        

                          image.png


上式中分子是实际函数下降的值,分母是近似值。若ρ的值接近1则认为近似是好的。如果ρ太小,则认为近似比较差,则需要缩小近似范围。反之,如果ρ比较大,则认为实际下降的比预计的大,我们可以扩大近似范围。

上图中公式(6.24)是一个带有不等式约束的优化问题。使用一个Lagrange乘子把其转换为一个无约束优化问题。

                  image.png

使用类似于高斯牛顿法中的过程,对上式进行求导,然后使其导数为0,得到的增量方程为:

                                              image.png

与高斯牛顿法相比,我们可以发现多出来一项image.png,简化记 D-I为:

                                        image.png

可以由上式观察到,当参数 λ的值比较大时,则LM算法接近为最速下降法,而 λ 的值较小时则近似于高斯牛顿法。

目录
相关文章
|
26天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
84 4
|
5天前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
28 3
|
5天前
|
算法
PAI下面的gbdt、xgboost、ps-smart 算法如何优化?
设置gbdt 、xgboost等算法的样本和特征的采样率
22 2
|
20天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
24天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
17天前
|
算法
基于WOA鲸鱼优化的购售电收益与风险评估算法matlab仿真
本研究提出了一种基于鲸鱼优化算法(WOA)的购售电收益与风险评估算法。通过将售电公司购售电收益风险计算公式作为WOA的目标函数,经过迭代优化计算出最优购电策略。实验结果表明,在迭代次数超过10次后,风险价值收益优化值达到1715.1万元的最大值。WOA还确定了中长期市场、现货市场及可再生能源等不同市场的最优购电量,验证了算法的有效性。核心程序使用MATLAB2022a实现,通过多次迭代优化,实现了售电公司收益最大化和风险最小化的目标。
|
21天前
|
算法
通过matlab分别对比PSO,反向学习PSO,多策略改进反向学习PSO三种优化算法
本项目使用MATLAB2022A版本,对比分析了PSO、反向学习PSO及多策略改进反向学习PSO三种优化算法的性能,主要通过优化收敛曲线进行直观展示。核心代码实现了标准PSO算法流程,加入反向学习机制及多种改进策略,以提升算法跳出局部最优的能力,增强全局搜索效率。
|
17天前
|
算法
通过matlab对比遗传算法优化前后染色体的变化情况
该程序使用MATLAB2022A实现遗传算法优化染色体的过程,通过迭代选择、交叉和变异操作,提高染色体适应度,优化解的质量,同时保持种群多样性,避免局部最优。代码展示了算法的核心流程,包括适应度计算、选择、交叉、变异等步骤,并通过图表直观展示了优化前后染色体的变化情况。
|
21天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
21天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-GRU网络的数据分类识别算法matlab仿真
本项目展示了使用MATLAB2022a实现的贝叶斯优化、CNN和GRU算法优化效果。优化前后对比显著,完整代码附带中文注释及操作视频。贝叶斯优化适用于黑盒函数,CNN用于时间序列特征提取,GRU改进了RNN的长序列处理能力。