本页对应的英文页面已更新,但尚未翻译。 若要查看最新内容,请点击此处访问英文页面。

选择算法

fmincon 算法

fmincon 有五个算法选项:

  • 'interior-point'(默认值)

  • 'trust-region-reflective'

  • 'sqp'

  • 'sqp-legacy'

  • 'active-set'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议
  • 首先使用 'interior-point' 算法。

    有关最小化失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

  • 要再次运行优化以提高求解中小规模问题的速度,接下来请尝试 'sqp',最后尝试 'active-set'

  • 适用时,使用 'trust-region-reflective'。您的问题必须具备:目标函数(其中包括梯度)、仅边界或仅线性等式约束(但不能同时包括两者)。

请参阅使用内点算法时的潜在不准确性

建议算法的理论依据

  • 'interior-point' 处理大型稀疏问题以及小型稠密问题。该算法在所有迭代中都满足边界,并且可以从 NaNInf 结果中恢复。它是一种大规模算法;请参阅大规模算法与中等规模算法。该算法可以对大规模问题使用特殊方法。有关详细信息,请参阅 fmincon options 中的内点算法

  • 'sqp' 在所有迭代中都满足边界。该算法可以从 NaNInf 结果中恢复。它不是一种大规模算法;请参阅大规模算法与中等规模算法

  • 'sqp-legacy' 类似于 'sqp',但通常速度更慢且占用的内存更多。

  • 'active-set' 可以采用大步长,从而提高速度。该算法对一些具有非平滑约束的问题很有效。它不是一种大规模算法;请参阅大规模算法与中等规模算法

  • 'trust-region-reflective' 要求您提供梯度,并且只允许边界或线性等式约束,但不能同时使用两者。在这些限制下,该算法可以高效处理大型稀疏问题和小型稠密问题。它是一种大规模算法;请参阅大规模算法与中等规模算法。该算法可以使用特殊方法来节省内存使用量,例如 Hessian 矩阵乘法函数。有关详细信息,请参阅 fmincon options 中的信赖域反射算法

有关算法的说明,请参阅约束非线性优化算法

fsolve 算法

fsolve 有三种算法:

  • 'trust-region-dogleg'(默认值)

  • 'trust-region'

  • 'levenberg-marquardt'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议
  • 首先使用 'trust-region-dogleg' 算法。

    有关 fsolve 失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

  • 要重新求解方程(如果您有 Jacobian 矩阵乘法函数)或要调整内部算法(请参阅 fsolve options 中的信赖域算法),请尝试 'trust-region'

  • 尝试对所有算法进行计时,包括 'levenberg-marquardt',以找到最适合您的问题的算法。

建议算法的理论依据

  • 'trust-region-dogleg' 是唯一专门设计为用于求解非线性方程的算法。其他算法尝试最小化函数的平方和。

  • 'trust-region' 算法对稀疏问题有效。对于大规模问题,它可以使用特殊方法,如 Jacobian 矩阵乘法函数。

有关算法的说明,请参阅方程求解算法

fminunc 算法

fminunc 有两种算法:

  • 'quasi-newton'(默认值)

  • 'trust-region'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议
  • 如果您的目标函数包括梯度,请使用 'Algorithm' = 'trust-region',并将 SpecifyObjectiveGradient 选项设置为 true

  • 否则,请使用 'Algorithm' = 'quasi-newton'

有关最小化失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

有关算法的说明,请参阅无约束非线性优化算法

最小二乘算法

lsqlin

lsqlin 有三种算法:

  • 'interior-point',默认值

  • 'trust-region-reflective'

  • 'active-set'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议
  • 首先尝试 'interior-point'

    提示

    当您的输入矩阵 C 包含大量非零项时,为了获得更好的性能,请将 C 指定为普通的双精度矩阵。同样,为了在 C 的非零项相对较少时获得更好的性能,请将 C 指定为稀疏矩阵。有关数据类型的详细信息,请参阅稀疏矩阵。您也可以使用 'LinearSolver' 选项设置内部线性代数类型。

  • 如果您没有约束或只有边界约束,并且需要更高的准确度、更快的速度或要使用 Jacobian Multiply Function with Linear Least Squares,请尝试 'trust-region-reflective'

  • 如果您有大量的线性约束而没有大量的变量,请尝试 'active-set'

有关最小化失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

请参阅使用内点算法时的潜在不准确性

有关算法的说明,请参阅最小二乘(模型拟合)算法

lsqcurvefit 和 lsqnonlin

lsqcurvefitlsqnonlin 有两种算法:

  • 'trust-region-reflective'(默认值)

  • 'levenberg-marquardt'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议
  • 通常,先尝试 'trust-region-reflective'。如果您的问题有边界,您必须使用 'trust-region-reflective'

  • 如果您的问题没有边界并且欠定(方程数少于维数),请使用 'levenberg-marquardt'

有关最小化失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

有关算法的说明,请参阅最小二乘(模型拟合)算法

线性规划算法

linprog 有三种算法:

  • 'dual-simplex',默认值

  • 'interior-point-legacy'

  • 'interior-point'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议

首先使用 'dual-simplex' 算法或 'interior-point' 算法。

有关最小化失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

请参阅使用内点算法时的潜在不准确性

建议算法的理论依据

  • 通常,'dual-simplex''interior-point' 算法速度快且占用的内存最少。

  • 'interior-point-legacy' 算法类似于 'interior-point',但 'interior-point-legacy' 可能速度较慢、稳健性较差或占用内存较多。

有关算法的说明,请参阅线性规划算法

二次规划算法

quadprog 有三种算法:

  • 'interior-point-convex'(默认值)

  • 'trust-region-reflective'

  • 'active-set'

在命令行中使用 optimoptions 设置 Algorithm 选项。

建议
  • 如果您遇到凸问题,或不知道您的问题是否为凸问题,请使用 'interior-point-convex'

  • 提示

    当您的 Hessian 矩阵 H 包含大量非零项时,为了获得更好的性能,请将 H 指定为普通的双精度矩阵。同样,为了在 H 的非零项相对较少时获得更好的性能,请将 H 指定为稀疏矩阵。有关数据类型的详细信息,请参阅稀疏矩阵。您也可以使用 'LinearSolver' 选项设置内部线性代数类型。

  • 如果您的非凸问题只有边界或只有线性等式约束,请使用 'trust-region-reflective'

  • 如果您有具有大量线性约束而没有大量变量的半正定问题,请尝试 'active-set'

有关最小化失败时的帮助,请参阅当求解器失败时When the Solver Might Have Succeeded

请参阅使用内点算法时的潜在不准确性

有关算法的说明,请参阅二次规划算法

大规模算法与中等规模算法

如果优化算法使用的线性代数不需要存储满矩阵,也不需要对满矩阵进行运算,则该优化算法是大规模算法。这可以在内部实现,方法是存储稀疏矩阵以及尽可能使用稀疏线性代数进行计算。此外,内部算法要么保持稀疏性(如稀疏 Cholesky 分解),要么不生成矩阵(如共轭梯度法)。

相反,中等规模方法是在内部创建满矩阵并使用稠密线性代数。如果问题足够大,满矩阵会占用大量内存,稠密线性代数可能需要很长时间来执行。

不要让“大规模”一词误导您;您可以对小型问题使用大规模算法。此外,使用大规模算法不需要指定任何稀疏矩阵。选择中等规模的算法可使用额外的功能(例如其他约束类型),或者可能获得更好的性能。

使用内点算法时的潜在不准确性

fminconquadproglsqlinlinprog 中的内点算法有许多好的特征,例如内存使用量少,能够快速求解大型问题。然而,其解的准确性可能比其他算法得出的解稍差一些。这种潜在的误差是因为(内部计算的)障碍函数会阻止迭代靠近不等式约束边界。

对于大多数实际目的来说,这种不准确性通常并不明显。

要减少不准确性,请尝试:

  • 使用较小的 StepToleranceOptimalityTolerance 以及可能的 ConstraintTolerance 容差重新运行求解器(但保持容差合理。)请参阅容差和停止条件

  • 从内点解开始,运行不同算法。这可能会失败,因为有些算法会使用过多的内存或时间,所有 linprog 和一些 quadprog 算法不接受初始点。

例如,当下界为 0 时,尝试最小化函数 x。使用 fmincon 的默认 interior-point 算法:

options = optimoptions(@fmincon,'Algorithm','interior-point','Display','off');
x = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x =

   2.0000e-08

使用 fmincon sqp 算法:

options.Algorithm = 'sqp';
x2 = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x2 =

   0

同样,使用 linprog interior-point-legacy 算法求解同一问题:

opts = optimoptions(@linprog,'Display','off','Algorithm','interior-point-legacy');
x = linprog(1,[],[],[],[],0,[],1,opts)
x =

   2.0833e-13

使用 linprog dual-simplex 算法:

opts.Algorithm = 'dual-simplex';
x2 = linprog(1,[],[],[],[],0,[],1,opts)
x2 =

     0

在这些情况下,内点算法准确性稍差,但答案非常接近正确答案。