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
    1000 days starting from January 2010 · 90 to 1500 assets
    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 The paper reports no trading or execution result.

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.

Cited by 2 papers in the archive (2 by independent authors)

Code

https://github.com/jpmorganchase/dcmppln — the authors' own repository

Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.