Everything is possible: constructing spectrahedra with prescribed facial dimensions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909293851181056 |
|---|---|
| author | Roshchina, Vera Tunçel, Levent |
| author_facet | Roshchina, Vera Tunçel, Levent |
| contents | Given any finite set of nonnegative integers, there exists a closed convex set whose facial dimension signature coincides with this set of integers, that is, the dimensions of its nonempty faces comprise exactly this set of integers. In this work, we show that such sets can be realised as solution sets of systems of finitely many convex quadratic inequalities, and hence are representable via second-order cone programming problems, and are, in particular, spectrahedral. It also follows that these sets are facially exposed, in contrast to earlier constructions. We obtain a lower bound on the minimum number of convex quadratic inequalities needed to represent a closed convex set with prescribed facial dimension signature, and show that our bound is tight for some special cases. Finally, we relate the question of finding efficient representations with indecomposability of integer sequences and other topics, and discuss a substantial number of open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04419 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Everything is possible: constructing spectrahedra with prescribed facial dimensions Roshchina, Vera Tunçel, Levent Optimization and Control Combinatorics 90C22, 90C25, 52A38 Given any finite set of nonnegative integers, there exists a closed convex set whose facial dimension signature coincides with this set of integers, that is, the dimensions of its nonempty faces comprise exactly this set of integers. In this work, we show that such sets can be realised as solution sets of systems of finitely many convex quadratic inequalities, and hence are representable via second-order cone programming problems, and are, in particular, spectrahedral. It also follows that these sets are facially exposed, in contrast to earlier constructions. We obtain a lower bound on the minimum number of convex quadratic inequalities needed to represent a closed convex set with prescribed facial dimension signature, and show that our bound is tight for some special cases. Finally, we relate the question of finding efficient representations with indecomposability of integer sequences and other topics, and discuss a substantial number of open questions. |
| title | Everything is possible: constructing spectrahedra with prescribed facial dimensions |
| topic | Optimization and Control Combinatorics 90C22, 90C25, 52A38 |
| url | https://arxiv.org/abs/2312.04419 |