Polynomiální SOS - Polynomial SOS

v matematika, a formulář (tj. homogenní polynom) h(X) stupně 2m ve skutečnosti n-dimenzionální vektor X je součet čtverců formulářů (SOS) právě tehdy, pokud existují formuláře ${ displaystyle g_ {1} (x), ldots, g_ {k} (x)}$ stupně m takhle

{ displaystyle h (x) = součet _ {i = 1} ^ {k} g_ {i} (x) ^ {2}.}

Každá forma, která je SOS, je také pozitivní polynom, a ačkoli konverzace není vždy pravdivá, Hilbert to dokázal pro n = 2, m = 1 nebo n = 3 a 2m = 4 formulář je SOS právě tehdy, pokud je kladný.^[1] Totéž platí také pro analogový problém na pozitivní symetrický formuláře.^[2]^[3]

Ačkoli ne každý formulář může být reprezentován jako SOS, byly nalezeny výslovně dostatečné podmínky pro to, aby byl formulář SOS.^[4]^[5] Kromě toho lze každou skutečnou nezápornou formu aproximovat co nejblíže (v souboru) ${ displaystyle l_ {1}}$ -norm svého vektoru koeficientu) posloupností forem ${ displaystyle {f _ { epsilon} }}$ to jsou SOS.^[6]

Čtvercová maticová reprezentace (SMR)

Chcete-li zjistit, zda formulář h(X) je SOS rovná řešení a konvexní optimalizace problém. Opravdu každý h(X) lze psát jako

{ displaystyle h (x) = x ^ { {m } '} vlevo (H + L ( alpha) vpravo) x ^ { {m }}}

kde ${ displaystyle x ^ { {m }}}$ je vektor obsahující základ pro formy stupně m v X (jako jsou všechny monomily stupně m v X), prvočíslo ′ označuje přemístit, H je libovolná symetrická matice vyhovující

{ displaystyle h (x) = x ^ { vlevo {m vpravo } '} Vx ^ { {m }}}

a ${ displaystyle L ( alpha)}$ je lineární parametrizace lineární prostor

{ displaystyle { mathcal {L}} = vlevo {L = L ': ~ x ^ { {m }'} Lx ^ { {m }} = 0 vpravo }.}

Rozměr vektoru ${ displaystyle x ^ { {m }}}$ je dána

{ displaystyle sigma (n, m) = { binom {n + m-1} {m}}}

zatímco rozměr vektoru ${ displaystyle alpha}$ je dána

{ displaystyle omega (n, 2m) = { frac {1} {2}} sigma (n, m) levý (1+ sigma (n, m) pravý) - sigma (n, 2m ).}

Pak, h(X) je SOS právě tehdy, když existuje vektor ${ displaystyle alpha}$ takhle

{ displaystyle H + L ( alpha) geq 0,}

což znamená, že matice ${ displaystyle H + L ( alpha)}$ je kladně semidefinitní. Tohle je lineární maticová nerovnost (LMI) test proveditelnosti, což je konvexní optimalizační problém. Výraz ${ displaystyle h (x) = x ^ { {m } '} vlevo (H + L ( alpha) vpravo) x ^ { {m }}}$ byl představen v ^[7] s názvem square matricial representation (SMR) za účelem zjištění, zda je formulář SOS prostřednictvím LMI. Tato reprezentace je také známá jako Gramova matice.^[8]

Příklady

Zvažte formu stupně 4 ve dvou proměnných ${ displaystyle h (x) = x_ {1} ^ {4} -x_ {1} ^ {2} x_ {2} ^ {2} + x_ {2} ^ {4}}$ . My máme

{ displaystyle m = 2, ~ x ^ { {m }} = vlevo ({ begin {pole} {c} x_ {1} ^ {2} x_ {1} x_ {2} x_ {2} ^ {2} end {array}} right), ~ H + L ( alpha) = left ({ begin {array} {ccc} 1 & 0 & - alpha _ {1} 0 & -1 + 2 alpha _ {1} & 0 - alpha _ {1} & 0 & 1 end {array}} right).}

Protože existuje α takové, že

{ displaystyle H + L ( alpha) geq 0}

, jmenovitě

{ displaystyle alpha = 1}

, z toho vyplývá, že h(X) je SOS.

Zvažte formu stupně 4 ve třech proměnných ${ displaystyle h (x) = 2x_ {1} ^ {4} -2,5x_ {1} ^ {3} x_ {2} + x_ {1} ^ {2} x_ {2} x_ {3} -2x_ { 1} x_ {3} ^ {3} + 5x_ {2} ^ {4} + x_ {3} ^ {4}}$ . My máme

{ displaystyle m = 2, ~ x ^ { {m }} = vlevo ({ begin {pole} {c} x_ {1} ^ {2} x_ {1} x_ {2} x_ {1} x_ {3} x_ {2} ^ {2} x_ {2} x_ {3} x_ {3} ^ {2} end {array}} right), ~ H + L ( alpha) = left ({ begin {array} {cccccc} 2 & -1,25 & 0 & - alpha _ {1} & - alpha _ {2} & - alpha _ {3} - 1,25 & 2 alpha _ {1} & 0,5 + alpha _ {2} & 0 & - alpha _ {4} & - alpha _ {5} 0 & 0,5 + alpha _ {2} & 2 alpha _ { 3} & alpha _ {4} & alpha _ {5} & - 1 - alpha _ {1} & 0 & alpha _ {4} & 5 & 0 & - alpha _ {6} - alpha _ { 2} & - alpha _ {4} & alpha _ {5} & 0 & 2 alpha _ {6} & 0 - alpha _ {3} & - alpha _ {5} & - 1 & - alpha _ { 6} & 0 & 1 end {array}} right).}

Od té doby

{ displaystyle H + L ( alpha) geq 0}

pro

{ displaystyle alpha = (1,18, -0,43,0,73,1,13, -0,37,0,57)}

, z toho vyplývá, že h(X) je SOS.

Zobecnění

Matrix SOS

Maticová forma F(X) (tj. matice, jejíž záznamy jsou formy) dimenze r a stupeň 2 m ve skutečnosti n-dimenzionální vektor X je SOS právě tehdy, pokud existují maticové formy ${ displaystyle G_ {1} (x), ldots, G_ {k} (x)}$ stupně m takhle

{ displaystyle F (x) = součet _ {i = 1} ^ {k} G_ {i} (x) 'G_ {i} (x).}

Matice SMR

Chcete-li zjistit, zda je maticová forma F(X) je SOS rovná se řešení konvexního optimalizačního problému. Ve skutečnosti, podobně jako skalární případ F(X) lze psát podle SMR as

{ displaystyle F (x) = vlevo (x ^ { {m }} krát I_ {r} vpravo) ' vlevo (H + L ( alpha) vpravo) vlevo (x ^ { {m }} mnohokrát I_ {r} vpravo)}

kde ${ displaystyle otimes}$ je Produkt Kronecker matic, H je libovolná symetrická matice vyhovující

{ displaystyle F (x) = levý (x ^ { {m }} další I_ {r} pravý) 'H levý (x ^ { {m }} další I_ {r} že jo)}

a ${ displaystyle L ( alpha)}$ je lineární parametrizace lineárního prostoru

{ displaystyle { mathcal {L}} = vlevo {L = L ': ~ vlevo (x ^ { {m }} často I_ {r} vpravo)' L vlevo (x ^ { {m }} mnohokrát I_ {r} right) = 0 right }.}

Rozměr vektoru ${ displaystyle alpha}$ je dána

{ displaystyle omega (n, 2m, r) = { frac {1} {2}} r levý ( sigma (n, m) levý (r sigma (n, m) +1 pravý) - (r + 1) sigma (n, 2 m) vpravo).}

Pak, F(X) je SOS právě tehdy, když existuje vektor ${ displaystyle alpha}$ tak, že platí následující LMI:

{ displaystyle H + L ( alfa) geq 0.}

Výraz ${ displaystyle F (x) = vlevo (x ^ { {m }} krát I_ {r} vpravo) ' vlevo (H + L ( alpha) vpravo) vlevo (x ^ { {m }} mnohokrát I_ {r} vpravo)}$ byl představen v ^[9] za účelem zjištění, zda je maticová forma SOS prostřednictvím LMI.

Nekomutativní polynomiální SOS

Zvažte bezplatná algebra R⟨X⟩ Generováno n nezvyklé dopisy X = (X₁,...,X_n) a vybavené involucí ^T, takový, že ^T opravy R a X₁,...,X_n a obrácená slova tvořená X₁,...,X_nAnalogicky s komutativním případem jsou nekomutativní symetrické polynomy F jsou nekomutativní polynomy formy F = F^T. Když nějaká skutečná matice jakékoli dimenze r x r se hodnotí na symetrickém nekomutativním polynomu F vede k a pozitivní semi-definitivní matice, F se říká, že je maticový pozitivní.

Nekomutativní polynom je SOS, pokud existují nekomutativní polynomy ${ displaystyle h_ {1}, ldots, h_ {k}}$ takhle

{ displaystyle f (X) = součet _ {i = 1} ^ {k} h_ {i} (X) ^ {T} h_ {i} (X).}

Překvapivě v nekomutativním scénáři je nekomutativní polynom SoS právě tehdy, pokud je maticový pozitivní.^[10] Kromě toho existují algoritmy k rozkladu polynomů pozitivních na matici součtem čtverců nekomutativních polynomů.^[11]

Reference

^ Hilbert, David (září 1888). „Ueber die Darstellung definiter Formen als Summe von Formenquadraten“. Mathematische Annalen. 32 (3): 342–350. doi:10.1007 / bf01443605.
^ Choi, M. D .; Lam, T. Y. (1977). „Stará otázka Hilberta“. Queen's Papers in Pure and Applied Mathematics. 46: 385–405.
^ Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (Květen 2016). „Na analogii Choi-Lam z Hilbertovy věty z roku 1888 pro symetrické tvary“. Lineární algebra a její aplikace. 496: 114–120. arXiv:1505.08145. doi:10.1016 / j.laa.2016.01.024.
^ Lasserre, Jean B. (2007). „Dostatečné podmínky pro to, aby skutečný polynom byl součtem čtverců“. Archiv der Mathematik. 89 (5): 390–398. arXiv:matematika / 0612358. CiteSeerX 10.1.1.240.4438. doi:10.1007 / s00013-007-2251-r.
^ Powers, Victoria; Wörmann, Thorsten (1998). "Algoritmus pro součet čtverců skutečných polynomů" (PDF). Journal of Pure and Applied Algebra. 127 (1): 99–104. doi:10.1016 / S0022-4049 (97) 83827-3.
^ Lasserre, Jean B. (2007). "Součet čtverců aproximace nezáporných polynomů". Recenze SIAM. 49 (4): 651–669. arXiv:matematika / 0412398. Bibcode:2007SIAMR..49..651L. doi:10.1137/070693709.
^ Chesi, G .; Tesi, A .; Vicino, A .; Genesio, R. (1999). „O konvexifikaci některých problémů s minimální vzdáleností“. Sborník z 5. evropské kontrolní konference. Karlsruhe, Německo: IEEE. 1446–1451.
^ Choi, M .; Lam, T .; Reznick, B. (1995). "Součty čtverců skutečných polynomů". Proceedings of Symposia in Pure Mathematics. 103–125.
^ Chesi, G .; Garulli, A .; Tesi, A .; Vicino, A. (2003). "Robustní stabilita pro polytopické systémy prostřednictvím polynomiálně parametricky závislých Lyapunovových funkcí". Sborník 42. konference IEEE o rozhodování a kontrole. Maui, Havaj: IEEE. 4670–4675. doi:10.1109 / CDC.2003.1272307.
^ Helton, J. William (září 2002). ""Pozitivní „Nekomutativní polynomy jsou sumy čtverců“. Annals of Mathematics. 156 (2): 675–694. doi:10.2307/3597203. JSTOR 3597203.
^ Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25. října 2012). "Algoritmické aspekty součtů hermitovských čtverců nekomutativních polynomů". Výpočetní optimalizace a aplikace. 55 (1): 137–153. CiteSeerX 10.1.1.416.543. doi:10.1007 / s10589-012-9513-8.

Viz také

[1] Hilbert, David (září 1888). „Ueber die Darstellung definiter Formen als Summe von Formenquadraten“. Mathematische Annalen. 32 (3): 342–350. doi:10.1007 / bf01443605.

[2] Choi, M. D .; Lam, T. Y. (1977). „Stará otázka Hilberta“. Queen's Papers in Pure and Applied Mathematics. 46: 385–405.

[3] Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (Květen 2016). „Na analogii Choi-Lam z Hilbertovy věty z roku 1888 pro symetrické tvary“. Lineární algebra a její aplikace. 496: 114–120. arXiv:1505.08145. doi:10.1016 / j.laa.2016.01.024.

[4] Lasserre, Jean B. (2007). „Dostatečné podmínky pro to, aby skutečný polynom byl součtem čtverců“. Archiv der Mathematik. 89 (5): 390–398. arXiv:matematika / 0612358. CiteSeerX 10.1.1.240.4438. doi:10.1007 / s00013-007-2251-r.

[5] Powers, Victoria; Wörmann, Thorsten (1998). "Algoritmus pro součet čtverců skutečných polynomů" (PDF). Journal of Pure and Applied Algebra. 127 (1): 99–104. doi:10.1016 / S0022-4049 (97) 83827-3.

[6] Lasserre, Jean B. (2007). "Součet čtverců aproximace nezáporných polynomů". Recenze SIAM. 49 (4): 651–669. arXiv:matematika / 0412398. Bibcode:2007SIAMR..49..651L. doi:10.1137/070693709.

[7] Chesi, G .; Tesi, A .; Vicino, A .; Genesio, R. (1999). „O konvexifikaci některých problémů s minimální vzdáleností“. Sborník z 5. evropské kontrolní konference. Karlsruhe, Německo: IEEE. 1446–1451.

[8] Choi, M .; Lam, T .; Reznick, B. (1995). "Součty čtverců skutečných polynomů". Proceedings of Symposia in Pure Mathematics. 103–125.

[9] Chesi, G .; Garulli, A .; Tesi, A .; Vicino, A. (2003). "Robustní stabilita pro polytopické systémy prostřednictvím polynomiálně parametricky závislých Lyapunovových funkcí". Sborník 42. konference IEEE o rozhodování a kontrole. Maui, Havaj: IEEE. 4670–4675. doi:10.1109 / CDC.2003.1272307.

[10] Helton, J. William (září 2002). ""Pozitivní „Nekomutativní polynomy jsou sumy čtverců“. Annals of Mathematics. 156 (2): 675–694. doi:10.2307/3597203. JSTOR 3597203.

[11] Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25. října 2012). "Algoritmické aspekty součtů hermitovských čtverců nekomutativních polynomů". Výpočetní optimalizace a aplikace. 55 (1): 137–153. CiteSeerX 10.1.1.416.543. doi:10.1007 / s10589-012-9513-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]