一般情况下，最小二乘问题求的是使某一函数局部最小的向量 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) 和各种类型的约束：

除了 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 上进行最小化（或近似最小化）来计算的。以下是信赖域子问题，

如果 f(x + s) < f(x)，当前点更新为 x + s；否则，当前点保持不变，信赖域 N 缩小，算法再次计算试探步。

在定义特定信赖域方法以最小化 f(x) 的过程中，关键问题是如何选择和计算逼近 q（在当前点 x 上定义）、如何选择和修改信赖域 N，以及如何准确求解信赖域子问题。本节重点讨论无约束问题。后面的章节讨论由于变量约束的存在而带来的额外复杂性。

在标准信赖域方法 ([48]) 中，二次逼近 q 由 F 在 x 处的泰勒逼近的前两项定义；邻域 N 通常是球形或椭圆形。以数学语言表述，信赖域子问题通常写作

其中，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 是近似牛顿方向，即下式的解

或是负曲率的方向，