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

This repository contains the code of the decomposition pipeline algorithm. 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.

The main blocks of this algorithm as located in the folder "dcmppln". We test some of these components in the folder "tests". We include a simple notebook that shows how to run this decomposition pipeline in the folder "examples". Note that we include some data to perform these executions in tests/data.

SPDX-License-Identifier: Apache-2.0 @ Copyright 2024: Amazon Web Services, Inc. - Contributions from JPMC