Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.09864 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911503511191552 |
|---|---|
| author | Günlük, Oktay Jünger, Paul Linderoth, Jeff Lodi, Andrea Luedtke, James |
| author_facet | Günlük, Oktay Jünger, Paul Linderoth, Jeff Lodi, Andrea Luedtke, James |
| contents | We consider optimization problems containing nonconvex quadratic functions for which semidefinite programming (SDP) relaxations often yield strong bounds. We investigate linear inequalities that outer approximate the positive semidefinite cone and are sparse in the sense that they are supported only on the variables corresponding to products of variables present in quadratic functions. We show that these sparse linear inequalities yield an LP relaxation that gives the same bound as the SDP relaxation. We demonstrate how to identify these inequalities via a separation procedure that involves solving a structured ``projection'' SDP. In a computational study, we find that the sparse LP relaxations defined by these inequalities can accelerate branch-and-bound methods for globally solving nonconvex optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09864 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sparse Cuts for the Positive Semidefinite Cone Günlük, Oktay Jünger, Paul Linderoth, Jeff Lodi, Andrea Luedtke, James Optimization and Control We consider optimization problems containing nonconvex quadratic functions for which semidefinite programming (SDP) relaxations often yield strong bounds. We investigate linear inequalities that outer approximate the positive semidefinite cone and are sparse in the sense that they are supported only on the variables corresponding to products of variables present in quadratic functions. We show that these sparse linear inequalities yield an LP relaxation that gives the same bound as the SDP relaxation. We demonstrate how to identify these inequalities via a separation procedure that involves solving a structured ``projection'' SDP. In a computational study, we find that the sparse LP relaxations defined by these inequalities can accelerate branch-and-bound methods for globally solving nonconvex optimization problems. |
| title | Sparse Cuts for the Positive Semidefinite Cone |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.09864 |