Theta Bodies for Polynomial Ideals
Inspired by a question of Lovász, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal called theta bodies of the ideal. These relaxations generalize Lovász's construction of the theta body of a graph. We establish a r...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2010
|
| Online Access: | http://hdl.handle.net/1721.1/58469 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1811083567272296448 |
|---|---|
| author | Parrilo, Pablo A. Thomas, Rekha R. Gouveia, João |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Parrilo, Pablo A. Thomas, Rekha R. Gouveia, João |
| author_sort | Parrilo, Pablo A. |
| collection | MIT |
| description | Inspired by a question of Lovász, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal called theta bodies of the ideal. These relaxations generalize Lovász's construction of the theta body of a graph. We establish a relationship between theta bodies and Lasserre's relaxations for real varieties which allows, in many cases, for theta bodies to be expressed as feasible regions of semidefinite programs. Examples from combinatorial optimization are given. Lovász asked to characterize ideals for which the first theta body equals the closure of the convex hull of its real variety. We answer this question for vanishing ideals of finite point sets via several equivalent characterizations. We also give a geometric description of the first theta body for all ideals. |
| first_indexed | 2024-09-23T12:35:07Z |
| format | Article |
| id | mit-1721.1/58469 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:35:07Z |
| publishDate | 2010 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/584692022-09-28T08:48:34Z Theta Bodies for Polynomial Ideals THETA BODIES FOR POLYNOMIAL IDEALS Parrilo, Pablo A. Thomas, Rekha R. Gouveia, João Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Parrilo, Pablo A. Parrilo, Pablo A. Inspired by a question of Lovász, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal called theta bodies of the ideal. These relaxations generalize Lovász's construction of the theta body of a graph. We establish a relationship between theta bodies and Lasserre's relaxations for real varieties which allows, in many cases, for theta bodies to be expressed as feasible regions of semidefinite programs. Examples from combinatorial optimization are given. Lovász asked to characterize ideals for which the first theta body equals the closure of the convex hull of its real variety. We answer this question for vanishing ideals of finite point sets via several equivalent characterizations. We also give a geometric description of the first theta body for all ideals. National Science Foundation (Focused Research Group grant (DMS-0757371, DMS-0757207)) 2010-09-03T20:59:56Z 2010-09-03T20:59:56Z 2010-03 2010-01 Article http://purl.org/eprint/type/JournalArticle 1052-6234 1095-7189 http://hdl.handle.net/1721.1/58469 Gouveia, João, Pablo A. Parrilo, and Rekha R. Thomas. "Theta Bodies for Polynomial Ideals." SIAM J. Optim. Volume 20, Issue 4, pp. 2097-2118 (2010) ©2010 Society for Industrial and Applied Mathematics. https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1137/090746525 SIAM Journal on Optimization Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Parrilo, Pablo A. Thomas, Rekha R. Gouveia, João Theta Bodies for Polynomial Ideals |
| title | Theta Bodies for Polynomial Ideals |
| title_full | Theta Bodies for Polynomial Ideals |
| title_fullStr | Theta Bodies for Polynomial Ideals |
| title_full_unstemmed | Theta Bodies for Polynomial Ideals |
| title_short | Theta Bodies for Polynomial Ideals |
| title_sort | theta bodies for polynomial ideals |
| url | http://hdl.handle.net/1721.1/58469 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT parrilopabloa thetabodiesforpolynomialideals AT thomasrekhar thetabodiesforpolynomialideals AT gouveiajoao thetabodiesforpolynomialideals |