无约束极小化就是求向量的问题
这个词无拘无束
fminunc信赖域算法
非线性极小化的信赖域方法
最优化工具箱™求解器中使用的许多方法都基于信任区域, 一个简单但强大的优化概念。
为了理解信任域优化方法,考虑无约束极小化问题,最小化F(x),其中函数接受向量参数并返回标量。假设你在一个点上x在里面N-space,如果您想要改进,即移动到一个函数值较低的点。基本思想是近似F用一个简单的函数Q,它合理地反映了功能的行为F在附近N周围的点x.这个社区是信任区域。试验步骤s是通过最小化(或近似最小化)除以来计算的吗N. 这是信赖域子问题,
(1)
当前点将更新为x+s如果F(x+s) <F(x);否则,当前点保持不变N缩小信任区域,并重复试验步骤计算。
定义特定信赖域最小化方法的关键问题F(x)是如何选择和计算近似值Q(在当前点定义x),如何选择和修改信任区域N,以及如何准确地解决信任区域子问题。本节重点讨论无约束问题。后面的部分将讨论由于变量上存在约束而导致的其他复杂性。
在标准信赖域方法中([48]),即二次逼近Q是由泰勒近似的前两项定义的F在x;附近N通常为球形或椭球形。从数学上讲,信赖域子问题是典型的
(2)
在哪里G为梯度F在目前x,H为Hessian矩阵(二阶导数的对称矩阵),D是对角缩放矩阵,Δ是正标量,并且∥ . ∥ 这是2-norm。有很好的算法来解决这个问题方程2(见[48]);这种算法通常涉及到的所有特征值的计算H牛顿过程应用于特征方程
这样的算法提供了一个精确的解决方案方程2.然而,它们需要的时间与的几个因数成正比H.因此,对于大规模的问题,需要一种不同的方法。几种近似和启发式策略,基于方程2,已在文献中提出([42]和[50]). 在优化工具箱求解器中采用的近似方法是将信赖域子问题限制为二维子空间s([39]和[42]).一旦子空间s已计算,需要解决的工作方程2即使需要完整的特征值/特征向量信息,也是琐碎的(因为在子空间中,问题只是二维的)。现在主要的工作已经转移到确定子空间。
二维子空间s是由a下面描述的预处理共轭梯度过程。解算器定义s作为跨越的线性空间s1.和s2.,在那里s1.在梯度的方向上G,s2.是一个近似值牛顿方向,即
(3)
或者一个方向负曲率,
(4)
这种选择背后的哲学s是迫使全局收敛(通过最陡下降方向或负曲率方向),并实现快速局部收敛(通过牛顿步,当它存在时)。
使用信任区域思想的无约束最小化的草图现在很容易给出:
构造二维信赖域子问题。
解决方程2确定试验步骤s.
如果F(x+s) <F(x)那么x=x+s .
Δ调整。
这四个步骤重复,直到收敛。信任区域维度Δ根据标准规则进行调整。特别是,如果试验步骤不被接受,它就会减少,即:F(x+s) ≥F(x).看到[46]和[49]对于这方面的讨论。
最优化工具箱求解器处理一些重要的特殊情况F特殊函数:非线性最小二乘,二次函数,线性最小二乘。然而,基本的算法思想与一般情况相同。这些特殊情况将在后面的小节中讨论。
预条件共轭梯度法
求解大型、对称、正定线性方程组的一种流行方法惠普= –G 是预处理共轭梯度法(PCG)。这种迭代方法需要能够计算形式的矩阵向量积s manbetx 845H·v在哪里v是一个任意向量。对称正定矩阵M是一个预处理器 对于H.也就是说,M=C2. ,在那里C1HC1 是一个良好条件矩阵或具有聚类特征值的矩阵。
在最小化的情况下,你可以假设Hessian矩阵H是对称的。然而,H仅在强极小化器的邻域内保证是正定的。算法PCG在遇到负(或零)曲率方向时退出,即:DT高清≤0.PCG输出方向P是负曲率的方向还是牛顿方程组的近似解惠普= –G .在这两种情况下,P有助于定义信任域方法中使用的二维子空间非线性极小化的信赖域方法.
fminunc拟牛顿法算法
无约束优化基础
虽然无约束优化方法的范围很广,但方法可以根据使用或不使用的导数信息进行广泛的分类。只使用函数计算的搜索方法(例如,Nelder和Mead的单纯形搜索)[30])最适用于非光滑或有许多不连续点的问题。当要最小化的函数在一阶导数中是连续的时,梯度法通常更有效。高阶方法,如牛顿法,只适用于二阶信息容易计算的情况,因为二阶信息的计算,使用数值微分,是昂贵的。
梯度法利用函数的斜率信息来确定搜索的方向,即最小值所在的位置。其中最简单的方法是最陡下降法,这种方法是在一个方向上进行搜索,–∇F(x),在那里∇F(x)是目标函数的梯度。当要最小化的函数有很长很窄的谷时,这种方法是非常低效的,例如。海涅的功能
(5)
这个函数的最小值是atx= [1,1],在那里F(x) = 0. 下图显示了该函数的等高线图,以及从点[-1.9,2]开始的最陡下降实现的最小解路径。优化在1000次迭代后终止,距离最小值还有相当大的距离。黑色区域是该方法从山谷的一侧到另一侧不断曲折的地方。请注意,当一个点正好落在山谷中心时,朝向绘图中心会采取许多较大的步骤。
图6-1 Rosenbrock函数上的最陡下降法
这个函数,也被称为香蕉函数,在无约束的例子中因为曲率在原点附近弯曲的方式而臭名昭著。在本节中,我们将使用Rosenbrock函数来说明各种优化技术的使用。由于u形山谷周围的陡度,等高线以指数递增的方式绘制。
有关此图的更完整描述,包括生成迭代点的脚本,请参见香蕉函数最小化.
拟牛顿方法
在使用梯度信息的方法中,最受欢迎的是拟牛顿方法。这些方法在每次迭代时建立曲率信息,以形成形式的二次模型问题
(6)
其中Hessian矩阵,H,是正定对称矩阵,C是常数向量吗B是一个常数。当方程的偏导数x趋近于0,也就是,
(7)
最优解点,x*,可以写成
(8)
牛顿型方法(与拟牛顿法相反)计算H直接并沿着下降的方向进行,在多次迭代后确定最小值。计算H数值计算涉及大量计算。拟牛顿方法通过使用观测到的粒子行为来避免这种情况F(x),∇F(x)建立曲率信息以进行近似计算的步骤H使用适当的更新技术。
大量的Hessian更新方法已经被开发出来。但是,布洛伊登公式[3],弗莱彻[12],戈德法布[20],和香诺[37]BFGS被认为是通用方法中最有效的一种。
BFGS给出的公式为
(9)
在哪里
作为一个起点,H0是否可以设为任意对称正定矩阵,例如单位矩阵我. 为了避免黑森曲线的倒转H,您可以派生一个更新方法,以避免直接反转H通过使用一个公式来近似逆HessianH1在每一个更新。一个众所周知的程序是戴维顿的DFP公式[7]弗莱彻和鲍威尔[14].这使用了与BFGS方法相同的公式(方程9),除了QK被替换为sK.
梯度信息要么通过解析计算的梯度提供,要么通过使用数值微分法通过有限差分得到偏导数。这涉及到扰乱每个设计变量,x,然后计算目标函数中的变化率。
在每个主要的迭代中,K时,在该方向执行线搜索
(10)
拟牛顿法通过上的求解路径进行了说明罗森布鲁克在教育中的作用图6-2,罗森布鲁克函数的BFGS方法.该方法能够跟踪谷的形状,仅使用有限差分梯度进行140次函数计算后收敛到最小。
图6-2,罗森布鲁克函数的BFGS方法
有关此图的更完整描述,包括生成迭代点的脚本,请参见香蕉函数最小化.
线路搜索
线路搜索 是一种搜索方法,用于更大的优化算法的一部分。在主算法的每一步中,直线搜索法沿着包含当前点的直线进行搜索,xK,平行于搜索方向 ,这是由主算法确定的向量。也就是说,该方法查找下一个迭代xK+1的形式
(11)
在哪里xK
表示当前迭代,DK搜索方向是,和α*是标量步长参数。
直线搜索法试图沿直线减少目标函数xK +α*DK 通过反复最小化多项式插值模型的目标函数。线路搜索程序有两个主要步骤:
这个夹叉射击 相位确定直线上点的范围
搜索。这个支架 对应于指定的值范围的一个区间α.
这个切片 Step将括号分成子区间,在子区间上用多项式插值逼近目标函数的最小值。
得到的步长α满足Wolfe条件:
(12)
(13)
在哪里C1.和C2.为0 <的常量C1.<C2.< 1.
第一个条件(方程式12)要求αK充分降低了目标函数。第二个条件(等式13),确保步长不过小。满足两个条件的点(方程式12和等式13)被称为可接受的点 .
线搜索方法是第2-6节所述算法的实现[13].另请参阅[31]有关行搜索的详细信息。
黑森更新
许多优化函数通过在每次迭代时更新Hessian矩阵来确定搜索方向,使用BFGS方法(方程9). 功能fminunc还提供了使用中给出的DFP方法的选项拟牛顿方法(设置HessUpdate来“dfp”在里面选项选择DFP方法)。黑森人,H,总是保持正定,以便搜索的方向,D,总是朝着下降的方向。这意味着对于一些任意小的步骤α在方向上D时,目标函数的幅度减小。你获得了肯定的H通过确保H初始化为正数,然后呢
(从等式14)总是积极的。术语
是直线搜索步长参数的乘积吗αK并结合搜索方向D根据过去和现在的梯度评估,
(14)
你总是达到这样的条件
通过执行足够精确的直线搜索,是积极的。这是因为搜索方向,D,是一个下降方向,因此αK负梯度呢–∇F(xK)TD 总是积极的。因此,可能的负项–∇F(xK+1)TD 通过增加直线搜索的准确性,可以使其大小满足要求。