Paper: arXiv 2409.10301
Authors: Atithi Acharya, Romina Yalovetzky, Pierre Minssen, Shouvanik Chakrabarti, Ruslan Shaydulin, Rudy Raymond, Yue Sun, Dylan Herman, Ruben S. Andrist, Grant Salton, Martin J. A. Schuetz, Helmut G. Katzgraber, Marco Pistoia
Abstract
Industrially relevant constrained optimization problems, such as portfolio optimization and portfolio rebalancing, are often intractable or difficult to solve exactly. In this work, we propose and benchmark a decomposition pipeline targeting portfolio optimization and rebalancing problems with constraints. The pipeline decomposes the optimization problem into constrained subproblems, which are then solved separately and aggregated to give a final result. Our pipeline includes three main components: preprocessing of correlation matrices based on random matrix theory, modified spectral clustering based on Newman’s algorithm, and risk rebalancing. Our empirical results show that our pipeline consistently decomposes real-world portfolio optimization problems into subproblems with a size reduction of approximately 80%. Since subproblems are then solved independently, our pipeline drastically reduces the total computation time for state-of-the-art solvers. Moreover, by decomposing large problems into several smaller subproblems, the pipeline enables the use of near-term quantum devices as solvers, providing a path toward practical utility of quantum computers in portfolio optimization.
Complexity vs Empirical Score
- Math Complexity: 7.5/10
- Empirical Rigor: 6.0/10
- Quadrant: Holy Grail — high math complexity, high empirical rigor
Why this score: The paper presents advanced mathematical concepts including random matrix theory, spectral clustering (Newman’s algorithm), and MIQCQP formulations, yet it is grounded in industrial data, benchmarking against commercial solvers (CPLEX/Gurobi), and provides empirical results like an 80% size reduction and 3x speedup.
Research Flowchart
flowchart TD
A["Research Goal: Decompose Large-Scale<br>Portfolio Optimization for<br>Quantum/Classical Solvers"] --> B{"Key Methodology: Decomposition Pipeline"}
B --> C["1. Preprocessing<br>Random Matrix Theory"]
B --> D["2. Clustering<br>Modified Spectral / Newman's"]
B --> E["3. Risk Rebalancing"]
C & D & E --> F["Computational Process:<br>Solve Subproblems Independently"]
F --> G["Key Outcomes"]
G --> G1["80% Size Reduction<br>in subproblems"]
G --> G2["Drastic Reduction<br>in computation time"]
G --> G3["Enables Near-Term<br>Quantum Device Solvers"]
Evidence Card
What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card
Proposes
The paper proposes a decomposition pipeline that splits large portfolio optimization problems into constrained subproblems, solves them independently, and aggregates the solutions.
Source sentence
Our pipeline includes three main components: preprocessing of correlation matrices based on random matrix theory, modified spectral clustering based on Newman's algorithm, and risk rebalancing.
Assumes 5
- Daily returns are used without loss of generality. data
Source sentence
For brevity, we will assume daily returns without loss of generality, but it is straightforward to use other types of returns.
- Decision variables are integer (binary or integer) variables. model
Source sentence
Given a universe of n ∈Z assets to choose from, the objective is to maximize the return while minimizing the exposure to risk.
- Risk aversion coefficient q is a positive real number. model
Source sentence
their trade-off is governed by the risk aversion coefficient q ∈R+.
- Correlation matrix can be decomposed into random and signal components using a threshold λ+. statistical
Source sentence
the eigendecomposition of C whose eigenvalues are at most λ+ captures the random components associated with eigenvalues less than or equal to λ+, and Csignal represents the structured components reflecting eigenvalues greater than λ+.
Show 1 more
- Subproblem size threshold ϕ is set to limit community size. execution
Source sentence
denoted by ϕ) after executing Algorithm 1 or Algorithm 3, respectively.
Data
- Russell 3000 index daily returns market-prices public
Source sentence
The dataset utilized in this work is based on the Russell 3000 index, with daily returns collected over a period of 1000 days starting from January 2010. The instances range in size from 90 to 1500 assets.
Costs
Not applicable
Finds 3
- The decomposition pipeline reduces problem size by approximately 80%. performance
Source sentence
Our empirical results show that our pipeline consistently decomposes real‑world portfolio optimization problems into subproblems with a size reduction of approximately 80%.
- Time‑to‑solution is reduced by at least 3× for the largest problems (1500 variables) when using the pipeline with a branch‑and‑bound solver. performance
Source sentence
the time‑to‑solution is significantly reduced (by at least 3× for the largest problems considered in our numerical experiments, with 1500 variables) as compared to directly solving the problem with the same solver.
- Decomposed subproblems become suitable targets for quantum optimization techniques. other
Source sentence
even the decomposed subproblems become difficult to solve with classical techniques, but are
Checked by others
No other paper in the archive has been found to support or contradict these findings (compared with 13 related papers). Coverage is partial, so this is neither replication nor refutation.
2 papers in the archive
Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.