Solving Convex Quadratic Optimization with Indicators Over Structured Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918366782947328 |
|---|---|
| author | Bhathena, Aaresh Fattahi, Salar Gómez, Andrés Küçükyavuz, Simge |
| author_facet | Bhathena, Aaresh Fattahi, Salar Gómez, Andrés Küçükyavuz, Simge |
| contents | This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth of the Hessian's support graph, its volume growth, and an appropriate margin parameter. Under suitable structural conditions, the overall complexity scales linearly with the problem dimension. To demonstrate the practical impact of our approach, we introduce a novel framework for joint forecasting and outlier detection by extending exponential smoothing to time series with outliers. Computational experiments on both synthetic and real data sets show that our method significantly outperforms state-of-the-art solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_02103 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Solving Convex Quadratic Optimization with Indicators Over Structured Graphs Bhathena, Aaresh Fattahi, Salar Gómez, Andrés Küçükyavuz, Simge Optimization and Control This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth of the Hessian's support graph, its volume growth, and an appropriate margin parameter. Under suitable structural conditions, the overall complexity scales linearly with the problem dimension. To demonstrate the practical impact of our approach, we introduce a novel framework for joint forecasting and outlier detection by extending exponential smoothing to time series with outliers. Computational experiments on both synthetic and real data sets show that our method significantly outperforms state-of-the-art solvers. |
| title | Solving Convex Quadratic Optimization with Indicators Over Structured Graphs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.02103 |