On the strength of Burer's lifted convex relaxation to quadratic programming with ball constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914880195395584 |
|---|---|
| author | Kılınç-Karzan, Fatma Sun, Shengding |
| author_facet | Kılınç-Karzan, Fatma Sun, Shengding |
| contents | We study quadratic programs with $m$ ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when $m=2$. For general $m$, Burer (2024) provides numerical evidence that this lifted relaxation is tighter than the Kronecker product based Reformulation Linearization Technique (RLT) inequalities introduced by Anstreicher (2017), and conjectures that this must be theoretically true as well. In this note, we provide an affirmative answer to this question and formally prove that this lifted relaxation indeed implies the Kronecker inequalities. Our proof is based on a decomposition of non-rank-one extreme rays of the lifted relaxation for each pair of ball constraints. Burer (2024) also numerically observes that for this lifted relaxation, an RLT-based inequality proposed by Zhen et al. (2021) is redundant, and conjectures this to be theoretically true as well. We also provide a formal proof that Zhen et al. (2021) inequalities are redundant for this lifted relaxation. In addition, we establish that Burer's lifted relaxation is a particular case of the moment-sum-of-squares hierarchy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14992 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the strength of Burer's lifted convex relaxation to quadratic programming with ball constraints Kılınç-Karzan, Fatma Sun, Shengding Optimization and Control We study quadratic programs with $m$ ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when $m=2$. For general $m$, Burer (2024) provides numerical evidence that this lifted relaxation is tighter than the Kronecker product based Reformulation Linearization Technique (RLT) inequalities introduced by Anstreicher (2017), and conjectures that this must be theoretically true as well. In this note, we provide an affirmative answer to this question and formally prove that this lifted relaxation indeed implies the Kronecker inequalities. Our proof is based on a decomposition of non-rank-one extreme rays of the lifted relaxation for each pair of ball constraints. Burer (2024) also numerically observes that for this lifted relaxation, an RLT-based inequality proposed by Zhen et al. (2021) is redundant, and conjectures this to be theoretically true as well. We also provide a formal proof that Zhen et al. (2021) inequalities are redundant for this lifted relaxation. In addition, we establish that Burer's lifted relaxation is a particular case of the moment-sum-of-squares hierarchy. |
| title | On the strength of Burer's lifted convex relaxation to quadratic programming with ball constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2407.14992 |