METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS-2.1下降法,2.2牛顿法

METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS-2.1下降法,2.2牛顿法

对于非线性优化的所有方法都是迭代的：从一个起点x0，方法产生出一系列的向量x1,x2,.....，希望收敛到x*,给定函数的一个局部最小点。看定义1.3（在上一节）

大多数方法都有一些措施，这些措施强迫下降的条件

这就阻止收敛到一个最大值以及使得算法不太可能收敛到一个鞍点。如果给定的函数有一些局部最小值，这就取决于给定的初始点x0了。不知道哪一个最小值会被找到，也没有必要这个最小值最接近于x0.

在许多例子中，方法产生的向量收敛于最小值的过程中有两个不同的阶段。当x0是离答案比较远的时候，我们希望方法生成的迭代可以平稳地移动到x*。在迭代的全局阶段，我们是满意的，如果误差不增加除了在最初的步骤中，误差不增加的意思，就是得到的xk越接近x*，例如：

在迭代的最后阶段，xk接近x*，我们想要快速收敛。下面的区别：

本部分提出的方法是下降方法，满足2.1中的在每一步迭代中的下降条件。从当前迭代开始的一步组成：

1.找到一个下降方向（后文讨论）

2.找到一个步长，给出一个好的下降值，下降方法的大致框架如下：

如果F（x+ah）是一个下降函数，在a充分接近于0的时候，那么h就可以称为是一个下降的方向。

则有如下定义：

如果没有这样的h存在，那么F’（x）=0，表明x是一个驻点。否则，我们就选择a，例如 我们应该在hd的方向上远离x多少，以使得对目标函数的一个下降，通过以下式来实现

这个过程称为线性搜索，在2.3节讨论，首先，我们将引入两个计算下降方向的方法。

2.1 The Steepest Descent method(最速下降法)

从（2.5）我们可以看出，当我们执行一个步长ah，a为正，然后在函数中的相对增长满足

θ是向量h和F’（x）之间的夹角。如果θ=pi，则可以获得最大的增长率，例如，如果我们使用最速下降方向hsd，

上面求导的式子要大于零，才会说明走的一个步长得出的值是比F（x）要小，那么只有cosθ取负值，得到的正数才是最大的，就是h的方向和F’（x）的方向成pi角度，那么就可以对方向的取值，使用上式子（2.8）

那么基于式子（2.8）的方法就称为最速下降法或者梯度下降法。下降方法的选择是局部最好的，且我们可以将它与一个准确的线性搜索（2.7）相结合。

像这样方法的收敛，但是在最后的收敛是线性的且通常很慢。在Frandsen et al (2004)的例子中，去找一个二次多项式的最小值失败了。对于许多问题，这个方法在迭代的初始阶段是很有效的。

基于这种考虑，就导致了混合方法，基于不同的方法来实现。一种是在初始阶段表现很好，像梯度方法，另外一种是在最后阶段表现很好，像牛顿方法；混合方法最主要的问题是如何采用合适的机制在不同方法之间进行切换。

2.2 牛顿方法

我们可以从条件x*是一个驻点开始进行推导。根据定义1.6，它满足F’（x*）=0.这是一个非线性的系统方程，从泰勒展开如下

（倒推？？）我们推导牛顿方法：寻找hn作为下面答案

然后计算下一次迭代

假设H是正定的，它是非奇的（表明2.9a有唯一的解）且

表明hn是一个下降方向：它满足定义2.6。

通过2.10得出上面的式子2.9a满足，那么就可以从2.9a中得到hn的值，不过要计算Hessian矩阵，很麻烦。

牛顿方法在最后的（当x接近x*）迭代阶段是很好的，可以证明（see Frandsen et al (2004)）如果在答案处Hessian是正定的（定理1.8中充分条件满足）且如果我们在x*周围的一个区域内，在该区域内F''(X)是正定的，然后我们得到二次收敛（定义在（2.3）），另一方面，如果x是在一个区域内，F''(X)是处处负定的，那么这是一个驻点，且基本的牛顿方法会二次趋向于驻点，该点是最大点。我们可以通过所有的步骤按照下降的方向来避免这种情况。

我们可以构建一个混合的方法，基于牛顿方法和最速下降法。根据(2.10)牛顿方法在下降的时候要保证F’’（x）是正定的，因此混合算法的主要部分如下：

在这儿，hsd是最速下降的方向，且a由线性搜索找到；在2.3节中，用于检查一个矩阵的正定性是Cholesky方法，该方法用于解决线性系统中你的问题。

在2.4节中，我们介绍一些方法，里面介绍了同事计算搜索方向hd和步长a。这样的混合方法非常有效，但是使用很难，因为需要实现F’’（x），对于复杂系统这个是不可用的。这样我们就使用所谓的高斯牛顿方法基于一系列的矩阵接近H*=F''(x*).在3.4节提出上述方法。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。