本页采用了机器翻译。点击此处可查看最新英文版本。

选择算法

fmincon 算法

fmincon 有五个算法选项：

  • 'interior-point'（默认值）

  • 'trust-region-reflective'

  • 'sqp'

  • 'sqp-legacy'

  • 'active-set'

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

建议

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

    有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

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

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

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

建议算法的理论依据

  • 'interior-point' 处理大型稀疏问题以及小型稠密问题。请参阅稀疏性在优化算法中的应用。该算法在所有迭代中都满足边界，并且可以从 NaN 或 Inf 结果中恢复。该算法可以对大规模问题使用特殊方法。有关详细信息，请参阅 fmincon options 中的内点算法。

  • 'sqp' 在所有迭代中都满足边界。该算法可以从 NaN 或 Inf 结果中恢复。该算法无法处理稀疏数据；请参阅 稀疏性在优化算法中的应用。

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

  • 'active-set' 可以采用大步长，从而提高速度。该算法对一些具有非平滑约束的问题很有效。该算法无法处理稀疏数据；请参阅 稀疏性在优化算法中的应用。

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

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

fsolve 算法

fsolve 有三种算法：

  • 'trust-region-dogleg'（默认值）

  • 'trust-region'

  • 'levenberg-marquardt'

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

建议

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

    有关 fsolve 失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

  • 要重新求解方程（如果您有雅可比矩阵乘法函数）或要调整内部算法（请参阅 fsolve options 中的信赖域算法），请尝试 'trust-region'。

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

建议算法的理论依据

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

  • 'trust-region' 算法可以使用特殊技术，例如雅可比乘法函数来处理大型问题。

  • 所有算法均可使用稀疏数据；请参阅稀疏性在优化算法中的应用。

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

fminunc 算法

fminunc 有两种算法：

  • 'quasi-newton'（默认值）

  • 'trust-region'

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

建议

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

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

有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

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

最小二乘算法

lsqlin

lsqlin 有三种算法：

  • 'interior-point'，默认值

  • 'trust-region-reflective'

  • 'active-set'

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

建议

  • 首先尝试 'interior-point'。

    提示

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

  • 如果您没有约束或只有边界约束，并且需要更高的准确度、更快的速度或要使用 雅可比乘法函数与线性最小二乘法，请尝试 'trust-region-reflective'。

  • 如果您有大量的线性约束而没有大量的变量，请尝试 'active-set'。这是唯一一个无法使用稀疏数据的算法；参阅稀疏性在优化算法中的应用。

有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

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

有关算法的说明，请参阅最小二乘（模型拟合）算法。

lsqcurvefit 和 lsqnonlin

lsqcurvefit 和 lsqnonlin 有三种算法：

  • 'trust-region-reflective'（无约束或有边界约束问题的默认值）

  • 'levenberg-marquardt'

  • 'interior-point'（线性或非线性约束问题的默认值）

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

建议

  • 对于只具有边界约束的问题，请先尝试 'trust-region-reflective' 或 'levenberg-marquardt'。

  • 如果您的边界约束问题是欠定的（方程数少于维数），请先尝试 'levenberg-marquardt'。

  • 如果您的问题具有线性或非线性约束，请使用 'interior-point'。

所有算法均可使用稀疏数据；请参阅稀疏性在优化算法中的应用。有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

有关算法的说明，请参阅最小二乘（模型拟合）算法。

线性规划算法

linprog 有四种算法：

  • 'dual-simplex-highs'，默认值

  • 'interior-point'

  • 'interior-point-legacy'

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

建议

首先使用 'dual-simplex-highs' 算法或 'interior-point' 算法。很难知道哪种算法对求解问题更高效。

有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

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

建议算法的理论依据

  • 通常，'dual-simplex-highs' 和 'interior-point' 算法运行速度快，且内存占用相对较少。

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

  • 所有算法均可使用稀疏数据；请参阅稀疏性在优化算法中的应用。

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

混合整数线性规划算法

intlinprog 有两种算法：

  • 'highs'，默认值

  • 'legacy'

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

建议

首先使用 'highs' 算法。

有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

建议算法的理论依据

  • 通常，'highs' 算法比 'legacy' 算法速度更快或效果更好。

  • 'highs' 算法的调节选项要少得多。因此，在求解问题时，可用的选择项较少。

  • 在以后的版本中将会删除 'legacy' 算法。

有关算法的说明，请参阅混合整数线性规划 (MILP) 算法。

二次规划算法

quadprog 有三种算法：

  • 'interior-point-convex'（默认值）

  • 'trust-region-reflective'

  • 'active-set'

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

建议

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

  • 提示

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

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

  • 如果您有具有大量线性约束而没有大量变量的半正定问题，请尝试 'active-set'。该算法无法处理稀疏数据；请参阅稀疏性在优化算法中的应用。

有关最小化失败时的帮助，请参阅当求解器失败时或当求解器可能成功求解时。

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

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

稀疏性在优化算法中的应用

某些优化算法支持稀疏数据，无需存储或对完整矩阵进行运算。这些算法在计算过程中尽可能使用稀疏线性代数。此外，这些算法要么保留稀疏性，例如稀疏乔利斯基分解，要么不生成矩阵，例如共轭梯度法。当您有大型线性约束矩阵 A 或 Aeq，或者问题变量数量较多时，这些算法是更佳的选择。

相比之下，某些算法会在内部创建完整的矩阵并使用密集线性代数。如果问题足够大，满矩阵会占用大量内存，稠密线性代数可能需要很长时间来执行。对于变量不多且线性约束矩阵不大的问题，这些算法有时比使用稀疏性的算法更快。

此表显示了哪些求解器和算法可以使用稀疏数据，哪些不能。

可以使用稀疏数据无法使用稀疏数据

coneprog

fgoalattain

fmincon 'interior-point', 'trust-region-reflective'

fmincon 'active-set', 'sqp', 'sqp-legacy'

fminunc 'trust-region'

fminimax

fsolve

fminunc 'quasi-newton'

intlinprog

fseminf

linprog

lsqlin 'active-set'

lsqcurvefit

quadprog 'active-set'

lsqlin 'interior-point', 'trust-region-reflective'

 

lsqnonlin

 

quadprog 'interior-point-convex', 'trust-region-reflective'

 

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

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

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

要减少不准确性，请尝试：

  • 使用较小的 StepTolerance、OptimalityTolerance 以及可能的 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

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

另请参阅

主题