2022秋招SLAM——最优化方法

Mecanim · 发表于 2021-11-22 18:08

1.背景

该课程是我在北航时上的数学学院的课，刘红英老师开的课，质量非常非常高，但是也很，只要有一丝丝走神后面就跟不上了，上完课还是收获很大的，每个优化算法都自己敲一遍，优劣自现，为了准备期末考试我整理了很详细的资料，为了准备秋招我也挑着用的多的也整理了一下，都在链接里了。包含之前上深蓝学院VIO的课时，对优化算法的改进，这是一个练手的好机会。
2.内容

秋招复习笔记、期末考试笔记，详细对比了多种最优化算法：无约束优化和约束优化，无约束优化有line-search、trust-region等；约束优化有SVM、罚函数这些，但是平时用的会少一些；
此外还有一些我自己对比的实验结果，之前做VIO的时候把LM算法换成了DogLeg进行尝试，发现迭代次数、耗时都有降低，但是精度相差无几。
3.完整的总结

最优化方法主要分为约束优化和无约束优化，点云和slam用无约束优化多一些；在无约束优化方法主要分为两种：line-search线搜索法和信赖域法。
1.线搜索法的主要思想是：首先找到一个合适的下降方向，再确定步长，以使问题的解从初始可行解向局部最优解逼近
①比如，使用了一阶信息的最速下降法，选择负梯度法向作为下降方向；在选择步长时可以使用精确线搜索法，即沿着下降方向，求得精确的步长（把方向代到公式里，令梯度等于0），相当于沿该方向走到最低点才停下；但是如果想减少计算量的话，可以使用非精确线搜索，其动机是只要目标值下降就行，不一定要降到最低。所以该方法会得到一个区间，只要落在这个区间内即可。但是这里还有一个问题：如果步长特别靠近区间的左端点或右端点时，会使下降方向和梯度方向垂直，导致算法出现震荡，进入一个死循环，无法继续优化。因而出现了几种迭代策略，比如armijo法则、wolfe准则等，使步长既不太大，也不太小。这些方法通常使用迭代的方法找到合适的步长。
总之，在该方法中，只要下降方向和梯度方向不垂直，就可以保证大范围收敛（这是一个很重要的特性）
②如果参数量比较少，计算能力比较强的话，可以再加入二阶信息，比如牛顿法。牛顿法即是在当前点进行泰勒展开，然后令一阶导等于0，得到的步长为牛顿步。其引入了二阶信息，因此可以拟合的更好更快，拥有二阶收敛性（误差之比是常数），但是该方法也有一些缺陷，比如他的两个前提：①Hessian正定；②离局部最优值比较近；他的不足：③Hessian矩阵计算量太大了：O(n3)，
为了解决牛顿法的这些问题，GN开发了一种平方和的结构：最小化残差平方和，可以使用残差的一阶导转职乘以一阶导，也就是JTJ来近似Hessian矩阵，这样确实减小了计算量，但是可能不正定满秩。（必须小余量或者非线性程度低才会近似的比较好），
进而，LM算法给JTJ的对角线加了一个μ，也就变成了（JTJ+μI），来使其正定满秩，同时可以根据拟合的效果动态调整μ的大小，当拟合的不好时可将μ调大，整个算法近似于梯度下降法，使其拥有大范围收敛的特性；当拟合的较好时可将μ调小，整个算法近似于高斯牛顿法，使其更快的靠近局部最优值。LM算法还有两个好处：可以拒绝当前自变量的更新；可以动态调整μ的大小。（此处拟合的效果可以用实际下降量与拟合模型下降量的比值来表示）
2.共轭梯度法：共轭梯度法相当于要找到多个共轭方向，并沿着共轭方向做精确线搜索。二次终止性（最多迭代n次，多用于求解大规模的AX=b）
3.拟牛顿法：使用一阶导来计算Hessian矩阵，并进行迭代更新，以解决牛顿法H矩阵计算量太大的问题
4.信赖域法，其动机是不希望将方向和步长分开考虑，而是给出一个范围，在这个范围内寻找最优值，同时根据拟合程度动态调整信赖域半径，如果拟合效果好就增大半径。
补充：DogLeg的策略：

如果h_gn在域内：
h_dl←h_gn；
否则：
如果h_sd在与域外（h_gn和h_sd都在域外）：
h_dl←hsd与信赖域的交点（明显更相信梯度下降法）
如果h_sd在域内：
h_dl←为h_sd与h_gn连线，与信赖域圆的交点
其中，h_gn为高斯牛顿解，h_sd为最速下降解，h_dl为DogLeg解

关于为什么信赖域比LM要快一些的讨论：
在解决局部最优解的过程中，LM一直有阻尼在牵制他，但是DogLeg就没有，所以他会找到信赖域中最好的，所以会更快些；但是两者在精度上没有明显区别。
4.笔记链接

为了大家秋招复习、考试复习方便，我把内容全部整理到有道云笔记中，除了上面的总结，还补充了一些期末考试复习笔记，包含约束优化和无约束优化。
参考：[1]刘红英. 数学规划基础[M]. 北京航空航天大学出版社. 2012: 1-280.
欢迎关注，持续更新……

johnsoncodehk · 发表于 2021-11-22 18:15

楼主链接打不开

xiaozongpeng · 发表于 2021-11-22 18:21

之前内容有些草率了，我正在重新编辑整理，尽快发出来哈

TheLudGamer · 发表于 2021-11-22 18:30

谢谢楼主分享！

		自动登录	找回密码
密码			立即注册