最小二乘(模型拟合)算法 |
您所在的位置:网站首页 › 最小二乘法求线性回归方程计算器在线 › 最小二乘(模型拟合)算法 |
最小二乘(模型拟合)算法最小二乘定义 一般情况下,最小二乘问题求的是使某一函数局部最小的向量 x,函数具有平方和的形式,求解可能需要满足一定的约束: minx‖F(x)‖22=minx∑iFi2(x) 满足 A·x ≤ b, Aeq·x = beq, lb ≤ x ≤ ub, c(x) ≤ 0, ceq(x) = 0。 Optimization Toolbox™ 提供几种求解器,适用于各种类型的 F(x) 和各种类型的约束: 求解器F(x)约束mldivideC·x – d无lsqnonnegC·x – dx ≥ 0lsqlinC·x – d边界、线性lsqnonlin一般形式的 F(x)一般的线性和非线性lsqcurvefitF(x, xdata) – ydata一般的线性和非线性除了 mldivide 中使用的算法外,Optimization Toolbox 求解器中还有六种最小二乘算法: lsqlin 内点 lsqlin 活动集 信赖域反射(非线性或线性最小二乘、边界约束) 莱文贝格-马夸特(非线性最小二乘,边界约束) fmincon 'interior-point' 算法,针对非线性最小二乘求解器 lsqnonlin 和 lsqcurvefit(一般的线性和非线性约束)进行了修正。 lsqnonneg 使用的算法 除 lsqlin 活动集外,所有算法均为大规模算法;请参阅大规模算法与中等规模算法。有关非线性最小二乘方法的一般概况,请参阅 Dennis 的论著 [8]。莱文贝格-马夸特方法的具体细节可见于 Moré 的论著 [28]。 线性最小二乘:内点或活动集lsqlin 'interior-point' 算法使用 interior-point-convex quadprog 算法,lsqlin 'active-set' 算法使用活动集 quadprog 算法。quadprog 问题定义用于最小化以下二次函数 minx12xTHx+cTx 且需要满足线性约束和边界约束。lsqlin 函数在满足线性约束和边界约束的前提下最小化向量 Cx – d 的 2-范数平方。换句话说,lsqlin 最小化下式 ‖Cx−d‖22=(Cx−d)T(Cx−d)=(xTCT−dT)(Cx−d)=(xTCTCx)−(xTCTd−dTCx)+dTd=12xT(2CTC)x+(−2CTd)Tx+dTd. 将上式的 2CTC 替换为 H 矩阵,并将 (–2CTd) 替换为 c 向量,即符合 quadprog 框架。(加法项 dTd 对最小值的位置没有影响。)在重新表示 lsqlin 问题后,quadprog 会计算解。 注意 quadprog 'interior-point-convex' 算法有两种代码路径。当黑塞矩阵 H 是由双精度值组成的普通(满)矩阵时,它采用一种代码路径;当 H 是稀疏矩阵时,它采用另一种代码路径。有关稀疏数据类型的详细信息,请参阅稀疏矩阵。通常,对于非零项相对较少的大型问题,该算法在 H 指定为 sparse 时执行更快。同样,对于较小或相对稠密的问题,该算法在 H 指定为 full 时执行更快。 信赖域反射最小二乘信赖域反射最小二乘算法Optimization Toolbox 求解器中使用的许多方法都基于信赖域,这是一个简单而功能强大的优化概念。 要理解信赖域优化方法,请考虑无约束最小化问题,最小化 f(x),该函数接受向量参数并返回标量。假设您现在位于 n 维空间中的点 x 处,并且您要寻求改进,即移至函数值较低的点。基本思路是用较简单的函数 q 来逼近 f,该函数需能充分反映函数 f 在点 x 的邻域 N 中的行为。此邻域是信赖域。试探步 s 是通过在 N 上进行最小化(或近似最小化)来计算的。以下是信赖域子问题, mins{q(s), s∈N}.(1)如果 f(x + s) < f(x),当前点更新为 x + s;否则,当前点保持不变,信赖域 N 缩小,算法再次计算试探步。 在定义特定信赖域方法以最小化 f(x) 的过程中,关键问题是如何选择和计算逼近 q(在当前点 x 上定义)、如何选择和修改信赖域 N,以及如何准确求解信赖域子问题。本节重点讨论无约束问题。后面的章节讨论由于变量约束的存在而带来的额外复杂性。 在标准信赖域方法 ([48]) 中,二次逼近 q 由 F 在 x 处的泰勒逼近的前两项定义;邻域 N 通常是球形或椭圆形。以数学语言表述,信赖域子问题通常写作 min{12sTHs+sTg such that ‖Ds‖≤Δ},(2)其中,g 是 f 在当前点 x 处的梯度,H 是黑塞矩阵(二阶导数的对称矩阵),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 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |