SOS-convexity: Difference between revisions
TheMathCat (talk | contribs) m wikilink |
Correct polynomial degree information |
||
| Line 6: | Line 6: | ||
== Connection with convexity == |
== Connection with convexity == |
||
If a polynomial is SOS-convex, then it is also convex.{{Citation needed|date=July 2021}} Since establishing whether a polynomial is SOS-convex amounts to solving a [[semidefinite programming]] problem, SOS-convexity can be used as a proxy to establishing if a polynomial is convex. In contrast, deciding if a generic polynomial of degree |
If a polynomial is SOS-convex, then it is also convex.{{Citation needed|date=July 2021}} Since establishing whether a polynomial is SOS-convex amounts to solving a [[semidefinite programming]] problem, SOS-convexity can be used as a proxy to establishing if a polynomial is convex. In contrast, deciding if a generic quartic polynomial of degree four (or higher even degree) is convex is a NP-hard problem.<ref>{{Cite journal|last1=Ahmadi|first1=Amir Ali|last2=Olshevsky|first2=Alex|last3=Parrilo|first3=Pablo A.|last4=Tsitsiklis|first4=John N.|date=2013|title=NP-hardness of deciding convexity of quartic polynomials and related problems|journal=Mathematical Programming|language=en|volume=137|issue=1–2|pages=453–476|doi=10.1007/s10107-011-0499-2|issn=0025-5610|arxiv=1012.1908|s2cid=2319461}}</ref> |
||
The first counterexample of a polynomial which is convex but not SOS-convex was constructed by [[Amir Ali Ahmadi]] and [[Pablo Parrilo]] in 2009.<ref name=":0">{{Cite book|last1=Ahmadi|first1=Amir Ali|last2=Parrilo|first2=Pablo A.|title=Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference |chapter=A positive definite polynomial Hessian that does not factor |date=2009|pages=1195–1200|doi=10.1109/CDC.2009.5400519|hdl=1721.1/58871|isbn=978-1-4244-3871-6|s2cid=5344338|hdl-access=free}}</ref> The polynomial is a homogeneous polynomial that is sum-of-squares and given by:<ref name=":0" /> |
The first counterexample of a polynomial which is convex but not SOS-convex was constructed by [[Amir Ali Ahmadi]] and [[Pablo Parrilo]] in 2009.<ref name=":0">{{Cite book|last1=Ahmadi|first1=Amir Ali|last2=Parrilo|first2=Pablo A.|title=Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference |chapter=A positive definite polynomial Hessian that does not factor |date=2009|pages=1195–1200|doi=10.1109/CDC.2009.5400519|hdl=1721.1/58871|isbn=978-1-4244-3871-6|s2cid=5344338|hdl-access=free}}</ref> The polynomial is a homogeneous polynomial that is sum-of-squares and given by:<ref name=":0" /> |
||
Latest revision as of 17:17, 25 August 2024
 | This article may be too technical for most readers to understand. (July 2020) |
A multivariate polynomial is SOS-convex (or sum of squares convex) if its Hessian matrix H can be factored as H(x) = ST(x)S(x) where S is a matrix (possibly rectangular) which entries are polynomials in x.[1] In other words, the Hessian matrix is a SOS matrix polynomial.
An equivalent definition is that the form defined as g(x,y) = yTH(x)y is a sum of squares of forms.[2]
Connection with convexity
[edit]If a polynomial is SOS-convex, then it is also convex.[citation needed] Since establishing whether a polynomial is SOS-convex amounts to solving a semidefinite programming problem, SOS-convexity can be used as a proxy to establishing if a polynomial is convex. In contrast, deciding if a generic quartic polynomial of degree four (or higher even degree) is convex is a NP-hard problem.[3]
The first counterexample of a polynomial which is convex but not SOS-convex was constructed by Amir Ali Ahmadi and Pablo Parrilo in 2009.[4] The polynomial is a homogeneous polynomial that is sum-of-squares and given by:[4]
In the same year, Grigoriy Blekherman proved in a non-constructive manner that there exist convex forms that is not representable as sum of squares.[5] An explicit example of a convex form (with degree 4 and 272 variables) that is not a sum of squares was claimed by James Saunderson in 2021.[6]
Connection with non-negativity and sum-of-squares
[edit]In 2013 Amir Ali Ahmadi and Pablo Parrilo showed that every convex homogeneous polynomial in n variables and degree 2d is SOS-convex if and only if either (a) n = 2 or (b) 2d = 2 or (c) n = 3 and 2d = 4.[7] Impressively, the same relation is valid for non-negative homogeneous polynomial in n variables and degree 2d that can be represented as sum of squares polynomials (See Hilbert's seventeenth problem).
References
[edit]- ^ Helton, J. William; Nie, Jiawang (2010). "Semidefinite representation of convex sets". Mathematical Programming. 122 (1): 21–64. arXiv:0705.4068. doi:10.1007/s10107-008-0240-y. ISSN 0025-5610. S2CID 1352703.
- ^ Ahmadi, Amir Ali; Parrilo, Pablo A. (2010). "On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials". 49th IEEE Conference on Decision and Control (CDC). pp. 3343–3348. doi:10.1109/CDC.2010.5717510. hdl:1721.1/74151. ISBN 978-1-4244-7745-6. S2CID 11904851.
- ^ Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N. (2013). "NP-hardness of deciding convexity of quartic polynomials and related problems". Mathematical Programming. 137 (1–2): 453–476. arXiv:1012.1908. doi:10.1007/s10107-011-0499-2. ISSN 0025-5610. S2CID 2319461.
- ^ a b Ahmadi, Amir Ali; Parrilo, Pablo A. (2009). "A positive definite polynomial Hessian that does not factor". Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference. pp. 1195–1200. doi:10.1109/CDC.2009.5400519. hdl:1721.1/58871. ISBN 978-1-4244-3871-6. S2CID 5344338.
- ^ Blekherman, Grigoriy (2009-10-04). "Convex Forms that are not Sums of Squares". arXiv:0910.0656 [math.AG].
- ^ Saunderson, James (2022). "A Convex Form That is Not a Sum of Squares". Mathematics of Operations Research. 48: 569–582. arXiv:2105.08432. doi:10.1287/moor.2022.1273. S2CID 234763204.
- ^ Ahmadi, Amir Ali; Parrilo, Pablo A. (2013). "A Complete Characterization of the Gap between Convexity and SOS-Convexity". SIAM Journal on Optimization. 23 (2): 811–833. arXiv:1111.4587. doi:10.1137/110856010. ISSN 1052-6234. S2CID 16801871.