SOS-konvexnost - SOS-convexity

A vícerozměrný polynom je SOS-konvexní (nebo součet čtverců konvexní) Pokud je to Hesenská matice H lze započítat jako H(X) = S^T(X)S(X) kde S je matice (možná obdélníková), ve které jsou položky polynomy X.^[1] Jinými slovy, hesenská matice je a SOS maticový polynom.

Ekvivalentní definice je, že forma definovaná jako G(X,y) = y^TH(X)y je součet čtverců forem.^[2]

Spojení s konvexitou

Pokud je polynom konvexní SOS, pak je také konvexní. Od stanovení, zda polynom je SOS-konvexní, se rovná řešení a semidefinitní programování problém, SOS-konvexnost lze použít jako proxy pro stanovení, zda je polynom konvexní. Naproti tomu rozhodování, zda je obecný polynom stupně většího než čtyři konvexní, je NP-těžký problém.^[3]

První protipříklad polynomu, který je konvexní, ale ne SOS-konvexní, zkonstruoval Amir Ali Ahmadi a Pablo Parrilo v roce 2009.^[4] Polynom je homogenní polynom, který je součtem čtverců a je dán vztahem:^[4]

${ displaystyle p (x) = 32x_ {1} ^ {8} + 118x_ {1} ^ {6} x_ {2} ^ {2} + 40x_ {1} ^ {6} x_ {3} ^ {2} + 25x_ {1} ^ {4} x_ {2} ^ {4} -43x_ {1} ^ {4} x_ {2} ^ {2} x_ {3} ^ {2} -35x_ {1} ^ {4 } x_ {3} ^ {4} + 3x_ {1} ^ {2} x_ {2} ^ {4} x_ {3} ^ {2} -16x_ {1} ^ {2} x_ {2} ^ {2 } x_ {3} ^ {4} + 24x_ {1} ^ {2} x_ {3} ^ {6} + 16x_ {2} ^ {8} + 44x_ {2} ^ {6} x_ {3} ^ { 2} + 70x_ {2} ^ {4} x_ {3} ^ {4} + 60x_ {2} ^ {2} x_ {3} ^ {6} + 30x_ {3} ^ {8}}$

Ve stejném roce se Grigoriy Blekherman ukázal v a nekonstruktivní způsobem, že existují konvexní formy, které nelze vyjádřit jako součet čtverců.^[5]

Spojení s nezáporností a čtverci

V roce 2013 Amir Ali Ahmadi a Pablo Parrilo ukázal, že každý konvexní homogenní polynom v n proměnné a stupeň 2d je SOS-konvexní právě tehdy, když buď (a) n = 2 nebo (b) 2d = 2 nebo (c) n = 3 a 2d = 4.^[6] Působivě platí, že stejný vztah platí pro nezáporný homogenní polynom v n proměnné a stupeň 2d které lze vyjádřit jako součet polynomů čtverců (viz Hilbertův sedmnáctý problém ).

Reference

^ Helton, J. William; Nie, Jiawang (2010). Msgstr "Semidefinitní reprezentace konvexních množin". Matematické programování. 122 (1): 21–64. arXiv:0705.4068. doi:10.1007 / s10107-008-0240-r. ISSN 0025-5610. S2CID 1352703.
^ Ahmadi, Amir Ali; Parrilo, Pablo A. (2010). "O rovnocennosti algebraických podmínek pro konvexitu a kvazikonvexitu polynomů". 49. konference IEEE o rozhodování a kontrole (CDC): 3343–3348. doi:10.1109 / CDC.2010.5717510. hdl:1721.1/74151. ISBN 978-1-4244-7745-6. S2CID 11904851.
^ Ahmadi, Amir Ali; Olševskij, Alex; Parrilo, Pablo A .; Tsitsiklis, John N. (2013). "NP-tvrdost rozhodování o konvexnosti kvartických polynomů a související problémy". Matematické programování. 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). "Pozitivní určitý polynom Hessian, který nezohledňuje". Sborník z 48h konference IEEE o rozhodování a kontrole (CDC) pořádané společně s 28. čínskou konferencí o kontrole 2009: 1195–1200. doi:10.1109 / CDC.2009.5400519. hdl:1721.1/58871. ISBN 978-1-4244-3871-6. S2CID 5344338.
^ Blekherman, Grigoriy (04.10.2009). "Konvexní formy, které nejsou součty čtverců". arXiv:0910.0656 [math.AG ].
^ Ahmadi, Amir Ali; Parrilo, Pablo A. (2013). "Úplná charakteristika mezery mezi konvexitou a SOS-konvexitou". SIAM Journal on Optimization. 23 (2): 811–833. arXiv:1111.4587. doi:10.1137/110856010. ISSN 1052-6234. S2CID 16801871.

Viz také

[1] Helton, J. William; Nie, Jiawang (2010). Msgstr "Semidefinitní reprezentace konvexních množin". Matematické programování. 122 (1): 21–64. arXiv:0705.4068. doi:10.1007 / s10107-008-0240-r. ISSN 0025-5610. S2CID 1352703.

[2] Ahmadi, Amir Ali; Parrilo, Pablo A. (2010). "O rovnocennosti algebraických podmínek pro konvexitu a kvazikonvexitu polynomů". 49. konference IEEE o rozhodování a kontrole (CDC): 3343–3348. doi:10.1109 / CDC.2010.5717510. hdl:1721.1/74151. ISBN 978-1-4244-7745-6. S2CID 11904851.

[3] Ahmadi, Amir Ali; Olševskij, Alex; Parrilo, Pablo A .; Tsitsiklis, John N. (2013). "NP-tvrdost rozhodování o konvexnosti kvartických polynomů a související problémy". Matematické programování. 137 (1–2): 453–476. arXiv:1012.1908. doi:10.1007 / s10107-011-0499-2. ISSN 0025-5610. S2CID 2319461.

[:0-4] A ^b Ahmadi, Amir Ali; Parrilo, Pablo A. (2009). "Pozitivní určitý polynom Hessian, který nezohledňuje". Sborník z 48h konference IEEE o rozhodování a kontrole (CDC) pořádané společně s 28. čínskou konferencí o kontrole 2009: 1195–1200. doi:10.1109 / CDC.2009.5400519. hdl:1721.1/58871. ISBN 978-1-4244-3871-6. S2CID 5344338.

[5] Blekherman, Grigoriy (04.10.2009). "Konvexní formy, které nejsou součty čtverců". arXiv:0910.0656 [math.AG ].

[6] Ahmadi, Amir Ali; Parrilo, Pablo A. (2013). "Úplná charakteristika mezery mezi konvexitou a SOS-konvexitou". SIAM Journal on Optimization. 23 (2): 811–833. arXiv:1111.4587. doi:10.1137/110856010. ISSN 1052-6234. S2CID 16801871.

[1]

[2]

[3]

[4]

[5]

[6]