优化算法学习(LM算法)

优化算法学习(LM算法)LM算法可以理解为**Gauss-Newton算法与最速下降法的结合**

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

推荐书籍

建议学习,METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS:
http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3215/pdf/imm3215.pdf
篇幅不长,容易理解
学习的时候可以参考另一篇,UNCONSTRAINED OPTIMIZATION:http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3217/pdf/imm3217.pdf

Numerical Optimization 2nd –Jorge Nocedal Stephen J. Wright:
http://www.bioinfo.org.cn/~wangchao/maa/Numerical_Optimization.pdf
《视觉SLAM十四讲》第六讲 https://github.com/gaoxiang12/slambook

理论理解

知乎上看到一个回答非常好:

LM算法可以理解为Gauss-Newton算法与最速下降法的结合,如果理解了如何用上述算法求解目标函数最小值的问题,自然也能理解LM。

其实算法的本质就是 a. 站在当前位置( x k x_k xk ),我们需要一个预言(oracle)告诉我们往哪走能找到目的地(最优解可能的方向,比如梯度方向);b. 我们沿着该方向走了一段距离之后(stepsize),更新当前位置信息( x k + 1 x_{k+1} xk+1 ),再问预言家我们下一步往哪走,以此反复。

所以,梯度下降法,给的 oracle 就是当前位置的梯度信息(损失方程关于变量的一阶导数):

x k + 1 = x k − α g k x_{k+1}=x_k-\alpha g_k xk+1=xkαgk

如果是牛顿法,给的 oracle 就是Hessian matrix(损失方程关于变量的二阶导数):

x k + 1 = x k − H k − 1 g k x_{k+1}=x_k-H_k^{-1}g_k xk+1=xkHk1gk(1)

为什么是一阶导数和二阶导数?因为我们知道,对于任意(处处可导的)方程,在其任意一点,我们都可以用泰勒展开式对其拟合,阶数越高,精度越高。但是,考虑到高阶导数的计算复杂度,以及三阶以上函数的非凸性,也不会使用高阶导数。

好了,那么LM算法的优势是什么?牛顿法虽然收敛速度快,但是需要计算 Hessian matrix,对于高维的问题,计算二阶导数会很复杂。因此我们有了Gauss-Newton算法。Gauss-Newton算法不直接计算Hessian matrix,而是通过 Jacobian matrix 对 Hessian matrix 进行拟合:

H ≈ J T J H\approx J^TJ HJTJ

但是,用 Jacobian matrix 拟合Hessian matrix,所计算出来的结果不一定可逆。所以在此基础上,我们引入了一个identity matrix:

H ≈ J T J + μ I H\approx J^TJ+\mu I HJTJ+μI

这也就得到了LM算法。如果我们把上述式子带入之前的公式(1),可以得到

x k + 1 = x k − ( J k T J k + μ I ) − 1 g k x_{k+1}=x_k-(J_k^TJ_k+\mu I)^{-1}g_k xk+1=xk(JkTJk+μI)1gk

所以我们发现,当 μ \mu μ接近于0时,这个算法近似于Gauss-Newton算法;当 μ \mu μ很大时,这个算法近似于最速下降法。因此,这也是为什么LM算法称为Gauss-Newton算法与最速下降法的结合。最后,上一张图表示几种算法之间的关系:
在这里插入图片描述
参考文献:Wilamowski, B. M., & Yu, H. (2010). Improved computation for Levenberg–Marquardt training. IEEE transactions on neural networks, 21(6), 930-937.

一个回答:Matlab 的话现成的代码也是很多的;比如,Solve nonlinear least-squares (nonlinear data-fitting) problems,或者 Levenberg-Marquardt-Fletcher algorithm for nonlinear least squares problems。你可以在网站里面搜搜有没有适合你的。

作者:Sixiang
链接:https://www.zhihu.com/question/269579938/answer/349205519
来源:知乎

这是最上面推荐的书,英文不难:
在这里插入图片描述

gradient matrix, hessian matrix, jacobian matrix:gradient hessian jacobian matrix
https://www.value-at-risk.net/functions/

csdn 有个不错的博客:数值优化(Numerical Optimization)学习系列-目录:https://blog.csdn.net/fangqingan_java/article/details/48951191

程序实现

视觉SLAM十四讲里推荐了**Ceres库**,Ceres solver 是谷歌开发的一款用于非线性优化的库,在谷歌的开源激光雷达slam项目cartographer中被大量使用。
安装和使用参考:
https://zhaoxuhui.top/blog/2018/04/04/ceres&ls.html
下面把关键操作贴出来:

ceres安装

  • 下载源码
    git clone https://github.com/ceres-solver/ceres-solver.git
  • 安装依赖:
sudo apt-get install cmake
# google-glog + gflags
sudo apt-get install libgoogle-glog-dev libgtest-dev libgflags-dev
# BLAS & LAPACK
sudo apt-get install libatlas-base-dev liblapack-dev
# Eigen3
sudo apt-get install libeigen3-dev
# SuiteSparse and CXSparse (optional)
sudo apt-get install libsuitesparse-dev libcxsparse3.1.4

这里libcxsparse可能存在版本问题(出现找不到对应版本),解决办法:

sudo apt-get install bash-completion
sudo gedit /etc/bash.bashrc

将这一部分取消注释,并保存,即可自动补全:
在这里插入图片描述
sudo apt-get install libsuitesparse-dev libcxsparse(按tab)

cd ceres-solver/
mkdir build
cd build
cmake ..
make -j3
sudo make install

代码:

利用Ceres简单实现最小二乘曲线拟合。首先需要生成数据,这里采用OpenCV的随机数生成器生成误差。

#include <iostream>
#include <opencv2/core/core.hpp>
#include <ceres/ceres.h>
using namespace std;
using namespace cv;
using namespace ceres;
//vector,用于存放x、y的观测数据
//待估计函数为y=3.5x^3+1.6x^2+0.3x+7.8
vector<double> xs;
vector<double> ys;
//定义CostFunctor结构体用于描述代价函数
struct CostFunctor{ 

double x_guan,y_guan;
//构造函数,用已知的x、y数据对其赋值
CostFunctor(double x,double y)
{ 

x_guan = x;
y_guan = y;
}
//重载括号运算符,两个参数分别是估计的参数和由该参数计算得到的残差
//注意这里的const,一个都不能省略,否则就会报错
template <typename T>
bool operator()(const T* const params,T* residual)const
{ 

residual[0]=y_guan-(params[0]*x_guan*x_guan*x_guan+params[1]*x_guan*x_guan+params[2]*x_guan+params[3]);
return true;  
}
};
//生成实验数据
void generateData()
{ 

RNG rng;
//RNG::gaussian( σ) 返回一个均值为0,标准差为σ的随机数。
double w_sigma = 1.0;
for(int i=0;i<100;i++)
{ 

double x = i;
double y = 3.5*x*x*x+1.6*x*x+0.3*x+7.8;
xs.push_back(x);
ys.push_back(y+rng.gaussian(w_sigma));
}
for(int i=0;i<xs.size();i++)
{ 

cout<<"x:"<<xs[i]<<" y:"<<ys[i]<<endl;
}
}
//简单描述我们优化的目的就是为了使我们估计参数算出的y'和实际观测的y的差值之和最小
//所以代价函数(CostFunction)就是y'-y,其对应每一组观测值与估计值的残差。
//由于我们优化的是残差之和,因此需要把代价函数全部加起来,使这个函数最小,而不是单独的使某一个残差最小
//默认情况下,我们认为各组的残差是等权的,也就是核函数系数为1。
//但有时可能会出现粗差等情况,有可能不等权,但这里不考虑。
//这个求和以后的函数便是我们优化的目标函数
//通过不断调整我们的参数值,使这个目标函数最终达到最小,即认为优化完成
int main(int argc, char **argv) { 

generateData();
//创建一个长度为4的double数组用于存放参数
double params[4]={ 
1.0};
//第一步,创建Problem对象,并对每一组观测数据添加ResidualBlock
//由于每一组观测点都会得到一个残差,而我们的目的是最小化所有残差的和
//所以采用for循环依次把每个残差都添加进来
Problem problem;
for(int i=0;i<xs.size();i++)
{ 

//利用我们之前写的结构体、仿函数,创建代价函数对象,注意初始化的方式
//尖括号中的参数分别为误差类型,输出维度(因变量个数),输入维度(待估计参数的个数)
CostFunction* cost_function = new AutoDiffCostFunction<CostFunctor,1,4>(new CostFunctor(xs[i],ys[i]));
//三个参数分别为代价函数、核函数和待估参数
problem.AddResidualBlock(cost_function,NULL,params);
}
//第二步,配置Solver
Solver::Options options;
//配置增量方程的解法
options.linear_solver_type=ceres::DENSE_QR;
//是否输出到cout
options.minimizer_progress_to_stdout=true;
//第三步,创建Summary对象用于输出迭代结果
Solver::Summary summary;
//第四步,执行求解
Solve(options,&problem,&summary);
//第五步,输出求解结果
cout<<summary.BriefReport()<<endl;
cout<<"p0:"<<params[0]<<endl;
cout<<"p1:"<<params[1]<<endl;
cout<<"p2:"<<params[2]<<endl;
cout<<"p3:"<<params[3]<<endl;
return 0;
}

CMakeLists.txt:

cmake_minimum_required(VERSION 2.6)
project(ceres_test)
set( CMAKE_CXX_FLAGS "-std=c++11 -O3" )
# 添加cmake模块以使用ceres库
list( APPEND CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake_modules )
# 寻找Ceres库并添加它的头文件
find_package( Ceres REQUIRED )
include_directories( ${CERES_INCLUDE_DIRS} )
# OpenCV
find_package( OpenCV REQUIRED )
include_directories( ${OpenCV_DIRS} )
add_executable(ceres_test main.cpp)
# 与Ceres和OpenCV链接
target_link_libraries( ceres_test ${CERES_LIBRARIES} ${OpenCV_LIBS} )
install(TARGETS ceres_test RUNTIME DESTINATION bin)

另外,有个levmar的C/C++的库:(这个还不会用)
levmar : Levenberg-Marquardt nonlinear least squares algorithms in C/C++
http://users.ics.forth.gr/~lourakis/levmar/index.html#download
http://users.ics.forth.gr/~lourakis/sparseLM/

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187088.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • React—最简洁的技术学习(一)

    React—最简洁的技术学习(一)React—最简洁的技术学习(一)

  • 解决lefse配置过程中遇到的问题「建议收藏」

    解决lefse配置过程中遇到的问题「建议收藏」记录centos7.5中配置lefse过程中遇到的问题1、下载lefse软件包,解压,查看“requirements.txt”文件,需要的R和python包列表:-R-Rlibraries:splines,stats4,survival,mvtnorm,modeltools,coin,MASS-pythonlibraries:rpy2(v.2.1orh…

  • uu怎么卸载_卸载deepin引导

    uu怎么卸载_卸载deepin引导ubutun干净卸载删除wineQQ博主原本想要在ubuntu18.04安装wineQQ,在安装完成后却显示QQ版本过低无法运行,只能卸载重装,不然那个QQ标志在软件列表非常碍眼。这个是之前安装wineQQ的教程【QQ版本已过期】问题:卸载不掉该软件且网上大多数指令都过期了解决方案:在deepinwine的应用容器中,用sudoaptremove软件包主名命令来删除。比如d…

  • 汉语拼音发音教学视频_钢琴手把手教学视频

    汉语拼音发音教学视频_钢琴手把手教学视频pycharm汉化pycharm怎么改成汉语,手把手教学,超详细(汉语插件安装教程)首先,打开pycharm。然后点击左上角File(文件)会弹出如下页面继续点击蓝色位置Settings…(设置)会弹出一个页面如下:继续点击蓝色位置Plugins(插件)在搜索栏中输入chinese,如图然后安装第二个(可以滑动找一下),点击Install(安装),会加载一下下载进度条,然后变成这样:安装之后点击绿色按钮RestartIDE,会弹出点击蓝色按钮Restart,然后pycharm会重启,重启后

  • centos 7如何将 网卡ens33 修改成 eth0「建议收藏」

    centos 7如何将 网卡ens33 修改成 eth0「建议收藏」文章目录linux网卡名称命名命名规则修改eth0方法linux网卡名称命名命名规则CENTOS6的网卡命名方式它会根据情况有所改变而非唯一且固定,在CENTOS6之前,网络接口使用连续号码命名:eth0、eth1等,当增加或删除网卡时,名称可能会发生变化CENTOS7命名方式采用dmidecode采集命名方案,以此来得到主板信息;它可以实现网卡名字永久唯一化(dmidecode这个命令可以采集有关硬件方面的信息)对网络设备的命名方式:1)如果Firmware(固件)或B

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号