迭代求解最优化问题——Levenberg

迭代改进：解决问题后持续优化解决方案 #生活技巧# #学习技巧# #解决问题的思考技巧#

高斯牛顿法使用的条件

上一篇中提到了线性最小二乘问题minx||Ax−b||的的标准方程为ATAx−ATb=0。其中x为n维向量，b为m维向量，A为m×n的矩阵。

从标准方程我们可以求出x的解析解，然而这其实隐含了一个条件，就是rank(A)=n。当A秩亏的时候，rank(ATA)≤rank(A)<n，ATA不可逆。

事实上，这种情况下x的解有无穷多个，此时问题是欠约束的。

我们使用高斯牛顿法的时候，也有同样的限制，当rank(J)<n时，理论上JTJ没有逆。但是由于浮点数误差等原因，我们有可能得到一个JTJ的逆，显然此时det(JTJ)非常接近于零，由于||Δ||=||(JTJ)−1JTb||=||JTb||||det(JTJ)||，我们会得到一个非常大的Δ。这显然会导致求解失败。

正则化

为保证每次的迭代步长不过大，我们可以在优化的损失函数里面加入一个阻尼项，于是优化问题变成了minx||Ax−b||2+λ||x||2。

它的标准方程变成了 (ATA+λI)x=ATb，因为ATA是半正定的，当λ>0时，ATA+λI 一定可逆。

对λ的选取需要特别注意，λ过小时起不到阻尼的作用，λ过大时会使得最终求解的问题偏离原问题。

Levenberg算法

将上述策略应用到高斯牛顿法中，我们就得到了Levenberg算法。对标准方程 (JTJ+λI)Δ=−JTb。当λ接近于零时，方程退化成高斯牛顿法，当λ很大时，Δ=−1λJTb，接近于梯度下降法。

实际进行迭代时，我们可以动态的调整λ的大小，当损失函数下降较快时减少λ，当损失函数下降较慢时增加λ，从而使得迭代同时具备高斯牛顿法（收敛快但不一定能找到最值点）和梯度下降法（稳定但是速度慢）的优点。

Levenberg-Marquardt算法

上述策略中，当λ很大时(JTJ+λI)的求解对于最终迭代步长并没有什么贡献。Marquardt在此基础上提出我们可以通过Jacobian矩阵来缩放梯度的不同维度，从而在梯度较小的方向也能走得更远，由此将阻尼项改写为λdiag(JTJ)。这就是Levenberg-Marquardt算法。

Marquardt也提出了λ的选择策略。他提出在算法开始时假设两个参数λ0和ν >1。分别使用λ=λ0和λ=λ/ν迭代两次并计算损失函数。如果两次结果都比初始点差，则不断增加阻尼系数，用ν去乘λ，直到损失函数下降为止。

迭代时如果阻尼系数λ/ν使得损失函数下降更快，则用它来代替之前的λ，并使用当前点代替之前的点，再次执行该过程。否则不改变λ，并使用当前点代替之前的点。

事实上，如果对数值优化有一定了解的话，我们可以发现LM算法是一种信赖域算法。它使用二次模型来近似真实模型。

网址：迭代求解最优化问题——Levenberg https://www.yuejiaxmz.com/news/view/861808

相关内容

迭代优化怎么做（产品优化迭代的3个方面）
强化学习中的策略迭代算法优化研究
用迭代法求x=√a求平方根的迭代公式为
机器/深度学习模型最优化问题详解及优化算法汇总
手把手教你强化学习 (四)动态规划与策略迭代、值迭代
优化迭代方法和深度学习反向传播
非线性方程迭代求根
浅谈*迭代加深*深度优先搜索
经典与现代的优化算法详解
【运筹】0402 网络优化问题

随便看看