在关于 Galahad[1] 的技术报告中，作者指出，在一般非线性规划问题的背景下，
在我们看来，从长远来看，SQP [顺序二次规划] 方法[比增广拉格朗日方法] 会更成功，这一点毫无疑问......
这种信念的基础是什么？即，是否有任何理论结果表明 SQP 方法应该比增强拉格朗日方法更快/更可靠？
[1] Galahad，一个用于大规模非线性优化的线程安全 Fortran 90 包库，由 Gould、Orban 和 Toint 编写
为什么 SQP 在非线性规划方面优于增强拉格朗日？
计算科学
非线性规划
2021-12-24 08:29:36
2个回答
SQP 方法要求目标是两次可微的（参见https://en.m.wikipedia.org/wiki/Sequential_quadratic_programming），而增强拉格朗日即使在目标不可微的情况下也能工作（因此它们最近在图像处理社区 cf ftp 中复苏： //arachne.math.ucla.edu/pub/camreport/cam09-05.pdf）
我不了解 galahad 软件，但如果应该解决可微优化问题，使用允许微分目标函数的方法可能会做得更好。
就外部迭代而言，SQP 应该获胜，因为它包含二阶导数信息，而增强拉格朗日方法（如 ADMM）则不包含。
但是，要记住的一件事是，这些方法的每次迭代都涉及求解线性系统，因此要进行公平比较，您必须考虑这些系统求解的难易程度。
对于增强拉格朗日（交替）方法，每次迭代您都在解决类似的问题，
在哪里是直接来自已知且通常更容易处理或前置条件的目标函数的前向算子，并且是惩罚参数。（例如，您的问题是受到一些正则化和约束）。
对于 SQP 方法，您正在解决类似 其中是 Hessian（或其近似值），通常仅在其对向量的作用方面隐含可用，而是梯度。Hessian 不仅包含，还包含来自线性化约束和正则化的其他矩阵和矩阵逆矩阵的组合。
预处理 Hessians 是一项非常棘手的工作，与预处理前向问题相比，它的研究要少得多。一种标准的方法是用 L-BFGS 来近似 Hessian 逆，但是当 Hessian 逆是高秩时，这种方法的效果有限。另一种流行的方法是将 Hessian 近似为低秩矩阵加上易于反转的矩阵的总和，但这对于难题的有效性也有限。其他流行的 Hessian 估计技术基于稀疏近似，但连续统问题通常具有稀疏近似较差的 Hessian。