Markowitz 投資組合優化的時間複雜度

Markowitz 均值變異數投資組合優化 (MVO) 的時間複雜度是多少？

我無法在網際網路和學術論文中找到任何明確的解釋。

這些是我的問題：

1. 標準 MVO 算法的時間和空間複雜度是多少？請解釋原因。
2. 是否有可以更快解決的特殊情況，例如最小變異數投資組合？
3. 在典型的電腦上使用各種軟體包優化投資組合（例如 1000 個資產）的典型執行時間是多少秒？
4. 是否有更快的投資組合算法可用？

對學術論文或其他來源的參考也將不勝感激。

謝謝！

MVO 是一個 QP（二次規劃問題）

假設一個非病態的情況，你可以用 O(n^{3.5} L) 附近的複雜度的內點（沒有優化）進行估計

參看。https://en.wikipedia.org/wiki/Quadratic_programming cf。https://en.wikipedia.org/wiki/Interior-point_method 參見。https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm

在現實生活中，由於一組約束是稀疏的，我們可以有 O(n L) 和 O(n^{3} L) 之間的複雜度

關於最小變異數投資組合，我們只需要找出一個線性系統的解，也就是 O(n^{3} L)

根據矩陣、軟體、參數、機器和約束結構，您可以期望在幾百微秒到幾秒之間解決這類問題。

根據您的結構，您可以為自己編寫一個性能優於通用求解器的專用求解器。

關於問題 4：最近出現了一種新的投資組合方法，它與 Markowitz 範式非常不同。該論文聲稱它具有時間複雜性 $ O(N^2) $ 和 $ N $ 是投資組合中資產的數量，並且保證收斂到最優解，並且對估計誤差非常穩健。據稱，對於 1000 種資產的投資組合，時間使用僅為幾毫秒。該算法看起來與常見的投資組合算法非常不同，因此當然有必要持懷疑態度，但也有可用的Python 包，因此應該很容易測試。

引用自：https://quant.stackexchange.com/questions/68245