誰知道MATLAB中函數quadprog的計算複雜度？

Question

QP問題是凸的。對於Wiki，問題可以在多項式時間內解決。 但是訂單到底是什麼？

Answer 1

這是一個有趣的問題（在我看來）沒有明確的答案。我將假設你的問題是凸的，你對運行時複雜性感興趣（而不是迭代複雜度）。

• 如您所知，QuadProg不是一種算法，而是解決二次問題的通用名稱。它使用下面的一組算法。內部點（默認），信任區域和活動集。 Source。
• 根據您的選擇，這些算法中的每一個都會有自己的複雜性分析。對於Trust-Region和Active-Set方法，複雜性分析非常困難。實際上，Active-Set方法不是以多項式開始的。在Active-Set方法採用指數「時間」收斂的地方存在反例（對於線性程序的單純形法也是如此）。 Source。
• 現在，假設您選擇了內點法，答案仍然不簡單，因爲這些方法有各種各樣的風味。當Karmarkar首次提出這種方法時，它是第一個已知的求解線性程序的多項式算法，它的複雜度爲O（n^3.5）。 Source。這些界限在很長時間後得到了改善。但是，這是針對線性程序的。
• 最後，回答你的問題，Ye and Tse proved in 1989我們可以有一個複雜度爲O（n^3）的內點法。然而，MATLAB是否使用內點法的這種確切的味道是有點棘手知道，但O（n^3）將是我最好的猜測。

當然，我的回答是相當理論性的;如果您想憑經驗對其進行測試，您可以逐步增加變量數量並繪製獲得估計所需的CPU時間。