Paper: arXiv 2409.10301

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"]