非线性最小二乘法：优化算法解析
需积分: 9 32 浏览量
更新于2024-07-21
收藏 367KB PDF 举报
"nonlinear_least_squares - 一本关于非线性最小二乘问题的书籍，涵盖基于导数的优化算法，如梯度下降、牛顿法、线搜索、信赖域和阻尼方法等。"
在非线性最小二乘问题（Nonlinear Least Squares Problems）中，目标是找到一个局部最小值点x*，使得函数F(x)的值最小。F(x)通常定义为数据残差平方和的一半，即所有观测值fi(x)与理想值之间的差异平方和。这个问题广泛应用于数据拟合等领域。
1. 梯度下降法（The Steepest Descent method）：
这是最简单的迭代优化方法之一，通过沿着负梯度方向更新参数来减少目标函数的值。在每次迭代中，步长由线性搜索确定，以确保函数值的下降。
2. 牛顿法（Newton’s Method）：
牛顿法利用函数的二阶导数（Hessian矩阵）来确定搜索方向，旨在寻找使梯度为零的点。这种方法通常更快，但计算成本较高，因为需要求解Hessian矩阵。
3. 线搜索（Line Search）：
在确定的搜索方向上，线搜索算法通过调整步长来寻找目标函数最小值。它通常结合在其他方法中，如梯度下降或牛顿法，以找到合适的步长。
4. 信赖域和阻尼方法（Trust Region and Damped Methods）：
这些方法在牛顿法的基础上添加了限制条件，确保每次迭代的步长不会太大，从而避免远离当前解的局部极小值。阻尼方法如拟牛顿法，通过近似Hessian矩阵来降低计算复杂性。
5. 高斯-牛顿法（The Gauss-Newton Method）：
专门用于非线性最小二乘问题，它通过近似Hessian矩阵为零来简化牛顿法，适用于函数的雅可比矩阵（Jacobian）易于计算的情况。
6. 列文伯格-马夸特法（Levenberg-Marquardt Method）：
结合了高斯-牛顿法和梯度下降法的优点，当雅可比矩阵近似不好时，通过添加一个类似梯度的项来改善收敛性能。
7. 波尔茨曼狗腿法（Powell’s Dog-Leg Method）：
一种混合策略，结合了牛顿法和共轭梯度法的元素，试图在全局和局部搜索之间找到平衡。
8. L-M方法的拟牛顿版本（A Hybrid Method: L-M and Quasi-Newton）：
使用拟牛顿技术改进Levenberg-Marquardt方法，通过近似Hessian矩阵减少计算负担。
9. L-M方法的secant版本（A Secant Version of the L-M Method）：
类似于拟牛顿法，但使用secant方程代替二阶导数信息。
10. 狗腿法的secant版本（A Secant Version of the Dog-Leg Method）：
对波尔茨曼狗腿法的改进，用secant代替Hessian矩阵，降低计算复杂性。
这些方法在实际应用中各有优缺点，选择哪种方法取决于问题的特性、计算资源和对解的精度要求。书中详细介绍了每种方法的原理、实现和适用场景，为解决非线性最小二乘问题提供了丰富的工具和策略。
92.DESCENT METHODS
F
00
(x) is positive definite, then we get quadratic convergence (defined in
(2.3)). On the other hand, if x is in a region where F
00
(x) is negative definite
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
00
(x) is positive definite, so a sketch of the central section of
this hybrid algorithm could be
if F
00
(x) is positive definite
h := h
n
else
h := h
sd
x := x + αh
(2.11)
Here, h
sd
is the steepest descent direction and α is found by line search; see
Section 2.3. A good tool for checking a matrix for positive definiteness is
Cholesky’s method (see Appendix A) which, when successful, is also used
for solving the linear system in question. Thus, the check for definiteness is
almost for free.
In Section 2.4 we introduce some methods, where the computation of the
search direction h
d
and step length α is done simultaneously, and give a
version of (2.11) without line search. Such hybrid methods can be very
efficient, but they are hardly ever used. The reason is that they need an im-
plementation of F
00
(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
00
(x
∗
). 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 find 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 fixed,α≥0. (2.12)
An example of the behaviour of ϕ(α) is shown in Figure 2.1.
α
y
y = φ(0)
y = φ(α)
Figure 2.1. Variation of the cost
function along the search line.
Our h being a descent direction ensures that
ϕ
0
(0) = h
>
F
0
(x) < 0 ,
indicating that if α is sufficiently 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
1
◦
α is so small that the gain in value of the objective function is very
small. α should be increased.
2
◦
α is too large: ϕ(α) ≥ϕ(0). Decrease α in order to satisfy the descent
condition (2.1).
3
◦
α is close to the minimizer
1)
of ϕ(α). Accept this α-value.
1)
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页未读，继续阅读
2022-07-15 上传
2023-07-16 上传
2020-03-02 上传
2021-05-13 上传
2021-02-10 上传
2020-04-03 上传
2022-09-24 上传
2021-02-13 上传
fengxiuyaun
- 粉丝: 2
- 资源: 1
我的内容管理
展开
最新资源
- 平尾装配工作平台运输支撑系统设计与应用
- MAX-MIN Ant System：用MATLAB解决旅行商问题
- Flutter状态管理新秀：sealed_flutter_bloc包整合seal_unions
- Pong²开源游戏：双人对战图形化的经典竞技体验
- jQuery spriteAnimator插件：创建精灵动画的利器
- 广播媒体对象传输方法与设备的技术分析
- MATLAB HDF5数据提取工具：深层结构化数据处理
- 适用于arm64的Valgrind交叉编译包发布
- 基于canvas和Java后端的小程序“飞翔的小鸟”完整示例
- 全面升级STM32F7 Discovery LCD BSP驱动程序
- React Router v4 入门教程与示例代码解析
- 下载OpenCV各版本安装包，全面覆盖2.4至4.5
- 手写笔画分割技术的新突破：智能分割方法与装置
- 基于Koplowitz & Bruckstein算法的MATLAB周长估计方法
- Modbus4j-3.0.3版本免费下载指南
- PoqetPresenter：Sharp Zaurus上的开源OpenOffice演示查看器
