非线性最小二乘问题求解方法详解：视觉SLAM与三维重建应用

3星 · 超过75%的资源需积分: 33 121 浏览量更新于2024-07-19 收藏 517KB PDF 举报

《非线性最小二乘问题方法》是一本介绍求解数值优化中非线性最小二乘问题的经典教材，出版于2004年4月，作者包括K.Madsen、H.B.Nielsen和O.Tingleff，由丹麦技术大学的Informatics and Mathematical Modelling部门编写。该书主要针对视觉SLAM（同时定位与映射）和三维重建等领域的广泛应用，探讨了多种有效的求解策略。书中首先定义了最优化的基本概念，即第1章中的“最小化问题”。最小二乘问题的核心是要找到一个向量x*，使得函数F(x)，定义为所有fi(x)（i=1,2,...,m，其中m至少等于n）的平方和的一半，达到最小值。例如，数据拟合是这类问题的重要来源，如图1.1所示的数据点集合{(ti, yi)}。在第2章“下降法”中，讲解了经典的梯度下降法，它通过沿着负梯度方向逐步逼近最小值。接着介绍了牛顿法，这是一种基于函数近似二次模型的方法，通过迭代更新来更精确地接近最小值。接下来讨论了线搜索策略，以确定在每次迭代中最佳的步长，确保收敛到最优解。第三章深入探讨了非线性最小二平方问题的特定解决技术。首先是高斯-牛顿法，利用函数的局部线性化来简化问题。其次是Levenberg-Marquardt方法，这是一种结合了高斯-牛顿和梯度法优点的混合方法，通过调整参数动态调整步长。Powell's Dog Leg Method则是一种采用折线搜索的算法，提供更灵活的步长选择。书中还介绍了L-M方法的正切版本和Dog Leg方法的正切版本，这些变体在某些情况下能提高算法效率。最后，第3.7节给出了总结性的讨论，可能包括算法的适用范围、优点和局限性，以及如何根据具体问题选择合适的方法。附录提供了补充的理论和技术细节，而参考文献列出了进一步研究的基础文献。索引部分便于读者查找特定概念或方法。这本书详细阐述了非线性最小二乘问题求解的理论基础和实践技巧，对于从事计算机视觉、机器人学、信号处理等相关领域的研究人员和工程师具有很高的实用价值。通过学习本书，读者可以掌握从基本的梯度下降到高级的混合方法，如何在实际问题中有效应用这些技术。

92.DESCENT METHODS

(x) is positive deﬁnite, then we get quadratic convergence (deﬁned in

(2.3)). On the other hand, if x is in a region where F

(x) is negative deﬁnite

everywhere, and where there is a stationary point, the basic Newton method

(2.9) would converge (quadratically) towards this stationary point, which

is a maximizer. We can avoid this by requiring that all steps taken are in

descent directions.

We can build a hybrid method, based on Newton’s method and the steepest

descent method. According to (2.10) the Newton step is guaranteed to be

downhill if F

(x) is positive deﬁnite, so a sketch of the central section of

this hybrid algorithm could be

if F

(x) is positive deﬁnite

h := h

else

h := h

x := x + αh

(2.11)

Here, h

is the steepest descent direction and α is found by line search; see

Section 2.3. A good tool for checking a matrix for positive deﬁniteness is

Cholesky’s method (see Appendix A) which, when successful, is also used

for solving the linear system in question. Thus, the check for deﬁniteness is

almost for free.

In Section 2.4 we introduce some methods, where the computation of the

search direction h

and step length α is done simultaneously, and give a

version of (2.11) without line search. Such hybrid methods can be very

efﬁcient, but they are hardly ever used. The reason is that they need an im-

plementation of F

(x), and for complicated application problems this is not

available. Instead we can use a so-called Quasi-Newton method, based on

series of matrices which gradually approach H

∗

= F

∗

). In Section 3.4

we present such a method. Also see Chapter 5 in Frandsen et al (2004).

2.3. Line Search

Given a point x and a descent direction h. The next iteration step is a move

from x in direction h. To ﬁnd out, how far to move, we study the variation

of the given function along the half line from x in the direction h,

2.3. Line Search 10

ϕ(α)=F(x+αh), xand h ﬁxed,α≥0. (2.12)

An example of the behaviour of ϕ(α) is shown in Figure 2.1.

y = φ(0)

y = φ(α)

Figure 2.1. Variation of the cost

function along the search line.

Our h being a descent direction ensures that

(0) = h

(x) < 0 ,

indicating that if α is sufﬁciently small, we satisfy the descending condition

(2.1), which is equivalent to

ϕ(α) <ϕ(0) .

Often, we are given an initial guess on α,egα=1 with Newton’s method.

Figure 2.1 illustrates that three different situations can arise

◦

α is so small that the gain in value of the objective function is very

small. α should be increased.

◦

α is too large: ϕ(α) ≥ϕ(0). Decrease α in order to satisfy the descent

condition (2.1).

◦

α is close to the minimizer

of ϕ(α). Accept this α-value.

More precisely: the smallest local minimizer of ϕ. If we increase α beyond the interval

shown in Figure 2.1, it may well happen that we get close to another local minimum

for F .

剩余29页未读，继续阅读

likai1610

粉丝: 1
资源: 1

非线性最小二乘问题求解方法详解：视觉SLAM与三维重建应用

Method for Nonlinear Least Squares Problems

Algorithm-Moving-Least-Squares.zip

nonlinear_least_squares

比较least squares, logit,probit model的maximised log-likelihood

logistic模型的估计方法为: A:Ordinary least squares B:Ordinary least squares C:Poisson distribution D:Maximum likelihood estimation

partial least squares python

最小二乘法 (Least Squares, LSM) 算法python代码

image deformation using moving least squares

linear least squares (LLS) curve fitting problem

详细介绍OLS (Ordinary Least Squares) 模型

最新资源