1
$\begingroup$

What is the time-complexity of Markowitz mean-variance portfolio optimization (MVO)?

I am unable to find any clear explanation of this on the internet and in academic papers.

These are my questions:

  1. What is the time and space-complexity of a standard MVO algorithm? Please explain why.

  2. Are there special cases that can be solved faster, such as the minimum-variance portfolio?

  3. What is the typical runtime in seconds using various software packages to optimize a portfolio with e.g. 1000 assets on a typical computer?

  4. Are there any faster portfolio algorithms available?

References to academic papers or other sources would also be appreciated.

Thanks!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Performing MVO with 1000 free variables is certain to yield a portfolio that is useless in practice due to uncertainty in expected returns. You are better off with a random number generator that runs in $\mathcal{O}\left(n\right)$. $\endgroup$
    – shabbychef
    Oct 6, 2021 at 19:42
  • $\begingroup$ @shabbychef Please elaborate. Is it useless because the MVO procedure will not work properly with that many assets in the portfolio, e.g. due to problems with numerical stability in the computation? What is the maximum number of assets that the MVO solver can handle? Do you have a source for this, such as an academic paper? $\endgroup$
    – questiondude
    Oct 7, 2021 at 7:08
  • $\begingroup$ My statement has nothing to do with numerical stability, but rather parameter uncertainty. This paper gives bounds on expected Sharpe in terms of sample size, number of assets and true effect size. I am not sure there is an equivalent result for MVO per se, but I urge you to perform Monte Carlo simulations with your objective of interest to see how it responds to number of assets. (Or ask a question here to see if anyone has a reference.) $\endgroup$
    – shabbychef
    Oct 7, 2021 at 16:24
  • $\begingroup$ @shabbychef As I understand, you are talking about estimation errors in the mean returns and covariance matrix making you doubt that a portfolio of 1000 assets can gain anything from portfolio optimization. Perhaps that is true, but my interest with these questions is mainly in the computational time aspects of MVO. But thanks for your input! $\endgroup$
    – questiondude
    Oct 11, 2021 at 14:43

2 Answers 2

Reset to default
1
$\begingroup$

MVO is a QP (Quadratic programming question)

Assuming a non pathological case, you can have an estimate with the interior point (without optimization) of a complexity around O(n^{3.5} L)

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

In real life, with a set of constraints to be sparse, we can have a complexity between O(n L) and O(n^{3} L)

About the minimum variance portfolio, we just need to figure out the solution of a linear system, which also is O(n^{3} L)

Depending on the matrix, software, parameters, machine and structure of constraints, you can expect between few hundreds of microseconds to few seconds to solve this type of problems.

Depending on your structure, you can code yourself a specialized solver that will outperform generic ones.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi, isn’t the Karmakar algorithm a LP algo instead of a QP algo? $\endgroup$
    – Kermittfrog
    Oct 6, 2021 at 13:23
  • $\begingroup$ Thanks for the quick reply! But I was hoping for a more clear answer. Please answer in numbered points and carefully explain your claims. You don't even say what $n$ and $L$ are? Also please use math-formatting. Are these time-complexities for finding the entire Efficient Frontier, or just one point? What is the "interior point"? What are "pathological cases"? You say time-usage depends on configuration, that's obvious and I was hoping for some concrete examples. And "you can code yourself a specialized solver that will outperform generic ones." is not very helpful either :-) Please elaborate. $\endgroup$
    – questiondude
    Oct 7, 2021 at 7:23
  • $\begingroup$ Hi, it is because there is no clear answer. It depends a lot of your parameters and convergence criteria. $\endgroup$
    – Laurent
    Oct 7, 2021 at 10:22
  • $\begingroup$ Then you will have numerical inaccuracies and convergence issues depending on your problem. Only very specific cases can be answered exactly. I recommend the book from Stephen Boyd in free access (buy it too) web.stanford.edu/~boyd/cvxbook And the software OSQP (potentially CVXPY) using his algorithm (ADMM) for free. osqp.org/docs/solver/index.html cvxpy.org $\endgroup$
    – Laurent
    Oct 7, 2021 at 10:29
  • $\begingroup$ @Laurent Thanks for your input. I was hoping someone would give a more detailed answer than just "it depends", so I will leave the question unanswered for now, hoping that someone else will take a stab at answering it with more details. $\endgroup$
    – questiondude
    Oct 11, 2021 at 14:45
0
$\begingroup$

On question 4: There is a new portfolio method that came out very recently, that is very different from the Markowitz paradigm. The paper claims that it has time-complexity $O(N^2)$ with $N$ being the number of assets in the portfolio, and that it is guaranteed to converge to the optimal solution, and that it is very robust to estimation errors. The time-usage is claimed to be only a few milli-seconds for a portfolio of 1000 assets. The algorithm looks very different from the common portfolio algorithms, so some skepticism would of course be warranted, but there is also a Python package available so it should be easy to test.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.