On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918428794683392 |
|---|---|
| author | Burer, Samuel Natarajan, Karthik |
| author_facet | Burer, Samuel Natarajan, Karthik |
| contents | We study continuous quadratic submodular minimization with bounds and propose a polynomially sized semidefinite relaxation, which is provably tight for dimension $n \le 3$ and empirically tight for larger $n$. We apply the relaxation to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing study of continuous submodular minimization and opens new application areas therein. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03996 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems Burer, Samuel Natarajan, Karthik Optimization and Control 90C20 (Primary), 90C22, 44A60 (Secondary) We study continuous quadratic submodular minimization with bounds and propose a polynomially sized semidefinite relaxation, which is provably tight for dimension $n \le 3$ and empirically tight for larger $n$. We apply the relaxation to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing study of continuous submodular minimization and opens new application areas therein. |
| title | On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems |
| topic | Optimization and Control 90C20 (Primary), 90C22, 44A60 (Secondary) |
| url | https://arxiv.org/abs/2504.03996 |