高斯-牛顿法

对于目标函数为平方和形式     

的极小化问题,往往可以利用问题的这一特殊结构. 通过计算残差函数 ,和它的导数,以及雅克比 ,我们可以节约时间和精力. 高斯-牛顿法就是用来解决这一问题的巧妙方法. 高斯-牛顿法没有使用二次模型的整个二阶Hessian矩阵,而是在 (1) 中使用 ,这样就使得步骤 可以用公式

来计算,其中 ,等等. 请注意, 这是对完整Hessian,即 的近似. 在残差为零的情况下,即 是极小值时,或者当 在极小值点附近线性变化时,对 Hessian 的近似是相当不错的,并且牛顿法的二次收敛性也通常得到遵守.

平方和形式的目标函数是很常见的,而且实际上,这正是使用 FindFit 时,选用 NormFunction 选项的默认值的情况下,目标函数的形式. 考查高斯-牛顿法的方法之一,是以最小二乘问题的形式. 求解高斯-牛顿步骤与求解线性最小二乘问题相同, 所以应用一个高斯-牛顿方法实际上是对一个对非线性函数采取一系列的线性最小二乘拟合. 从这一观点来看,说这种方法尤其适用于FindFit 所进行的一类非线性拟合就可以理解了.

这里加载一个包含一些功用函数的程序包.
In[1]:=
Click for copyable input
这里使用非约束问题的程序包,来建立经典Rosenbrock函数,它有一个狭窄弯曲的谷部.
In[2]:=
Click for copyable input
Out[2]=

当 Wolfram 语言遇到一个明确表示为平方和形式的问题,比如Rosenbrock的例子,或者是一个向量和自身点乘形式的函数,高斯-牛顿法就会自动被使用.

这里显示了对于Rosenbrock函数,使用高斯-牛顿法的 FindMinimum 所采取的步骤,这里对步骤控制采取了信赖域的方法.     
In[3]:=
Click for copyable input
Out[3]=

如果您比较一下相同的例子使用 牛顿法,您可以看到我们是用了较少的步骤数和求值次数完成的,这是因为高斯-牛顿法利用了问题的特殊结构的优点. 在极小值附近的收敛速度就和牛顿法的一样好,因为在极小值的残差为零.

LevenbergMarquardt 方法是使用信赖域 步骤控制法的高斯-牛顿方法(虽然这是在信赖域的普遍概念形成之前提出的). 您可以使用 FindMinimum 选项 Method->"LevenbergMarquardt" 或者等效的 Method->"GaussNewton" 具体要求使用该方法.

有时候把函数明确表达为平方和的形式或者是向量和自身点乘的形式是有些别扭的. 在这种情况下,我们有可能可以使用 方法选项直接具体指定残差. 同样,您可以通过 方法选项具体指定残差的导数. 请注意,当通过 方法选项具体指定残差时,它不会就是否与FindMinimum 的第一个参数一致进行检查. 返回的值将取决于通过选项给定的值.

这里我们使用具体指定的残差寻找Rosenbrock函数的极小值.
In[4]:=
Click for copyable input
Out[4]=
选项名
默认值
"Residual"Automatic允许您直接指定残差 使得
"EvaluationMonitor"Automatic每次对残差求值时一同求值的表达式
"Jacobian"Automatic允许您指定残差的(矩阵)导数
"StepControl""TrustRegion"必须是 ,但是允许您通过方法选项改变控制参数

Method->"LevenbergMarquardt" 的方法选项.

另一种在 Wolfram 语言中建立平方和形式的问题的自然方式是使用 FindFit,它是计算数据的非线性拟合的. 下面是一个简单的例子.

这是一个模型函数.
In[5]:=
Click for copyable input
以下是加了一些随机扰动后该函数所产生的数据.
In[6]:=
Click for copyable input
这里寻找模型函数的一个非线性最小二乘拟合.
In[7]:=
Click for copyable input
Out[7]=
这里显示对数据的拟合模型.
In[8]:=
Click for copyable input
Out[8]=

在这个例子中,FindFit 在内部建立一个残差函数和雅克比,进而为高斯-牛顿法所用以寻找平方和的最小值,或者是非线性最小二乘拟合. 当然,FindFit 可以和其他方法一起使用,但由于可以构造能够迅速求值的残差函数,它常常快于其他方法.