Computational Complexity of Markowitz Portfolio Optimization
Summary
The document asks how computational cost scales for standard mean-variance portfolio optimization, whether minimum-variance portfolios are easier, and what runtimes or faster alternatives to expect. It characterizes MVO as a quadratic program and gives a rough interior-point estimate of O(n^3.5 L), while noting that sparse constraints can lead to a broad range of lower practical costs. It describes the minimum-variance case as solving a linear system, with cubic scaling in the stated estimate.
The answer estimates runtimes from hundreds of microseconds to seconds, depending on the matrix, solver, settings, hardware, and constraint structure. A second answer mentions a newer method claimed to have quadratic scaling and millisecond runtimes for 1,000 assets, but explicitly recommends skepticism toward those claims. The discussion is a brief Q&A rather than a benchmark study: it provides no reproducible measurements or detailed assumptions, so the estimates and proposed alternative should be treated as indicative rather than definitive.
Key ideas
- Markowitz mean-variance optimization can be formulated as a quadratic program.
- A cited interior-point estimate gives complexity around O(n^3.5 L) in non-pathological cases.
- Sparse constraints can reduce practical computational cost, though the range depends on problem structure.
- The minimum-variance portfolio can be found by solving a linear system, with cubic scaling in the answer's estimate.
- Reported runtime estimates vary widely, and the faster alternative's performance claims are not independently substantiated here.
Tags
Full text
# Time-complexity of Markowitz portfolio optimization
# Time-complexity of Markowitz portfolio optimization
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:
- What is the time and space-complexity of a standard MVO algorithm? Please explain why.
- Are there special cases that can be solved faster, such as the minimum-variance portfolio?
- What is the typical runtime in seconds using various software packages to optimize a portfolio with e.g. 1000 assets on a typical computer?
- Are there any faster portfolio algorithms available?
References to academic papers or other sources would also be appreciated.
Thanks!
## Answer by Laurent (score 1)
https://quant.stackexchange.com/a/68246
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.
## Answer by questiondude (score 0)
https://quant.stackexchange.com/a/68645
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.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.