无约束非线性优化算法
无约束优化定义
无约束最小化是求向量的问题x这是标量函数的局部最小值f(x):
这个词<年代pan class="emphasis">无约束的范围上没有任何限制x.
fminunc信赖域算法
非线性极小化的信赖域方法
优化工具箱™求解器中使用的许多方法都是基于<年代pan class="emphasis">信任区域,优化中的一个简单而强大的概念。
为了理解信任域优化方法,考虑无约束最小化问题,最小化f(x),其中函数接受向量参数并返回标量。假设你在某一点上x在n-空间,你想要改进,即移动到函数值较低的点。基本思想是近似f用一个更简单的函数问,合理地反映了函数的行为f在一个社区N围绕这一点x.这个区域是信任区域。试验步骤年代是通过最小化(或近似最小化)来计算的N.这是信任域子问题,
(1)
当前点被更新为x+年代如果<年代pan class="inlineequation">f(x+年代) <f(x);否则,当前点保持不变N,缩小信任区域,重复试步计算。
定义特定信任区域最小化方法的关键问题f(x)是如何选择和计算近似值问(定义在当前点x),如何选择和修改信任区域N,以及如何准确地求解信赖域子问题。本节主要讨论无约束问题。后面的部分讨论由于变量约束的存在而产生的其他复杂性。
在标准信赖域方法中([48]),即二次逼近问是由泰勒近似的前两项定义的F在x;附近N通常在形状上呈球形或椭球形。在数学上,信任域子问题是典型的表述
(2)
在哪里g的梯度f在目前的情况下x,H为海森矩阵(二阶导数的对称矩阵),D为对角线缩放矩阵,Δ为正标量,‖。‖是2范数。好的算法是存在的方程2(见[48]);的所有特征值的计算H牛顿过程应用于特征方程
这种算法提供了一个精确的解方程2.然而,它们需要的时间与因数分解成正比H.因此,对于大规模的问题,需要不同的方法。几种近似和启发式策略,基于方程2,已在文献中提出([42]而且[50]).优化工具箱求解器中遵循的近似方法是将信任域子问题限制为二维子空间年代([39]而且[42]).一旦子空间年代算过了,功要解吗方程2是微不足道的,即使需要完整的特征值/特征向量信息(因为在子空间中,问题只是二维的)。现在主要的工作已经转移到子空间的确定上。
二维子空间年代是借助一个预条件共轭梯度过程描述如下。求解器定义了年代由张成的线性空间年代1而且年代2,在那里年代1在梯度方向上g,年代2要么是近似值牛顿方向,即解到
(3)
或者一个方向负曲率,
(4)
这种选择背后的哲学年代是强迫全局收敛(通过最陡峭的下降方向或负曲率方向),并实现快速的局部收敛(通过牛顿阶跃,当它存在时)。
使用信任域思想的无约束最小化的草图现在很容易给出:
给出二维信赖域子问题。
解决方程2确定试验步骤年代.
如果<年代pan class="inlineequation">f(x+年代) <f(x),然后<年代pan class="inlineequation">x=x+年代.
Δ调整。
重复这四个步骤直到收敛为止。信任域维度Δ根据标准规则进行调整。特别是,如果不接受试验步骤,则减少,即,<年代pan class="inlineequation">f(x+年代)≥f(x).看到[46]而且[49]对于这方面的讨论。
优化工具箱求解器处理一些重要的特殊情况f有专门的函数:非线性最小二乘,二次函数,线性最小二乘。然而,基本的算法思想与一般情况是相同的。这些特殊情况将在后面的章节中讨论。
预条件共轭梯度法
一种常用的解大型对称正定线性方程组的方法<年代pan class="inlineequation">惠普= -g为预条件共轭梯度法(PCG)。这种迭代方法要求能够计算这种形式的矩阵-向量乘积2022世界杯八强谁会赢?H·v在哪里v是任意向量。对称正定矩阵米是一个<年代pan class="emphasis">预调节器为H.也就是说,<年代pan class="inlineequation">米=C2,在那里<年代pan class="inlineequation">C1HC1是一个良好条件矩阵或具有聚类特征值的矩阵。
在最小化的情况下,你可以假设黑森矩阵H是对称的。然而,H只有在强最小值附近才保证是正定的。PCG算法在遇到负(或零)曲率方向时退出,即:<年代pan class="inlineequation">d<年代up>T高清≤0.PCG输出方向p要么是负曲率方向,要么是牛顿系的近似解<年代pan class="inlineequation">惠普= -g.无论哪种情况,p有助于定义中讨论的信赖域方法中使用的二维子空间非线性极小化的信赖域方法.
fminunc拟牛顿算法<年代pan id="unconstrained_opt" class="anchor_target">
无约束优化基础
尽管存在广泛的无约束优化方法,但方法可以根据使用或不使用的衍生信息进行广泛的分类。只使用函数求值的搜索方法(例如,Nelder和Mead的单纯形搜索)[30])最适合处理不光滑或有许多不连续的问题。当要最小化的函数一阶导数连续时,梯度法通常更有效。高阶方法,如牛顿方法,只有在二阶信息易于计算时才真正适用,因为使用数值微分计算二阶信息,计算成本很高。
梯度方法使用关于函数斜率的信息来指示搜索方向,其中最小值被认为所在。其中最简单的方法是快速下降法,即沿着一个方向进行搜索,<年代pan class="inlineequation">——∇f(x),在那里<年代pan class="inlineequation">∇f(x)是目标函数的梯度。当要最小化的函数具有长而窄的山谷时,这种方法是非常低效的,例如,是。海涅的功能
(5)
这个函数的最小值是<年代pan class="inlineequation">x= [1],在那里<年代pan class="inlineequation">f(x) = 0.该函数的等高线图如下图所示,以及从点[-1.9,2]开始的最陡下降实现的最小值解路径。优化在1000次迭代后终止,距离最小值仍有相当大的距离。黑色区域是方法从山谷的一边到另一边不断曲折的地方。请注意,当一个点恰好落在山谷的中心时,朝着图的中心,会采取一些更大的步骤。
图5-1 Rosenbrock函数的最陡下降法
这个函数,也被称为香蕉函数,在无约束的例子中是臭名昭著的,因为曲率在原点周围弯曲。本节将使用Rosenbrock函数来说明各种优化技术的使用。由于u形山谷周围的斜坡很陡,等高线以指数增量绘制。
有关该图的更完整的描述,包括生成迭代点的脚本,请参见香蕉函数最小化.
拟牛顿方法
在使用梯度信息的方法中,最受欢迎的是准牛顿方法。这些方法在每次迭代中建立曲率信息,以制定形式的二次模型问题
(6)
其中黑森矩阵,H为正定对称矩阵,c是常数向量,和b是常数。的偏导数时,该问题的最优解x归零,也就是说,
(7)
最优解点,x*,可以写成
(8)
牛顿型方法(相对于准牛顿方法)计算H直接,并在下降的方向上进行,以确定经过多次迭代后的最小值。计算H在数值上涉及大量的计算。准牛顿方法通过使用观察到的行为来避免这种情况f(x),<年代pan class="inlineequation">∇f(x)建立曲率信息来进行近似H使用适当的更新技术。
大量的Hessian更新方法已经被开发出来。然而,布洛伊登公式[3],弗莱彻[12]戈德法布,[20],和山诺[37](BFGS)被认为是最有效的通用方法。
BFGS给出的公式为
(9)
在哪里
作为起点,H0可以设为任何对称正定矩阵,例如,单位矩阵我.为了避免黑森的反转H,您可以派生出一种避免直接反转的更新方法H通过使用一个公式来近似逆黑森函数H1每次更新。一个著名的程序是Davidon的DFP公式[7]弗莱彻和鲍威尔[14].此方法使用与BFGS方法相同的公式(方程9)除了问<年代ub>k被替换为年代<年代ub>k.
梯度信息要么通过分析计算梯度提供,要么通过有限差分的数值微分方法由偏导数导出。这涉及到扰动每个设计变量,x,依次计算目标函数的变化率。
在每个主要迭代中,k时,沿该方向进行直线搜索
(10)
拟牛顿法通过求解路径的形式进行了说明Rosenbrock的作用图5-2关于Rosenbrock函数的BFGS方法.该方法能够遵循山谷的形状,并在仅使用有限差分梯度的140个函数评估后收敛到最小值。
图5-2关于Rosenbrock函数的BFGS方法
有关该图的更完整的描述,包括生成迭代点的脚本,请参见香蕉函数最小化.
线搜索
线搜索 是一种搜索方法,用作大型优化算法的一部分。在主算法的每一步中,直线搜索方法沿着包含当前点的直线搜索,x<年代ub>k,平行于<年代pan class="emphasis">搜索方向,这是一个由主算法确定的向量。也就是说,该方法查找下一个迭代xk+1形式的
(11)
在哪里x<年代ub>k
表示当前迭代,d<年代ub>k 是搜索方向,和α*是标量步长参数。
直线搜索法试图沿直线减小目标函数<年代pan class="inlineequation">x<年代ub>k +α*d<年代ub>k通过反复最小化目标函数的多项式插值模型。行搜索过程有两个主要步骤:
的<年代pan class="emphasis">夹叉射击相位决定了直线上点的范围<年代pan class="inlineequation">
被搜索。的<年代pan class="emphasis">支架对应于指定值范围的间隔α.
的<年代pan class="emphasis">切片Step将括号划分为子区间,在子区间上用多项式插值逼近目标函数的最小值。
得到的步长α满足Wolfe条件:
(12)
(13)
在哪里c1而且c2是0 <的常数c1<c2< 1。
第一个条件(方程12)要求α<年代ub>k充分减小目标函数。第二个条件(方程13)确保步长不会太小。同时满足两个条件的点(方程12而且方程13)被称为<年代pan class="emphasis">可接受的点.
的第2-6节中描述的算法的实现[13].另请参阅[31]有关行搜索的更多信息。
黑森更新
许多优化函数通过每次迭代更新Hessian矩阵来确定搜索方向,使用BFGS方法(方程9).这个函数fminunc还提供了一个选项来使用中给出的DFP方法拟牛顿方法(设置HessUpdate来“dfp”在选项选择DFP方法)。海赛,H,总是正确定的,所以搜索的方向,d,总是在一个下降的方向。这意味着对于任意小的步长α在方向上d时,目标函数大小递减。你得到的正确定性H通过确保H初始化为正定,然后<年代pan class="inlineequation">
(从方程14)总是积极的。这个词<年代pan class="inlineequation">
直线搜索步长参数的乘积吗α<年代ub>k和搜索方向的组合d通过过去和现在的梯度计算,
(14)
你总是能达到这样的条件<年代pan class="inlineequation">
通过执行足够精确的直线搜索为正值。这是因为搜索方向,d,是一个下降的方向,所以α<年代ub>k还有负梯度<年代pan class="inlineequation">——∇f(x<年代ub>k)Td总是积极的。因此,可能的负项<年代pan class="inlineequation">——∇f(xk+1)Td通过增加直线搜索的精度,可以使其在量级上尽可能小。
LBFGS黑森近似
对于大型问题,BFGS Hessian近似方法可能相对较慢,并使用大量内存。为了避免这些问题,使用LBFGS黑森近似通过设置HessianApproximation选项“lbfgs”.这将导致fminunc使用低内存BFGS黑森近似,如下所述。有关在大型问题中使用LBFGS的好处,请参见求解多变量非线性问题.
正如Nocedal和Wright所描述的[31],低内存BFGS黑森近似与中描述的BFGS近似相似拟牛顿方法,但是对以前的迭代使用有限的内存。式中给出的黑森更新公式方程9是
在哪里
BFGS过程的另一种描述是
(15)
在哪里ɑ<年代ub>k步长是由直线搜索选择的,和H<年代ub>k是逆黑森近似。的公式H<年代ub>k:
在哪里年代<年代ub>k而且问<年代ub>k和之前一样定义,和
对于LBFGS算法,算法保持一个固定的、有限的数字米这些参数年代<年代ub>k而且问<年代ub>k从前面的迭代中。从首字母开始H<年代ub>0时,算法计算一个近似值H<年代ub>k获取的步骤方程15.的计算<年代pan class="inlineequation">
从前面的方程中使用最新的递归进行米的值ρ<年代ub>j,问<年代ub>j,年代<年代ub>j.具体请参见Nocedal和Wright的算法7.4[31].
另请参阅
相关的话题
无约束优化定义
无约束最小化是求向量的问题x这是标量函数的局部最小值f(x):
这个词<年代pan class="emphasis">无约束的范围上没有任何限制x.
无约束最小化是求向量的问题
这个词<年代pan class="emphasis">无约束
fminunc信赖域算法
非线性极小化的信赖域方法
优化工具箱™求解器中使用的许多方法都是基于<年代pan class="emphasis">信任区域,优化中的一个简单而强大的概念。
为了理解信任域优化方法,考虑无约束最小化问题,最小化f(x),其中函数接受向量参数并返回标量。假设你在某一点上x在n-空间,你想要改进,即移动到函数值较低的点。基本思想是近似f用一个更简单的函数问,合理地反映了函数的行为f在一个社区N围绕这一点x.这个区域是信任区域。试验步骤年代是通过最小化(或近似最小化)来计算的N.这是信任域子问题,
(1)
当前点被更新为x+年代如果<年代pan class="inlineequation">f(x+年代) <f(x);否则,当前点保持不变N,缩小信任区域,重复试步计算。
定义特定信任区域最小化方法的关键问题f(x)是如何选择和计算近似值问(定义在当前点x),如何选择和修改信任区域N,以及如何准确地求解信赖域子问题。本节主要讨论无约束问题。后面的部分讨论由于变量约束的存在而产生的其他复杂性。
在标准信赖域方法中([48]),即二次逼近问是由泰勒近似的前两项定义的F在x;附近N通常在形状上呈球形或椭球形。在数学上,信任域子问题是典型的表述
(2)
在哪里g的梯度f在目前的情况下x,H为海森矩阵(二阶导数的对称矩阵),D为对角线缩放矩阵,Δ为正标量,‖。‖是2范数。好的算法是存在的方程2(见[48]);的所有特征值的计算H牛顿过程应用于特征方程
这种算法提供了一个精确的解方程2.然而,它们需要的时间与因数分解成正比H.因此,对于大规模的问题,需要不同的方法。几种近似和启发式策略,基于方程2,已在文献中提出([42]而且[50]).优化工具箱求解器中遵循的近似方法是将信任域子问题限制为二维子空间年代([39]而且[42]).一旦子空间年代算过了,功要解吗方程2是微不足道的,即使需要完整的特征值/特征向量信息(因为在子空间中,问题只是二维的)。现在主要的工作已经转移到子空间的确定上。
二维子空间年代是借助一个预条件共轭梯度过程描述如下。求解器定义了年代由张成的线性空间年代1而且年代2,在那里年代1在梯度方向上g,年代2要么是近似值牛顿方向,即解到
(3)
或者一个方向负曲率,
(4)
这种选择背后的哲学年代是强迫全局收敛(通过最陡峭的下降方向或负曲率方向),并实现快速的局部收敛(通过牛顿阶跃,当它存在时)。
使用信任域思想的无约束最小化的草图现在很容易给出:
给出二维信赖域子问题。
解决方程2确定试验步骤年代.
如果<年代pan class="inlineequation">f(x+年代) <f(x),然后<年代pan class="inlineequation">x=x+年代.
Δ调整。
重复这四个步骤直到收敛为止。信任域维度Δ根据标准规则进行调整。特别是,如果不接受试验步骤,则减少,即,<年代pan class="inlineequation">f(x+年代)≥f(x).看到[46]而且[49]对于这方面的讨论。
优化工具箱求解器处理一些重要的特殊情况f有专门的函数:非线性最小二乘,二次函数,线性最小二乘。然而,基本的算法思想与一般情况是相同的。这些特殊情况将在后面的章节中讨论。
预条件共轭梯度法
一种常用的解大型对称正定线性方程组的方法<年代pan class="inlineequation">惠普= -g为预条件共轭梯度法(PCG)。这种迭代方法要求能够计算这种形式的矩阵-向量乘积2022世界杯八强谁会赢?H·v在哪里v是任意向量。对称正定矩阵米是一个<年代pan class="emphasis">预调节器为H.也就是说,<年代pan class="inlineequation">米=C2,在那里<年代pan class="inlineequation">C1HC1是一个良好条件矩阵或具有聚类特征值的矩阵。
在最小化的情况下,你可以假设黑森矩阵H是对称的。然而,H只有在强最小值附近才保证是正定的。PCG算法在遇到负(或零)曲率方向时退出,即:<年代pan class="inlineequation">d<年代up>T高清≤0.PCG输出方向p要么是负曲率方向,要么是牛顿系的近似解<年代pan class="inlineequation">惠普= -g.无论哪种情况,p有助于定义中讨论的信赖域方法中使用的二维子空间非线性极小化的信赖域方法.
信赖域算法
非线性极小化的信赖域方法
优化工具箱™求解器中使用的许多方法都是基于<年代pan class="emphasis">信任区域,优化中的一个简单而强大的概念。
为了理解信任域优化方法,考虑无约束最小化问题,最小化f(x),其中函数接受向量参数并返回标量。假设你在某一点上x在n-空间,你想要改进,即移动到函数值较低的点。基本思想是近似f用一个更简单的函数问,合理地反映了函数的行为f在一个社区N围绕这一点x.这个区域是信任区域。试验步骤年代是通过最小化(或近似最小化)来计算的N.这是信任域子问题,
(1)
当前点被更新为x+年代如果<年代pan class="inlineequation">f(x+年代) <f(x);否则,当前点保持不变N,缩小信任区域,重复试步计算。
定义特定信任区域最小化方法的关键问题f(x)是如何选择和计算近似值问(定义在当前点x),如何选择和修改信任区域N,以及如何准确地求解信赖域子问题。本节主要讨论无约束问题。后面的部分讨论由于变量约束的存在而产生的其他复杂性。
在标准信赖域方法中([48]),即二次逼近问是由泰勒近似的前两项定义的F在x;附近N通常在形状上呈球形或椭球形。在数学上,信任域子问题是典型的表述
(2)
在哪里g的梯度f在目前的情况下x,H为海森矩阵(二阶导数的对称矩阵),D为对角线缩放矩阵,Δ为正标量,‖。‖是2范数。好的算法是存在的方程2(见[48]);的所有特征值的计算H牛顿过程应用于特征方程
这种算法提供了一个精确的解方程2.然而,它们需要的时间与因数分解成正比H.因此,对于大规模的问题,需要不同的方法。几种近似和启发式策略,基于方程2,已在文献中提出([42]而且[50]).优化工具箱求解器中遵循的近似方法是将信任域子问题限制为二维子空间年代([39]而且[42]).一旦子空间年代算过了,功要解吗方程2是微不足道的,即使需要完整的特征值/特征向量信息(因为在子空间中,问题只是二维的)。现在主要的工作已经转移到子空间的确定上。
二维子空间年代是借助一个预条件共轭梯度过程描述如下。求解器定义了年代由张成的线性空间年代1而且年代2,在那里年代1在梯度方向上g,年代2要么是近似值牛顿方向,即解到
(3)
或者一个方向负曲率,
(4)
这种选择背后的哲学年代是强迫全局收敛(通过最陡峭的下降方向或负曲率方向),并实现快速的局部收敛(通过牛顿阶跃,当它存在时)。
使用信任域思想的无约束最小化的草图现在很容易给出:
给出二维信赖域子问题。
解决方程2确定试验步骤年代.
如果<年代pan class="inlineequation">f(x+年代) <f(x),然后<年代pan class="inlineequation">x=x+年代.
Δ调整。
重复这四个步骤直到收敛为止。信任域维度Δ根据标准规则进行调整。特别是,如果不接受试验步骤,则减少,即,<年代pan class="inlineequation">f(x+年代)≥f(x).看到[46]而且[49]对于这方面的讨论。
优化工具箱求解器处理一些重要的特殊情况f有专门的函数:非线性最小二乘,二次函数,线性最小二乘。然而,基本的算法思想与一般情况是相同的。这些特殊情况将在后面的章节中讨论。
预条件共轭梯度法
一种常用的解大型对称正定线性方程组的方法<年代pan class="inlineequation">惠普= -g为预条件共轭梯度法(PCG)。这种迭代方法要求能够计算这种形式的矩阵-向量乘积2022世界杯八强谁会赢?H·v在哪里v是任意向量。对称正定矩阵米是一个<年代pan class="emphasis">预调节器为H.也就是说,<年代pan class="inlineequation">米=C2,在那里<年代pan class="inlineequation">C1HC1是一个良好条件矩阵或具有聚类特征值的矩阵。
在最小化的情况下,你可以假设黑森矩阵H是对称的。然而,H只有在强最小值附近才保证是正定的。PCG算法在遇到负(或零)曲率方向时退出,即:<年代pan class="inlineequation">d<年代up>T高清≤0.PCG输出方向p要么是负曲率方向,要么是牛顿系的近似解<年代pan class="inlineequation">惠普= -g.无论哪种情况,p有助于定义中讨论的信赖域方法中使用的二维子空间非线性极小化的信赖域方法.
fminunc拟牛顿算法<年代pan id="unconstrained_opt" class="anchor_target">
拟牛顿算法<年代pan id="unconstrained_opt" class="anchor_target">
无约束优化基础
尽管存在广泛的无约束优化方法,但方法可以根据使用或不使用的衍生信息进行广泛的分类。只使用函数求值的搜索方法(例如,Nelder和Mead的单纯形搜索)[30])最适合处理不光滑或有许多不连续的问题。当要最小化的函数一阶导数连续时,梯度法通常更有效。高阶方法,如牛顿方法,只有在二阶信息易于计算时才真正适用,因为使用数值微分计算二阶信息,计算成本很高。
梯度方法使用关于函数斜率的信息来指示搜索方向,其中最小值被认为所在。其中最简单的方法是快速下降法,即沿着一个方向进行搜索,<年代pan class="inlineequation">——∇f(x),在那里<年代pan class="inlineequation">∇f(x)是目标函数的梯度。当要最小化的函数具有长而窄的山谷时,这种方法是非常低效的,例如,是。海涅的功能
(5)
这个函数的最小值是<年代pan class="inlineequation">x= [1],在那里<年代pan class="inlineequation">f(x) = 0.该函数的等高线图如下图所示,以及从点[-1.9,2]开始的最陡下降实现的最小值解路径。优化在1000次迭代后终止,距离最小值仍有相当大的距离。黑色区域是方法从山谷的一边到另一边不断曲折的地方。请注意,当一个点恰好落在山谷的中心时,朝着图的中心,会采取一些更大的步骤。
图5-1 Rosenbrock函数的最陡下降法
这个函数,也被称为香蕉函数,在无约束的例子中是臭名昭著的,因为曲率在原点周围弯曲。本节将使用Rosenbrock函数来说明各种优化技术的使用。由于u形山谷周围的斜坡很陡,等高线以指数增量绘制。
有关该图的更完整的描述,包括生成迭代点的脚本,请参见香蕉函数最小化.
尽管存在广泛的无约束优化方法,但方法可以根据使用或不使用的衍生信息进行广泛的分类。只使用函数求值的搜索方法(例如,Nelder和Mead的单纯形搜索) 梯度方法使用关于函数斜率的信息来指示搜索方向,其中最小值被认为所在。其中最简单的方法是快速下降法,即沿着一个方向进行搜索,<年代pan class="inlineequation">——∇ 这个函数的最小值是<年代pan class="inlineequation">x 图5-1 Rosenbrock函数的最陡下降法 这个函数,也被称为香蕉函数,在无约束的例子中是臭名昭著的,因为曲率在原点周围弯曲。本节将使用Rosenbrock函数来说明各种优化技术的使用。由于u形山谷周围的斜坡很陡,等高线以指数增量绘制。 有关该图的更完整的描述,包括生成迭代点的脚本,请参见
(5)
拟牛顿方法
在使用梯度信息的方法中,最受欢迎的是准牛顿方法。这些方法在每次迭代中建立曲率信息,以制定形式的二次模型问题
(6)
其中黑森矩阵,H为正定对称矩阵,c是常数向量,和b是常数。的偏导数时,该问题的最优解x归零,也就是说,
(7)
最优解点,x*,可以写成
(8)
牛顿型方法(相对于准牛顿方法)计算H直接,并在下降的方向上进行,以确定经过多次迭代后的最小值。计算H在数值上涉及大量的计算。准牛顿方法通过使用观察到的行为来避免这种情况f(x),<年代pan class="inlineequation">∇f(x)建立曲率信息来进行近似H使用适当的更新技术。
大量的Hessian更新方法已经被开发出来。然而,布洛伊登公式[3],弗莱彻[12]戈德法布,[20],和山诺[37](BFGS)被认为是最有效的通用方法。
BFGS给出的公式为
(9)
在哪里
作为起点,H0可以设为任何对称正定矩阵,例如,单位矩阵我.为了避免黑森的反转H,您可以派生出一种避免直接反转的更新方法H通过使用一个公式来近似逆黑森函数H1每次更新。一个著名的程序是Davidon的DFP公式[7]弗莱彻和鲍威尔[14].此方法使用与BFGS方法相同的公式(方程9)除了问<年代ub>k被替换为年代<年代ub>k.
梯度信息要么通过分析计算梯度提供,要么通过有限差分的数值微分方法由偏导数导出。这涉及到扰动每个设计变量,x,依次计算目标函数的变化率。
在每个主要迭代中,k时,沿该方向进行直线搜索
(10)
拟牛顿法通过求解路径的形式进行了说明Rosenbrock的作用图5-2关于Rosenbrock函数的BFGS方法.该方法能够遵循山谷的形状,并在仅使用有限差分梯度的140个函数评估后收敛到最小值。
图5-2关于Rosenbrock函数的BFGS方法
有关该图的更完整的描述,包括生成迭代点的脚本,请参见香蕉函数最小化.
在使用梯度信息的方法中,最受欢迎的是准牛顿方法。这些方法在每次迭代中建立曲率信息,以制定形式的二次模型问题 其中黑森矩阵, 最优解点, 牛顿型方法(相对于准牛顿方法)计算 大量的Hessian更新方法已经被开发出来。然而,布洛伊登公式 BFGS给出的公式为 在哪里
作为起点, 梯度信息要么通过分析计算梯度提供,要么通过有限差分的数值微分方法由偏导数导出。这涉及到扰动每个设计变量, 在每个主要迭代中, 拟牛顿法通过求解路径的形式进行了说明 图5-2关于Rosenbrock函数的BFGS方法 有关该图的更完整的描述,包括生成迭代点的脚本,请参见
(6)
(7)
(8)
(9)
(10)
线搜索
线搜索 是一种搜索方法,用作大型优化算法的一部分。在主算法的每一步中,直线搜索方法沿着包含当前点的直线搜索,x<年代ub>k,平行于<年代pan class="emphasis">搜索方向,这是一个由主算法确定的向量。也就是说,该方法查找下一个迭代xk+1形式的
(11)
在哪里x<年代ub>k
表示当前迭代,d<年代ub>k 是搜索方向,和α*是标量步长参数。
直线搜索法试图沿直线减小目标函数<年代pan class="inlineequation">x<年代ub>k +α*d<年代ub>k通过反复最小化目标函数的多项式插值模型。行搜索过程有两个主要步骤:
的<年代pan class="emphasis">夹叉射击相位决定了直线上点的范围<年代pan class="inlineequation">
被搜索。的<年代pan class="emphasis">支架对应于指定值范围的间隔α.
的<年代pan class="emphasis">切片Step将括号划分为子区间,在子区间上用多项式插值逼近目标函数的最小值。
得到的步长α满足Wolfe条件:
(12)
(13)
在哪里c1而且c2是0 <的常数c1<c2< 1。
第一个条件(方程12)要求α<年代ub>k充分减小目标函数。第二个条件(方程13)确保步长不会太小。同时满足两个条件的点(方程12而且方程13)被称为<年代pan class="emphasis">可接受的点.
的第2-6节中描述的算法的实现[13].另请参阅[31]有关行搜索的更多信息。
线搜索 在哪里 直线搜索法试图沿直线减小目标函数<年代pan class="inlineequation">x<年代ub>k 的<年代pan class="emphasis">夹叉射击 的<年代pan class="emphasis">切片 得到的步长α满足Wolfe条件: 在哪里 第一个条件( 的第2-6节中描述的算法的实现
(11)
(12)
(13)
黑森更新
许多优化函数通过每次迭代更新Hessian矩阵来确定搜索方向,使用BFGS方法(方程9).这个函数fminunc还提供了一个选项来使用中给出的DFP方法拟牛顿方法(设置HessUpdate来“dfp”在选项选择DFP方法)。海赛,H,总是正确定的,所以搜索的方向,d,总是在一个下降的方向。这意味着对于任意小的步长α在方向上d时,目标函数大小递减。你得到的正确定性H通过确保H初始化为正定,然后<年代pan class="inlineequation">
(从方程14)总是积极的。这个词<年代pan class="inlineequation">
直线搜索步长参数的乘积吗α<年代ub>k和搜索方向的组合d通过过去和现在的梯度计算,
(14)
你总是能达到这样的条件<年代pan class="inlineequation">
通过执行足够精确的直线搜索为正值。这是因为搜索方向,d,是一个下降的方向,所以α<年代ub>k还有负梯度<年代pan class="inlineequation">——∇f(x<年代ub>k)Td总是积极的。因此,可能的负项<年代pan class="inlineequation">——∇f(xk+1)Td通过增加直线搜索的精度,可以使其在量级上尽可能小。
许多优化函数通过每次迭代更新Hessian矩阵来确定搜索方向,使用BFGS方法( 你总是能达到这样的条件<年代pan class="inlineequation">
通过执行足够精确的直线搜索为正值。这是因为搜索方向,fminunc
(14)
LBFGS黑森近似
对于大型问题,BFGS Hessian近似方法可能相对较慢,并使用大量内存。为了避免这些问题,使用LBFGS黑森近似通过设置HessianApproximation选项“lbfgs”.这将导致fminunc使用低内存BFGS黑森近似,如下所述。有关在大型问题中使用LBFGS的好处,请参见求解多变量非线性问题.
正如Nocedal和Wright所描述的[31],低内存BFGS黑森近似与中描述的BFGS近似相似拟牛顿方法,但是对以前的迭代使用有限的内存。式中给出的黑森更新公式方程9是
在哪里
BFGS过程的另一种描述是
(15)
在哪里ɑ<年代ub>k步长是由直线搜索选择的,和H<年代ub>k是逆黑森近似。的公式H<年代ub>k:
在哪里年代<年代ub>k而且问<年代ub>k和之前一样定义,和
对于LBFGS算法,算法保持一个固定的、有限的数字米这些参数年代<年代ub>k而且问<年代ub>k从前面的迭代中。从首字母开始H<年代ub>0时,算法计算一个近似值H<年代ub>k获取的步骤方程15.的计算<年代pan class="inlineequation">
从前面的方程中使用最新的递归进行米的值ρ<年代ub>j,问<年代ub>j,年代<年代ub>j.具体请参见Nocedal和Wright的算法7.4[31].
对于大型问题,BFGS Hessian近似方法可能相对较慢,并使用大量内存。为了避免这些问题,使用LBFGS黑森近似通过设置 正如Nocedal和Wright所描述的
在哪里
BFGS过程的另一种描述是 在哪里
在哪里
对于LBFGS算法,算法保持一个固定的、有限的数字
(15)