SOS-dışbükeylik - SOS-convexity

Bir çok değişkenli polinom dır-dir SOS-dışbükey (veya kareler toplamı dışbükey) eğer onun Hessen matrisi H olarak çarpanlara ayrılabilir H(x) = S^T(x)S(x) nerede S girişlerin polinomlar olduğu bir matristir (muhtemelen dikdörtgen) x.^[1] Başka bir deyişle, Hessian matrisi bir SOS matris polinomu.

Eşdeğer bir tanım, formun şu şekilde tanımlanmasıdır: g(x,y) = y^TH(x)y bir formların karelerinin toplamı.^[2]

Dışbükeylik ile bağlantı

Bir polinom SOS-konveks ise, o zaman da konvekstir. Bir polinomun SOS-konveks olup olmadığını belirlemek, bir yarı belirsiz programlama problem, SOS-konvekslik bir polinomun konveks olup olmadığını belirlemek için bir vekil olarak kullanılabilir. Bunun aksine, dörtten büyük bir genel polinomun dışbükey olup olmadığına karar vermek NP açısından zor bir sorundur.^[3]

Dışbükey olan ancak SOS dışbükey olmayan bir polinomun ilk karşı örneği, Amir Ali Ahmedi ve Pablo Parrilo 2009 yılında.^[4] Polinom, karelerin toplamı olan ve aşağıdakiler tarafından verilen homojen bir polinomdur:^[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}}$

Aynı yıl, Grigoriy Blekherman, yapıcı olmayan karelerin toplamı olarak gösterilemeyen dışbükey formların var olduğu şekilde.^[5]

Olumsuzluk ve karelerin toplamı ile bağlantı

2013 yılında Amir Ali Ahmedi ve Pablo Parrilo her dışbükey homojen polinomun n değişkenler ve derece 2d SOS-dışbükeydir ancak ve ancak (a) n = 2 veya (b) 2d = 2 veya (c) n = 3 ve 2d = 4.^[6] Etkileyici bir şekilde, aynı ilişki negatif olmayan homojen polinom için de geçerlidir. n değişkenler ve derece 2d bu, polinom karelerinin toplamı olarak gösterilebilir (Bkz. Hilbert'in on yedinci problemi ).

Referanslar

^ Helton, J. William; Nie, Jiawang (2010). "Dışbükey kümelerin yarı kesin gösterimi". Matematiksel Programlama. 122 (1): 21–64. arXiv:0705.4068. doi:10.1007 / s10107-008-0240-y. ISSN 0025-5610. S2CID 1352703.
^ Ahmedi, Amir Ali; Parrilo, Pablo A. (2010). "Polinomların dışbükeyliği ve yarı konveksliği için cebirsel koşulların denkliği hakkında". 49. IEEE Karar ve Kontrol Konferansı (CDC): 3343–3348. doi:10.1109 / CDC.2010.5717510. hdl:1721.1/74151. ISBN 978-1-4244-7745-6. S2CID 11904851.
^ Ahmedi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A .; Tsitsiklis, John N. (2013). "Dördüncül polinomların konveksitesine karar vermenin NP sertliği ve ilgili problemler". Matematiksel Programlama. 137 (1–2): 453–476. arXiv:1012.1908. doi:10.1007 / s10107-011-0499-2. ISSN 0025-5610. S2CID 2319461.
^ ^a ^b Ahmedi, Amir Ali; Parrilo, Pablo A. (2009). "Çarpanlara ayırmayan pozitif bir kesin polinom Hessian". 2009 28. Çin Kontrol Konferansı ile Ortak Olarak Düzenlenen 48 Saatlik IEEE Karar ve Kontrol Konferansı (CDC) Bildirileri: 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). "Karelerin Toplamı Olmayan Dışbükey Formlar". arXiv:0910.0656 [math.AG ].
^ Ahmedi, Amir Ali; Parrilo, Pablo A. (2013). "Konveksite ve SOS-Konveksite Arasındaki Boşluğun Tam Bir Karakterizasyonu". SIAM Optimizasyon Dergisi. 23 (2): 811–833. arXiv:1111.4587. doi:10.1137/110856010. ISSN 1052-6234. S2CID 16801871.

Ayrıca bakınız

[1] Helton, J. William; Nie, Jiawang (2010). "Dışbükey kümelerin yarı kesin gösterimi". Matematiksel Programlama. 122 (1): 21–64. arXiv:0705.4068. doi:10.1007 / s10107-008-0240-y. ISSN 0025-5610. S2CID 1352703.

[2] Ahmedi, Amir Ali; Parrilo, Pablo A. (2010). "Polinomların dışbükeyliği ve yarı konveksliği için cebirsel koşulların denkliği hakkında". 49. IEEE Karar ve Kontrol Konferansı (CDC): 3343–3348. doi:10.1109 / CDC.2010.5717510. hdl:1721.1/74151. ISBN 978-1-4244-7745-6. S2CID 11904851.

[3] Ahmedi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A .; Tsitsiklis, John N. (2013). "Dördüncül polinomların konveksitesine karar vermenin NP sertliği ve ilgili problemler". Matematiksel Programlama. 137 (1–2): 453–476. arXiv:1012.1908. doi:10.1007 / s10107-011-0499-2. ISSN 0025-5610. S2CID 2319461.

[:0-4] Ahmedi, Amir Ali; Parrilo, Pablo A. (2009). "Çarpanlara ayırmayan pozitif bir kesin polinom Hessian". 2009 28. Çin Kontrol Konferansı ile Ortak Olarak Düzenlenen 48 Saatlik IEEE Karar ve Kontrol Konferansı (CDC) Bildirileri: 1195–1200. doi:10.1109 / CDC.2009.5400519. hdl:1721.1/58871. ISBN 978-1-4244-3871-6. S2CID 5344338.

[5] Blekherman, Grigoriy (2009-10-04). "Karelerin Toplamı Olmayan Dışbükey Formlar". arXiv:0910.0656 [math.AG ].

[6] Ahmedi, Amir Ali; Parrilo, Pablo A. (2013). "Konveksite ve SOS-Konveksite Arasındaki Boşluğun Tam Bir Karakterizasyonu". SIAM Optimizasyon Dergisi. 23 (2): 811–833. arXiv:1111.4587. doi:10.1137/110856010. ISSN 1052-6234. S2CID 16801871.

[1]

[2]

[3]

[4]

[5]

[6]