A Complete Characterization of the Gap between Convexity and SOS-Convexity
Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials, via the definition of convexity, its first order characterization, and its second order characterization, are equivalent. These three equivalent algebrai...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81433 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1826204430981136384 |
|---|---|
| author | Ahmadi, Amir Ali Parrilo, Pablo A. |
| 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 Ahmadi, Amir Ali Parrilo, Pablo A. |
| author_sort | Ahmadi, Amir Ali |
| collection | MIT |
| description | Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials, via the definition of convexity, its first order characterization, and its second order characterization, are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming, whereas deciding convexity is NP-hard. If we denote the set of convex and sos-convex polynomials in $n$ variables of degree $d$ with $\tilde{C}_{n,d}$ and $\tilde{\Sigma C}_{n,d}$ respectively, then our main contribution is to prove that $\tilde{C}_{n,d}=\tilde{\Sigma C}_{n,d}$ if and only if $n=1$ or $d=2$ or $(n,d)=(2,4)$. We also present a complete characterization for forms (homogeneous polynomials) except for the case $(n,d)=(3,4)$, which is joint work with Blekherman and is to be published elsewhere. Our result states that the set $C_{n,d}$ of convex forms in $n$ variables of degree $d$ equals the set $\Sigma C_{n,d}$ of sos-convex forms if and only if $n=2$ or $d=2$ or $(n,d)=(3,4)$. To prove these results, we present in particular explicit examples of polynomials in $\tilde{C}_{2,6}\setminus\tilde{\Sigma C}_{2,6}$ and $\tilde{C}_{3,4}\setminus\tilde{\Sigma C}_{3,4}$ and forms in $C_{3,6}\setminus\Sigma C_{3,6}$ and $C_{4,4}\setminus\Sigma C_{4,4,}$ and a general procedure for constructing forms in $C_{n,d+2}\setminus\Sigma C_{n,d+2}$ from nonnegative but not sos forms in $n$ variables and degree $d$. Although for disparate reasons, the remarkable outcome is that convex polynomials (resp., forms) are sos-convex exactly in cases where nonnegative polynomials (resp., forms) are sums of squares, as characterized by Hilbert. |
| first_indexed | 2024-09-23T12:54:38Z |
| format | Article |
| id | mit-1721.1/81433 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:54:38Z |
| publishDate | 2013 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/814332022-10-01T11:50:28Z A Complete Characterization of the Gap between Convexity and SOS-Convexity Ahmadi, Amir Ali Parrilo, Pablo A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Parrilo, Pablo A. Our first contribution in this paper is to prove that three natural sum of squares (sos) based sufficient conditions for convexity of polynomials, via the definition of convexity, its first order characterization, and its second order characterization, are equivalent. These three equivalent algebraic conditions, henceforth referred to as sos-convexity, can be checked by semidefinite programming, whereas deciding convexity is NP-hard. If we denote the set of convex and sos-convex polynomials in $n$ variables of degree $d$ with $\tilde{C}_{n,d}$ and $\tilde{\Sigma C}_{n,d}$ respectively, then our main contribution is to prove that $\tilde{C}_{n,d}=\tilde{\Sigma C}_{n,d}$ if and only if $n=1$ or $d=2$ or $(n,d)=(2,4)$. We also present a complete characterization for forms (homogeneous polynomials) except for the case $(n,d)=(3,4)$, which is joint work with Blekherman and is to be published elsewhere. Our result states that the set $C_{n,d}$ of convex forms in $n$ variables of degree $d$ equals the set $\Sigma C_{n,d}$ of sos-convex forms if and only if $n=2$ or $d=2$ or $(n,d)=(3,4)$. To prove these results, we present in particular explicit examples of polynomials in $\tilde{C}_{2,6}\setminus\tilde{\Sigma C}_{2,6}$ and $\tilde{C}_{3,4}\setminus\tilde{\Sigma C}_{3,4}$ and forms in $C_{3,6}\setminus\Sigma C_{3,6}$ and $C_{4,4}\setminus\Sigma C_{4,4,}$ and a general procedure for constructing forms in $C_{n,d+2}\setminus\Sigma C_{n,d+2}$ from nonnegative but not sos forms in $n$ variables and degree $d$. Although for disparate reasons, the remarkable outcome is that convex polynomials (resp., forms) are sos-convex exactly in cases where nonnegative polynomials (resp., forms) are sums of squares, as characterized by Hilbert. National Science Foundation (U.S.) (Grant DMS-0757207) 2013-10-18T16:46:39Z 2013-10-18T16:46:39Z 2013-05 2012-10 Article http://purl.org/eprint/type/JournalArticle 1052-6234 1095-7189 http://hdl.handle.net/1721.1/81433 Ahmadi, Amir Ali, and Pablo A. Parrilo. “A Complete Characterization of the Gap between Convexity and SOS-Convexity.” SIAM Journal on Optimization 23, no. 2 (April 4, 2013): 811-833. © 2013 Society for Industrial and Applied Mathematics https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1137/110856010 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 | Ahmadi, Amir Ali Parrilo, Pablo A. A Complete Characterization of the Gap between Convexity and SOS-Convexity |
| title | A Complete Characterization of the Gap between Convexity and SOS-Convexity |
| title_full | A Complete Characterization of the Gap between Convexity and SOS-Convexity |
| title_fullStr | A Complete Characterization of the Gap between Convexity and SOS-Convexity |
| title_full_unstemmed | A Complete Characterization of the Gap between Convexity and SOS-Convexity |
| title_short | A Complete Characterization of the Gap between Convexity and SOS-Convexity |
| title_sort | complete characterization of the gap between convexity and sos convexity |
| url | http://hdl.handle.net/1721.1/81433 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT ahmadiamirali acompletecharacterizationofthegapbetweenconvexityandsosconvexity AT parrilopabloa acompletecharacterizationofthegapbetweenconvexityandsosconvexity AT ahmadiamirali completecharacterizationofthegapbetweenconvexityandsosconvexity AT parrilopabloa completecharacterizationofthegapbetweenconvexityandsosconvexity |