En matemáticas , una forma (es decir, un polinomio homogéneo) h ( x ) de grado 2 m en el vector real n -dimensional x es suma de cuadrados de formas (SOS) si y sólo si existen formas de grado m tales que![{\displaystyle g_{1}(x),\ldots,g_{k}(x)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Toda forma que es SOS es también un polinomio positivo , y aunque lo contrario no siempre es cierto, Hilbert demostró que para n = 2, 2 m = 2, o n = 3 y 2 m = 4 una forma es SOS si y sólo si es positivo. [1] Lo mismo también es válido para el problema analógico en formas simétricas positivas . [2] [3]
Aunque no todas las formas pueden representarse como SOS, se han encontrado condiciones suficientes y explícitas para que una forma sea SOS. [4] [5] Además, cada forma real no negativa se puede aproximar tanto como se desee (en la norma - de su vector de coeficientes) mediante una secuencia de formas que son SOS. [6]![{\ Displaystyle l_ {1}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Representación matricial cuadrada (SMR)
Establecer si una forma h ( x ) es SOS equivale a resolver un problema de optimización convexa . De hecho, cualquier h ( x ) se puede escribir como
![{\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
mxlos monomiosmxtranspuestaHmatriz simétrica![{\displaystyle x^{\{m\}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
espacio lineal![{\displaystyle L(\alpha )}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La dimensión del vector está dada por![{\displaystyle x^{\{m\}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \sigma (n,m)={\binom {n+m-1}{m}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \alpha }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m ).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Entonces, h ( x ) es SOS si y sólo si existe un vector tal que![{\displaystyle \alpha }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle H+L(\alpha )\geq 0,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
matrizsemidefinida positivade desigualdad matricial lineal[7][8]![{\displaystyle H+L(\alpha )}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ejemplos
- Considere la forma de grado 4 en dos variables . Tenemos
![{\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{ 2}\end{pmatrix}}\!,~H+L(\alpha )={\begin{pmatrix}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\ -\alpha _{1}&0&1\end{pmatrix}}\!.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Puesto que existe α tal que , es decir , se sigue que h ( x ) es SOS.![{\displaystyle H+L(\alpha )\geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \alpha =1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Considere la forma de grado 4 en tres variables . Tenemos
![{\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}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{ 3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{pmatrix}},~H+L(\alpha )={\ comenzar{pmatrix}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{pmatrix}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Dado que para , se deduce que h ( x ) es SOS.![{\displaystyle H+L(\alpha )\geq 0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \alpha =(1,18,-0,43,0,73,1,13,-0,37,0,57)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Generalizaciones
Matriz SOS
Una forma matricial F ( x ) (es decir, una matriz cuyas entradas son formas) de dimensión r y grado 2 m en el vector real n -dimensional x es SOS si y sólo si existen formas matriciales de grado m tales que![{\displaystyle G_{1}(x),\ldots,G_{k}(x)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F(x)=\sum _ {i=1}^{k}G_{i}(x)'G_{i}(x).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Matriz SMR
Establecer si una forma matricial F ( x ) es SOS equivale a resolver un problema de optimización convexa. De hecho, de manera similar al caso escalar, cualquier F ( x ) se puede escribir según el SMR como
![{\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\ {m\}}\otimes I_{r}\right)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
productoH![{\displaystyle \otimes}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\ bien)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle L(\alpha )}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{ \{m\}}\otimes I_{r}\right)=0\right\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La dimensión del vector está dada por![{\displaystyle \alpha }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \omega (n,2m,r)={\frac {1}{2}}r\left(\sigma (n,m)\left(r\sigma (n,m)+1\right) -(r+1)\sigma (n,2m)\right).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Entonces, F ( x ) es SOS si y sólo si existe un vector tal que se cumpla el siguiente LMI:![{\displaystyle \alpha }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle H+L(\alpha )\geq 0.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
La expresión se introdujo en [9] para establecer si una forma matricial es SOS a través de un LMI.![{\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\ {m\}}\otimes I_{r}\right)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
SOS polinomio no conmutativo
Considere el álgebra libre R ⟨ X ⟩ generada por las n letras no conmutantes X = ( X 1 , ..., X n ) y equipada con la involución T , tal que T fija R y X 1 , ..., X n y invierte palabras formadas por X 1 , ..., X n . Por analogía con el caso conmutativo, los polinomios simétricos no conmutativos f son los polinomios no conmutativos de la forma f = f T . Cuando cualquier matriz real de cualquier dimensión r × r se evalúa en un polinomio simétrico no conmutativo f da como resultado una matriz semidefinida positiva , se dice que f es matriz positiva.
Un polinomio no conmutativo es SOS si existen polinomios no conmutativos tales que![{\displaystyle h_{1},\ldots,h_{k}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f(X)=\sum _ {i=1}^{k}h_{i}(X)^{T}h_{i}(X).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Sorprendentemente, en el escenario no conmutativo un polinomio no conmutativo es SOS si y sólo si es de matriz positiva. [10] Además, existen algoritmos disponibles para descomponer polinomios matriciales positivos en suma de cuadrados de polinomios no conmutativos. [11]
Referencias
- ^ Hilbert, David (septiembre de 1888). "Ueber die Darstellung definiter Formen als Summe von Formenquadraten". Annalen Matemáticas . 32 (3): 342–350. doi :10.1007/bf01443605. S2CID 177804714.
- ^ Choi, médico; Lam, TY (1977). "Una vieja pregunta de Hilbert". Artículos de Queen en Matemática Pura y Aplicada . 46 : 385–405.
- ^ Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (mayo de 2016). "Sobre el análogo de Choi-Lam del teorema de Hilbert de 1888 para formas simétricas". Álgebra lineal y sus aplicaciones . 496 : 114-120. arXiv : 1505.08145 . doi :10.1016/j.laa.2016.01.024. S2CID 17579200.
- ^ Lasserre, Jean B. (2007). "Condiciones suficientes para que un polinomio real sea suma de cuadrados". Archiv der Mathematik . 89 (5): 390–398. arXiv : matemáticas/0612358 . CiteSeerX 10.1.1.240.4438 . doi :10.1007/s00013-007-2251-y. S2CID 9319455.
- ^ Poderes, Victoria ; Wörmann, Thorsten (1998). "Un algoritmo para sumas de cuadrados de polinomios reales" (PDF) . Revista de Álgebra Pura y Aplicada . 127 (1): 99-104. doi : 10.1016/S0022-4049(97)83827-3 .
- ^ Lasserre, Jean B. (2007). "Una aproximación de suma de cuadrados de polinomios no negativos". Revisión SIAM . 49 (4): 651–669. arXiv : matemáticas/0412398 . Código Bib : 2007SIAMR..49..651L. doi : 10.1137/070693709.
- ^ Chesi, G.; Tesi, A.; Vicino, A.; Genesio, R. (1999). "Sobre la convexificación de algunos problemas de distancia mínima". Actas de la V Conferencia Europea de Control . Karlsruhe, Alemania: IEEE. págs. 1446-1451.
- ^ Choi, M.; Lam, T.; Reznick, B. (1995). "Sumas de cuadrados de polinomios reales". Actas de simposios de matemática pura . págs. 103-125.
- ^ Chesi, G.; Garulli, A.; Tesi, A.; Vicino, A. (2003). "Robusta estabilidad para sistemas politópicos mediante funciones de Lyapunov polinomialmente dependientes de parámetros". Actas de la 42ª Conferencia IEEE sobre Decisión y Control . Maui, Hawái: IEEE. págs. 4670–4675. doi :10.1109/CDC.2003.1272307.
- ^ Helton, J. William (septiembre de 2002). "Los polinomios "positivos" no conmutativos son sumas de cuadrados ". The Annals of Mathematics . 156 (2): 675–694. doi : 10.2307/3597203. JSTOR 3597203.
- ^ Burgdorf, Sabina; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25 de octubre de 2012). "Aspectos algorítmicos de sumas de cuadrados hermitianos de polinomios no conmutativos". Optimización Computacional y Aplicaciones . 55 (1): 137-153. CiteSeerX 10.1.1.416.543 . doi :10.1007/s10589-012-9513-8. S2CID 254416733.
Ver también