Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

选择算法

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' 选项设置内部线性代数类型。

  • 如果您没有约束或只有边界约束，并且需要更高的准确度、更快的速度或要使用 Jacobian Multiply Function with Linear Least Squares，请尝试 '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'，默认值

  • 'interior-point-legacy'

  • 'interior-point'

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

建议

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

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

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

建议算法的理论依据

  • 通常，'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'。

  • 提示

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

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

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

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

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

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

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

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

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

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

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

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

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