Optimización por suma de cuadrados

Un programa de optimización por suma de cuadrados es un problema de optimización con una función de costo lineal y un tipo particular de restricción en las variables de decisión. Estas restricciones son de la forma que cuando las variables de decisión se utilizan como coeficientes en ciertos polinomios , esos polinomios deben tener la propiedad polinomial SOS . Cuando se fija el grado máximo de los polinomios involucrados, la optimización por suma de cuadrados también se conoce como la jerarquía de relajaciones de Lasserre en programación semidefinida .

Las técnicas de optimización de suma de cuadrados se han aplicado en una variedad de áreas, incluida la teoría de control (en particular, para buscar funciones de Lyapunov polinomiales para sistemas dinámicos descritos por campos vectoriales polinomiales), las estadísticas, las finanzas y el aprendizaje automático. ^{[1] [2] [3] [4]}

Problema de optimización

Dado un vector y polinomios para , , un problema de optimización de suma de cuadrados se escribe como ${\displaystyle c\in \mathbb {R} ^{n}}$ ${\displaystyle a_{k,j}}$ ${\displaystyle k=1,\dots N_{s}}$ ${\displaystyle j=0,1,\dots ,n}$

$${\displaystyle {\begin{aligned}{\underset {u\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{T}u\\{\text{subject to}}\quad &a_{k,0}(x)+a_{k,1}(x)u_{1}+\cdots +a_{k,n}(x)u_{n}\in {\text{SOS}}\quad (k=1,\ldots ,N_{s}).\end{aligned}}}$$

Aquí, "SOS" representa la clase de polinomios de suma de cuadrados (SOS). Las cantidades son las variables de decisión. Los programas SOS se pueden convertir en programas semidefinidos (SDP) utilizando la dualidad del programa polinomial SOS y una relajación para la optimización polinomial restringida utilizando matrices semidefinidas positivas ; consulte la siguiente sección. ${\displaystyle u\in \mathbb {R} ^{n}}$

Problema dual: optimización polinómica restringida

Supongamos que tenemos un polinomio de variable , y que queremos minimizar este polinomio sobre un subconjunto . Supongamos además que las restricciones sobre el subconjunto se pueden codificar utilizando igualdades polinómicas de grado como máximo , cada una de la forma donde es un polinomio de grado como máximo . Un programa natural, aunque generalmente no convexo para este problema de optimización es el siguiente: sujeto a: ${\displaystyle n}$ ${\displaystyle p(x):\mathbb {R} ^{n}\to \mathbb {R} }$ ${\textstyle A\subseteq \mathbb {R} ^{n}}$ ${\textstyle A}$ ${\textstyle m}$ ${\displaystyle 2d}$ ${\textstyle a_{i}(x)=0}$ ${\displaystyle a_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle 2d}$ $${\displaystyle \min _{x\in \mathbb {R} ^{n}}\langle C,x^{\leq d}(x^{\leq d})^{\top }\rangle }$$

$${\displaystyle x_{\emptyset }=1,}$$donde es el vector -dimensional con una entrada para cada monomio en de grado como máximo , de modo que para cada multiconjunto , es una matriz de coeficientes del polinomio que queremos minimizar, y es una matriz de coeficientes del polinomio que codifica la restricción -ésima en el subconjunto . El índice constante fijo adicional en nuestro espacio de búsqueda, , se agrega para la conveniencia de escribir los polinomios y en una representación matricial. ${\textstyle x^{\leq d}}$ ${\displaystyle n^{O(d)}}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle S\subset [n],|S|\leq d,}$ ${\textstyle x_{S}=\prod _{i\in S}x_{i}}$ ${\textstyle C}$ ${\textstyle p(x)}$ ${\textstyle A_{i}}$ ${\textstyle a_{i}(x)}$ ${\displaystyle i}$ ${\displaystyle A\subset \mathbb {R} ^{n}}$ ${\displaystyle x_{\emptyset }=1}$ ${\textstyle p(x)}$ ${\textstyle a_{i}(x)}$

Este programa es generalmente no convexo, porque las restricciones ( 1 ) no son convexas. Una posible relajación convexa para este problema de minimización utiliza programación semidefinida para reemplazar la matriz de rango uno de variables con una matriz semidefinida positiva : indexamos cada monomio de tamaño como máximo por un multiconjunto de como máximo índices, . Para cada uno de esos monomios, creamos una variable en el programa y organizamos las variables para formar la matriz , donde es el conjunto de matrices reales cuyas filas y columnas se identifican con multiconjuntos de elementos de de tamaño como máximo . Luego escribimos el siguiente programa semidefinido en las variables : sujeto a: ${\displaystyle x^{\leq d}(x^{\leq d})^{\top }}$ ${\displaystyle X}$ ${\displaystyle 2d}$ ${\displaystyle S}$ ${\displaystyle 2d}$ ${\displaystyle S\subset [n],|S|\leq 2d}$ ${\displaystyle X_{S}}$ ${\displaystyle X_{S}}$ ${\textstyle X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}$ ${\displaystyle \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle X_{S}}$ $${\displaystyle \min _{X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}\langle C,X\rangle }$$ $${\displaystyle \langle A_{i},X\rangle =0\qquad \forall \ i\in [m],Q}$$ $${\displaystyle X_{\emptyset }=1,}$$ $${\displaystyle X_{U\cup V}=X_{S\cup T}\qquad \forall \ U,V,S,T\subseteq [n],|U|,|V|,|S|,|T|\leq d,{\text{ and}}\ U\cup V=S\cup T,}$$ $${\displaystyle X\succeq 0,}$$

donde nuevamente es la matriz de coeficientes del polinomio que queremos minimizar, y es la matriz de coeficientes del polinomio que codifica la -ésima restricción en el subconjunto . ${\textstyle C}$ ${\textstyle p(x)}$ ${\textstyle A_{i}}$ ${\textstyle a_{i}(x)}$ ${\displaystyle i}$ ${\displaystyle A\subset \mathbb {R} ^{n}}$

La tercera restricción asegura que el valor de un monomio que aparece varias veces dentro de la matriz sea igual en toda la matriz, y se suma para respetar las simetrías presentes en la forma cuadrática . ${\displaystyle X}$ ${\displaystyle x^{\leq d}(x^{\leq d})^{\top }}$

Dualidad

Se puede tomar el dual del programa semidefinido anterior y obtener el siguiente programa: sujeto a: $${\displaystyle \max _{y\in \mathbb {R} ^{m'}}y_{0},}$$ $${\displaystyle C-y_{0}e_{\emptyset }-\sum _{i\in [m]}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\succeq 0.}$$

Tenemos una variable correspondiente a la restricción (donde es la matriz con todas las entradas cero excepto la entrada indexada por ), una variable real para cada restricción polinómica y para cada grupo de multiconjuntos , tenemos una variable dual para la restricción de simetría . La restricción de semidefinición positiva asegura que es una suma de cuadrados de polinomios sobre : mediante una caracterización de matrices semidefinidas positivas, para cualquier matriz semidefinida positiva , podemos escribir para vectores . Por lo tanto, para cualquier , ${\displaystyle y_{0}}$ ${\displaystyle \langle e_{\emptyset },X\rangle =1}$ ${\displaystyle e_{\emptyset }}$ ${\displaystyle (\varnothing ,\varnothing )}$ ${\displaystyle y_{i}}$ ${\displaystyle \langle X,A_{i}\rangle =0\quad s.t.i\in [m],}$ ${\displaystyle S,T,U,V\subset [n],|S|,|T|,|U|,|V|\leq d,S\cup T=U\cup V}$ ${\displaystyle y_{S,T,U,V}}$ ${\displaystyle \langle X,e_{S,T}-e_{U,V}\rangle =0}$ ${\displaystyle p(x)-y_{0}}$ ${\displaystyle A\subset \mathbb {R} ^{n}}$ ${\textstyle Q\in \mathbb {R} ^{m\times m}}$ ${\textstyle Q=\sum _{i\in [m]}f_{i}f_{i}^{\top }}$ ${\textstyle f_{i}\in \mathbb {R} ^{m}}$ ${\textstyle x\in A\subset \mathbb {R} ^{n}}$ $${\displaystyle {\begin{aligned}p(x)-y_{0}&=p(x)-y_{0}-\sum _{i\in [m']}y_{i}a_{i}(x)\qquad {\text{since }}x\in A\\&=(x^{\leq d})^{\top }\left(C-y_{0}e_{\emptyset }-\sum _{i\in [m']}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\right)x^{\leq d}\qquad {\text{by symmetry}}\\&=(x^{\leq d})^{\top }\left(\sum _{i}f_{i}f_{i}^{\top }\right)x^{\leq d}\\&=\sum _{i}\langle x^{\leq d},f_{i}\rangle ^{2}\\&=\sum _{i}f_{i}(x)^{2},\end{aligned}}}$$

donde hemos identificado los vectores con los coeficientes de un polinomio de grado como máximo . Esto da una prueba de suma de cuadrados de que el valor sobre . ${\textstyle f_{i}}$ ${\displaystyle d}$ ${\textstyle p(x)\geq y_{0}}$ ${\displaystyle A\subset \mathbb {R} ^{n}}$

Lo anterior también puede extenderse a regiones definidas por desigualdades polinómicas. ${\displaystyle A\subset \mathbb {R} ^{n}}$

Jerarquía de suma de cuadrados

La jerarquía de suma de cuadrados (jerarquía SOS), también conocida como jerarquía de Lasserre, es una jerarquía de relajaciones convexas de potencia creciente y costo computacional creciente. Para cada número natural, la relajación convexa correspondiente se conoce como el ésimo nivel o la -ésima ronda de la jerarquía SOS. La st ronda, cuando , corresponde a un programa semidefinido básico , o a una optimización de suma de cuadrados sobre polinomios de grado como máximo . Para ampliar el programa convexo básico en el st nivel de la jerarquía al -ésimo nivel, se agregan variables y restricciones adicionales al programa para que el programa considere polinomios de grado como máximo . ${\textstyle d\in \mathbb {N} }$ ${\textstyle d}$ ${\textstyle d}$ ${\textstyle 1}$ ${\textstyle d=1}$ ${\displaystyle 2}$ ${\textstyle 1}$ ${\textstyle d}$ ${\displaystyle 2d}$

La jerarquía SOS deriva su nombre del hecho de que el valor de la función objetivo en el nivel -ésimo está acotado con una prueba de suma de cuadrados que utiliza polinomios de grado máximo a través del dual (ver "Dualidad" más arriba). En consecuencia, cualquier prueba de suma de cuadrados que utilice polinomios de grado máximo puede utilizarse para acotar el valor objetivo, lo que permite demostrar garantías sobre la rigidez de la relajación. ${\textstyle d}$ ${\textstyle 2d}$ ${\textstyle 2d}$

Junto con un teorema de Berg, esto implica además que, dadas suficientes rondas, la relajación se vuelve arbitrariamente estricta en cualquier intervalo fijo. El resultado de Berg ^{[5] [6]} establece que cada polinomio real no negativo dentro de un intervalo acotado puede aproximarse con precisión en ese intervalo con una suma de cuadrados de polinomios reales de grado suficientemente alto y, por lo tanto, si es el valor objetivo del polinomio como función del punto , si la desigualdad se cumple para todos en la región de interés, entonces debe haber una prueba de suma de cuadrados de este hecho. Al elegir que sea el mínimo de la función objetivo sobre la región factible, tenemos el resultado. ${\textstyle \varepsilon }$ ${\textstyle OBJ(x)}$ ${\textstyle x}$ ${\textstyle c+\varepsilon -OBJ(x)\geq 0}$ ${\textstyle x}$ ${\textstyle c}$

Costo computacional

Al optimizar sobre una función en variables, el nivel -ésimo de la jerarquía se puede escribir como un programa semidefinido sobre variables y se puede resolver en el tiempo utilizando el método del elipsoide . ${\textstyle n}$ ${\textstyle d}$ ${\textstyle n^{O(d)}}$ ${\textstyle n^{O(d)}}$

Antecedentes de la suma de cuadrados

Un polinomio es una suma de cuadrados ( SOS ) si existen polinomios tales que . Por ejemplo, es una suma de cuadrados ya que donde Nótese que si es una suma de cuadrados entonces para todos . Hay descripciones detalladas de SOS de polinomios disponibles. ^{[7] [8] [9]} ${\displaystyle p}$ ${\displaystyle \{f_{i}\}_{i=1}^{m}}$ ${\textstyle p=\sum _{i=1}^{m}f_{i}^{2}}$ $${\displaystyle p=x^{2}-4xy+7y^{2}}$$ $${\displaystyle p=f_{1}^{2}+f_{2}^{2}}$$ $${\displaystyle f_{1}=(x-2y){\text{ and }}f_{2}={\sqrt {3}}y.}$$ ${\displaystyle p}$ ${\displaystyle p(x)\geq 0}$ ${\displaystyle x\in \mathbb {R} ^{n}}$

Las formas cuadráticas se pueden expresar como donde es una matriz simétrica. De manera similar, los polinomios de grado ≤ 2 d se pueden expresar como donde el vector contiene todos los monomios de grado . Esto se conoce como la forma de matriz de Gram . Un hecho importante es que es SOS si y solo si existe una matriz simétrica y semidefinida positiva tal que . Esto proporciona una conexión entre los polinomios SOS y las matrices semidefinidas positivas. ${\displaystyle p(x)=x^{T}Qx}$ ${\displaystyle Q}$ $${\displaystyle p(x)=z(x)^{\mathsf {T}}Qz(x),}$$ ${\displaystyle z}$ ${\displaystyle \leq d}$ ${\displaystyle p}$ ${\displaystyle Q}$ ${\displaystyle p(x)=z(x)^{\mathsf {T}}Qz(x)}$

Herramientas de software

• SOSTOOLS, con licencia GNU GPL . La guía de referencia está disponible en arXiv:1310.4716 [math.OC], y una presentación sobre sus componentes internos está disponible aquí.
• CDCS-sos, un paquete de CDCS, un solucionador de método lagrangiano aumentado , para tratar programas SOS a gran escala.
• La extensión SumOfSquares de JuMP para Julia.
• TSSOS para Julia, una herramienta de optimización polinomial basada en las jerarquías de momentos SOS adaptadas a la escasez.
• Para el problema dual de optimización polinomial restringida, GloptiPoly para MATLAB/Octave, Ncpol2sdpa para Python y MomentOpt para Julia.

Referencias

1. Suma de cuadrados: teoría y aplicaciones: curso breve de AMS, Suma de cuadrados: teoría y aplicaciones, 14 y 15 de enero de 2019, Baltimore, Maryland. Parrilo, Pablo A.; Thomas, Rekha R. Providence, Rhode Island: American Mathematical Society. 2020. ISBN 978-1-4704-5025-0.OCLC 1157604983  .{{cite book}}: CS1 maint: others (link)
2. Tan, W., Packard, A., 2004. "Búsqueda de funciones de control de Lyapunov mediante programación de sumas de cuadrados". En: Allerton Conf. on Comm., Control and Computing . págs. 210–219.
3. Tan, W., Topcu, U., Seiler, P., Balas, G., Packard, A., 2008. Alcance asistido por simulación y análisis de ganancia local para sistemas dinámicos no lineales. En: Proc. de la Conferencia IEEE sobre Decisión y Control. págs. 4097–4102.
4. A. Chakraborty, P. Seiler y G. Balas, "Susceptibilidad de los controladores de vuelo del F/A-18 al modo de caída de hojas: análisis no lineal", AIAA Journal of Guidance, Control, and Dynamics, vol. 34 núm. 1 (2011), págs. 73–85.
5. Berg, Christian (1987). Landau, Henry J. (ed.). "El problema del momento multidimensional y los semigrupos". Actas de simposios sobre matemáticas aplicadas . 37 : 110–124. doi :10.1090/psapm/037/921086. ISBN . 9780821801147.
6. Lasserre, J. (1 de enero de 2007). "Una aproximación de suma de cuadrados de polinomios no negativos". SIAM Review . 49 (4): 651–669. arXiv : math/0412398 . doi :10.1137/070693709. ISSN  0036-1445.
7. Parrilo, P., (2000) Programas semidefinidos estructurados y métodos de geometría semialgebraica en robustez y optimización . Tesis doctoral, California Institute of Technology.
8. Parrilo, P. (2003) "Relajaciones de programación semidefinida para problemas semialgebraicos". Mathematical Programming Ser. B 96 (2), 293–320.
9. Lasserre, J. (2001) "Optimización global con polinomios y el problema de los momentos". SIAM Journal on Optimization , 11 (3), 796{817.