Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing

ArXiv ID: 2409.10301 “View on arXiv”

Authors: Unknown

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.

Keywords: decomposition pipeline, quantum computing, spectral clustering, portfolio rebalancing, random matrix theory, Multi-Asset

Complexity vs Empirical Score

• Math Complexity: 7.5/10
• Empirical Rigor: 6.0/10
• Quadrant: Holy Grail
• Why: 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.

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