Scipy中SLSQP最小化算法的时间和空间复杂度是多少？

Question

我指的是the following method：scipy.optimize.minimize(method=’SLSQP’)

我听说in this issue说“COBYLA和SLSQP所需的内存在变量数量上是二次的。这些算法不适合解决这么大的问题”：

有人知道这个算法的确切的时间和空间复杂度吗？

Answer 1

是的，看起来内存复杂度是O(n^2)，其中n是问题维度(变量的数量)。这是由于B矩阵( Hessian矩阵的近似)，因为SLSQP是一种准牛顿法。

关于时间复杂度，我还发现this related issue提出了O(n^3)的时间复杂度。但我并不信服。根据我所发现的，SciPy实现是旧FORTRAN代码的包装器，给出的参考是：

序列二次规划的软件包。(Wiss.Berichtswesen d.DFVLR，1988)。

一个计算缺陷将来自LDL decomposition，但只需要低密度脂蛋白分解的秩1更新，这可以在O(n^2)中实现。

O(n^3)可能仍然来自于用于解决二次子问题的算法。我仍然在阅读参考资料，所以我可以在这里编辑我的回复。