matlab - 谁知道MATLAB中的函数quadprog的计算复杂度？

Question

QP 问题是凸的。对于 Wiki，问题可以在多项式时间内解决。但具体的顺序是什么？

Answer 1

这是一个有趣的问题，（在我看来）没有明确的答案。我将假设您的问题是凸的，并且您对运行时复杂性（而不是迭代复杂性）感兴趣。

• 您可能知道，QuadProg它不是一种算法，而是解决二次问题的通用名称。它在下面使用一组算法。内点（默认）、信任区域和活动集。来源。
• 根据您的选择，这些算法中的每一个都有自己的复杂性分析。对于 Trust-Region 和 Active-Set 方法，复杂性分析非常困难。事实上，Active-Set 方法一开始就不是多项式的。存在反例，其中 Active-Set 方法需要指数“时间”才能收敛（对于线性规划的单纯形法也是如此）。来源。
• 现在，假设您选择内部点方法，答案仍然不简单，因为这些方法有多种形式。当 Karmarkar 首次提出这种方法时，它是已知的第一个求解线性规划的多项式算法，其复杂度为 O(n^3.5)。来源。这些界限后来得到了很大改善。但是，这适用于线性程序。
• 最后，为了回答你的问题，Ye 和 Tse 在 1989 年证明了我们可以有一个复杂度为 O(n^3) 的内点法。然而，MATLAB 是否使用这种内点法的确切风格有点难以确定，但 O(n^3) 将是我的最佳猜测。

当然，我的回答是相当理论的；如果您想凭经验对其进行测试，您可以通过逐渐增加变量的数量并绘制获得估计所需的 CPU 时间来做到这一点。