信赖域反射最小二乘算法
Optimization Toolbox 求解器中使用的许多方法都基于信赖域,这是一个简单而功能强大的优化概念。
要理解信赖域优化方法,请考虑无约束最小化问题,最小化 f(x),该函数接受向量参数并返回标量。假设您现在位于 n 维空间中的点 x 处,并且您要寻求改进,即移至函数值较低的点。基本思路是用较简单的函数 q 来逼近 f,该函数需能充分反映函数 f 在点 x 的邻域 N 中的行为。此邻域是信赖域。试探步 s 是通过在 N 上进行最小化(或近似最小化)来计算的。以下是信赖域子问题,mins{q(s),s∈N}.(1)
如果 f(x+s)
在定义特定信赖域方法以最小化 f(x) 的过程中,关键问题是如何选择和计算逼近 q(在当前点 x 上定义)、如何选择和修改信赖域 N,以及如何准确求解信赖域子问题。本节重点讨论无约束问题。后面的章节讨论由于变量约束的存在而带来的额外复杂性。
在标准信赖域方法 ([48]) 中,二次逼近 q 由 F 在 x 处的泰勒逼近的前两项定义;邻域 N 通常是球形或椭圆形。以数学语言表述,信赖域子问题通常写作min{12sTHs+sTgsuchthat‖Ds‖≤Δ},(2)
其中,g 是 f 在当前点 x 处的梯度,H 是 Hessian 矩阵(二阶导数的对称矩阵),D 是对角缩放矩阵,Δ 是正标量,∥ . ∥ 是 2-范数。存在求解公式2 的好算法(请参阅[48]);此类算法通常涉及计算 H 的所有特征值,并将牛顿法应用于以下久期方程
1Δ−1‖s‖=0.
此类算法提供公式2 的精确解。但是,它们要耗费与 H 的几个分解成比例的时间。因此,对于信赖域问题,需要采取另一种方法。文献([42] 和 [50])中提出了几种基于公式2 的逼近和启发式方法建议。Optimization Toolbox 求解器采用的逼近方法是将信赖域子问题限制在二维子空间 S 内([39] 和 [42])。一旦计算出子空间 S,即使需要完整的特征值/特征向量信息,求解公式2 的工作量也不大(因为在子空间中,问题只是二维的)。现在的主要工作已转移到子空间的确定上。
二维子空间 S 是借助下述预条件共轭梯度法确定的。求解器将 S 定义为由 s1 和 s2 确定的线性空间,其中 s1 是梯度 g 的方向,s2 是近似牛顿方向,即下式的解H⋅s2=−g,(3)
或是负曲率的方向,s2T⋅H⋅s2<0.(4)
以此种方式选择 S 背后的理念是强制全局收敛(通过最陡下降方向或负曲率方向)并实现快速局部收敛(通过牛顿步,如果它存在)。
现在,我们可以很容易地给出基于信赖域的无约束最小化的大致框架:
构造二维信赖域子问题。
求解公式2 以确定试探步 s。
如果 f(x +
s) <
f(x),则 x = x +
s。
调整 Δ。
重复这四个步骤,直到收敛。信赖域维度 Δ 根据标准规则进行调整。具体来说,它会在试探步不被接受(即 f(x +
s) ≥
f(x))时减小。有关这方面的讨论,请参阅[46] 和 [49]。
Optimization Toolbox 求解器用专用函数处理 f 的一些重要特例:非线性最小二乘、二次函数和线性最小二乘。然而,其底层算法思路与一般情况相同。这些特例将在后面的章节中讨论。
如果觉得《最小二乘matlab建模 最小二乘(模型拟合)算法》对你有帮助,请点赞、收藏,并留下你的观点哦!