# A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

arXiv: https://arxiv.org/abs/2110.12547 · HTML: https://mlsanity.com/paper/2110.12547/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2021.

## Built on by (most cited first, 5 of 5)

- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, we propose a novel decomposition method for general (sparse) Q, which leverages the efficient algorithm for the path case. Our computational experiments demonstrate the effectiveness of the proposed method compared to state-of-the-art mixed-integer optimization solvers.