Programa cuadrático con restricciones cuadráticas

En optimización matemática , un programa cuadrático con restricciones cuadráticas ( QCQP ) es un problema de optimización en el que tanto la función objetivo como las restricciones son funciones cuadráticas . Tiene la forma

${\displaystyle {\begin{aligned}&{\text{minimizar}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{0}x+q_{0}^{\mathrm {T} }x\\&{\text{sujeto a}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{i}x+q_{i}^{\mathrm {T} }x+r_{i}\leq 0\quad {\text{para }}i=1,\dots ,m,\\&&&Ax=b,\end{aligned}}}$

donde P ₀ , ..., P _m son matrices de n por n y x ∈ R ⁿ es la variable de optimización.

Si P ₀ , ..., P _m son todas semidefinidas positivas , entonces el problema es convexo . Si estas matrices no son ni semidefinidas positivas ni negativas, el problema es no convexo. Si P ₁ , ... , P _m son todas cero, entonces las restricciones son de hecho lineales y el problema es un programa cuadrático .

Un problema QCQP convexo se puede resolver eficientemente mediante un método de punto interior (en tiempo polinomial), que generalmente requiere entre 30 y 60 iteraciones para converger. Resolver el caso general no convexo es un problema NP-difícil .

Para comprobarlo, observe que las restricciones x ₁ ( x ₁ − 1) ≤ 0 y x ₁ ( x ₁ − 1) ≥ 0 son equivalentes a la restricción x ₁ ( x ₁ − 1) = 0, que a su vez es equivalente a la restricción x ₁ ∈ {0, 1}. Por lo tanto, cualquier programa entero 0-1 (en el que todas las variables deben ser 0 o 1) puede formularse como un programa cuadrático con restricciones cuadráticas. Dado que la programación entera 0-1 es NP-difícil en general, la programación cuadrática con restricciones cuadráticas (QCQP) también lo es.

Sin embargo, incluso para un problema QCQP no convexo, generalmente se puede encontrar una solución local con una variante no convexa del método de punto interior. En algunos casos (como al resolver problemas de programación no lineal con un enfoque QCQP secuencial), estas soluciones locales son suficientemente buenas como para ser aceptadas.

Existen dos relajaciones principales del problema QCQP: mediante programación semidefinida (SDP) y mediante la técnica de reformulación-linealización (RLT). Para algunas clases de problemas QCQP (precisamente, problemas QCQP con elementos diagonales nulos en las matrices de datos), se dispone de relajaciones de programación de cono de segundo orden (SOCP) y programación lineal (LP) que proporcionan el mismo valor objetivo que la relajación SDP. ^{[ 1 ]}

Los problemas QCQP no convexos con elementos fuera de la diagonal no positivos pueden resolverse exactamente mediante las relajaciones SDP o SOCP, ^{[ 2 ]} y existen condiciones suficientes verificables en tiempo polinomial para que las relajaciones SDP de problemas QCQP generales sean exactas. ^{[ 3 ]} Además, se demostró que una clase de problemas QCQP generales aleatorios tiene relajaciones semidefinidas exactas con alta probabilidad siempre que el número de restricciones no crezca más rápido que un polinomio fijo en el número de variables. ^{[ 3 ]}

Cuando P ₀ , ..., P _m son todas matrices definidas positivas , el problema es convexo y se puede resolver fácilmente utilizando métodos de punto interior , como se hace con la programación semidefinida .

• El problema de corte máximo es un problema de teoría de grafos, que es NP-difícil. Dado un grafo, el problema consiste en dividir los vértices en dos conjuntos, de manera que la mayor cantidad posible de aristas conecten un conjunto con el otro. El problema de corte máximo se puede formular como un problema QCQP, y la relajación SDP del dual proporciona buenas cotas inferiores.
• QCQP se utiliza para ajustar con precisión la configuración de la máquina en aplicaciones de alta precisión, como la fotolitografía .

• Boyd, Stephen; Lieven Vandenberghe (2004). Optimización convexa . Cambridge: Cambridge University Press. ISBN 978-0-521-83378-3.

• Albers CJ, Critchley F., Gower, JC (2011). "Problemas de minimización cuadrática en estadística" (PDF) . Journal of Multivariate Analysis . 102 (3): 698– 713. doi : 10.1016/j.jmva.2009.12.018 . hdl : 11370/6295bde7-4de1-48c2-a30b-055eff924f3e .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

• Guía de optimización de NEOS: Programación cuadrática con restricciones cuadráticas. Archivado el 2 de abril de 2013 en Wayback Machine.