2:6
•
M. I. A. Lourakis and A. A. Argyros
is iterative: initiated at the starting point p
0
, it produces a series of vectors
p
1
, p
2
, ..., that converge toward a local minimizer p
+
for f . Hence, at each
iteration, it is required to find the step δ
p
that minimizes the quantity ||x −
f (p + δ
p
)||≈||x − f (p) − Jδ
p
||=|| − Jδ
p
||. The sought δ
p
is thus the solution
to a linear least-squares problem: the minimum is attained when Jδ
p
− is
orthogonal to the column space of J. This leads to J
T
(Jδ
p
− ) = 0, which yields
δ
p
as the solution of the so-called normal equations [Golub and van Loan 1996]:
J
T
Jδ
p
= J
T
. (3)
Matrix J
T
J in the above equation is the first order approximation to the Hessian
of
1
2
T
[Nocedal and Wright 1999] and δ
p
is the Gauss-Newton step. Note also
that J
T
corresponds to the steepest descent direction since the gradient of
1
2
T
is −J
T
. The LM method actually solves a slight variation of Equation (3),
known as the augmented normal equations
Nδ
p
= J
T
, with N ≡ J
T
J + μI, μ>0. (4)
The strategy of altering the diagonal elements of J
T
J is called damping and
μ is referred to as the damping term. If the updated parameter vector p + δ
p
with δ
p
computed from Equation (4) leads to a reduction in the error
T
, the
update is accepted and the process repeats with a decreased damping term.
Otherwise, the damping term is increased, the augmented normal equations
are solved again, and the process iterates until a value of δ
p
that decreases
the error is found. The process of repeatedly solving Equation (4) for different
values of the damping term until an acceptable update to the parameter vector
is found corresponds to one iteration of the LM algorithm.
In LM, the damping term is adjusted at each iteration to assure a reduction in
the error. If the damping is set to a large value, matrix N in Equation (4) is nearly
diagonal and the LM update step δ
p
is skewed toward the steepest descent
direction J
T
. Moreover, the magnitude of δ
p
is reduced in this case, ensuring
that excessively large Gauss-Newton steps are not taken. Damping also handles
situations where the Jacobian is rank deficient and J
T
J is therefore singular
[Dennis and Schnabel 1996; Lampton 1997]. The damping term can be chosen
so that matrix N in Equation (4) is safely nonsingular and, therefore, positive
definite, thus ensuring that the δ
p
computed from it is a descent direction. If
the damping is small, the LM step approximates the Newton minimizer of the
local quadratic model m(δ
p
) =
1
2
T
− (J
T
)
T
δ
p
+
1
2
δ
T
p
J
T
Jδ
p
of
1
2
T
about p (cf.
Equation (3)), which is exact in the case of a fully linear problem [Kelley 1999].
LM is adaptive because it controls its own damping: it raises the damping if a
step fails to reduce
T
; otherwise it reduces the damping. By doing so, LM is
capable of alternating between a slow descent approach when being far from the
minimum and a fast convergence when being at the minimum’s neighborhood
[Lampton 1997]. An efficient updating strategy for the damping term that is
also used in this work has been described in Nielsen [1999]. The LM algorithm
terminates when any of the following conditions is met:
—the magnitude of the gradient drops below a threshold ε
1
;
—the relative magnitude of δ
p
drops below a threshold involving a parameter ε
2
;
ACM Transactions on Mathematical Software, Vol. 36, No. 1, Article 2, Publication date: March 2009.
剩余29页未读，继续阅读
白菜888
- 粉丝: 7
- 资源: 74
我的内容管理
展开
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析：故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全：高效编程的秘密武器
- 网页制作入门：常用代码详解
- TX2440A开发板网络远程监控系统移植教程：易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析：Socket基础与应用
- 掌握Struts1：Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全：字体、文本、列表样式详解
- Proteus元件库大全：从基础到高级组件
- 74HC08芯片：高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题：设置字符集为GB2312
- C语言的诞生与演进：从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
