Programación cuadrática

Solución de un problema de optimización con una función objetivo cuadrática

La programación cuadrática ( QP ) es el proceso de resolver ciertos problemas matemáticos de optimización que involucran funciones cuadráticas . Específicamente, se busca optimizar (minimizar o maximizar) una función cuadrática multivariable sujeta a restricciones lineales sobre las variables. La programación cuadrática es un tipo de programación no lineal .

En este contexto, "programación" se refiere a un procedimiento formal para resolver problemas matemáticos. Este uso data de la década de 1940 y no está específicamente vinculado con el concepto más reciente de "programación informática". Para evitar confusiones, algunos profesionales prefieren el término "optimización", por ejemplo, "optimización cuadrática". ^[1]

Formulación del problema

El problema de programación cuadrática con n variables y m restricciones se puede formular de la siguiente manera. ^[2] Dado:

• un vector c de valor real y n -dimensional ,
• una matriz simétrica real Q de n × n dimensiones ,
• una matriz real A de dimensión m × n , y
• un vector real m -dimensional b ,

El objetivo de la programación cuadrática es encontrar un vector x de dimensión n , que

donde x ^T denota la transpuesta vectorial de x , y la notación A x ⪯ b significa que cada entrada del vector A x es menor o igual que la entrada correspondiente del vector b (desigualdad componente por componente).

Mínimos cuadrados restringidos

Como caso especial cuando Q es simétrico positivo-definido , la función de costo se reduce a mínimos cuadrados:

donde Q = R ^T R se deduce de la descomposición de Cholesky de Q y c = − R ^T d . Por el contrario, cualquier programa de mínimos cuadrados restringido puede formularse de manera equivalente como un problema de programación cuadrática, incluso para una matriz R genérica no cuadrada .

Generalizaciones

Al minimizar una función f en el entorno de algún punto de referencia x ₀ , Q se establece en su matriz hessiana H ( f ( x ₀ )) y c se establece en su gradiente ∇ f ( x ₀ ) . Se puede plantear un problema de programación relacionado, la programación cuadrática con restricciones cuadráticas , agregando restricciones cuadráticas a las variables.

Métodos de solución

Para problemas generales se utilizan comúnmente una variedad de métodos, incluidos

• punto interior ,
• conjunto activo , ^[3]
• Lagrangiano aumentado , ^[4]
• gradiente conjugado ,
• proyección de gradiente,
• extensiones del algoritmo simplex . ^[3]

En el caso en que Q sea definida positiva , el problema es un caso especial del campo más general de la optimización convexa .

Restricciones de igualdad

La programación cuadrática es particularmente sencilla cuando Q es definida positiva y solo hay restricciones de igualdad; específicamente, el proceso de solución es lineal. Al utilizar multiplicadores de Lagrange y buscar el extremo del lagrangiano, se puede demostrar fácilmente que la solución al problema con restricciones de igualdad

${\displaystyle {\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$

${\displaystyle {\text{subject to}}\quad E\mathbf {x} =\mathbf {d} }$

viene dado por el sistema lineal

${\displaystyle {\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}$

donde λ es un conjunto de multiplicadores de Lagrange que salen de la solución junto con x .

La forma más sencilla de abordar este sistema es la solución directa (por ejemplo, la factorización LU ), que resulta muy práctica para problemas pequeños. En el caso de problemas grandes, el sistema plantea algunas dificultades inusuales, en particular que el problema nunca es positivo definido (incluso si Q lo es), lo que hace que sea potencialmente muy difícil encontrar un buen enfoque numérico, y existen muchos enfoques para elegir según el problema.

Si las restricciones no acoplan las variables demasiado estrechamente, un ataque relativamente simple consiste en cambiar las variables de modo que las restricciones se satisfagan incondicionalmente. Por ejemplo, supongamos que d = 0 (generalizar a un valor distinto de cero es sencillo). Si observamos las ecuaciones de restricción:

${\displaystyle E\mathbf {x} =0}$

introducir una nueva variable y definida por

${\displaystyle Z\mathbf {y} =\mathbf {x} }$

donde y tiene dimensión x menos el número de restricciones. Entonces

${\displaystyle EZ\mathbf {y} =\mathbf {0} }$

y si se elige Z de modo que EZ = 0, la ecuación de restricción siempre se cumplirá. Encontrar dicha Z implica encontrar el espacio nulo de E , lo cual es más o menos simple dependiendo de la estructura de E . Sustituyendo en la forma cuadrática se obtiene un problema de minimización sin restricciones:

${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\top }Q\mathbf {x} +\mathbf {c} ^{\top }\mathbf {x} \quad \implies \quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top }\mathbf {c} \right)^{\top }\mathbf {y} }$

cuya solución viene dada por:

${\displaystyle Z^{\top }QZ\mathbf {y} =-Z^{\top }\mathbf {c} }$

En determinadas condiciones de Q , la matriz reducida Z ^T QZ será definida positiva. Es posible escribir una variación del método del gradiente conjugado que evita el cálculo explícito de Z. ^[5]

Dualidad lagrangiana

El dual lagrangiano de un problema de programación cuadrática también es un problema de programación cuadrática. Para comprobarlo, centrémonos en el caso en el que c = 0 y Q es definida positiva. Escribimos la función lagrangiana como

${\displaystyle L(x,\lambda )={\tfrac {1}{2}}x^{\top }Qx+\lambda ^{\top }(Ax-b).}$

Definiendo la función dual (lagrangiana) g (λ) como , encontramos un ínfimo de L , usando una definitividad positiva de Q : ${\displaystyle g(\lambda )=\inf _{x}L(x,\lambda )}$ ${\displaystyle \nabla _{x}L(x,\lambda )=0}$

${\displaystyle x^{*}=-Q^{-1}A^{\top }\lambda .}$

Por lo tanto la función dual es

${\displaystyle g(\lambda )=-{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b,}$

y entonces el dual lagrangiano del problema de programación cuadrática es

${\displaystyle {\text{maximize}}_{\lambda \geq 0}\quad -{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b.}$

Además de la teoría de dualidad lagrangiana, existen otros emparejamientos de dualidad (por ejemplo, Wolfe , etc.).

Complejidad en tiempo de ejecución

Programación cuadrática convexa

Para Q definida positiva , cuando el problema es convexo, el método del elipsoide resuelve el problema en tiempo (débilmente) polinomial . ^[6]

Ye y Tse ^[7] presentan un algoritmo de tiempo polinomial que extiende el algoritmo de Karmarkar de la programación lineal a la programación cuadrática convexa. En un sistema con n variables y L bits de entrada, su algoritmo requiere O(L n) iteraciones, cada una de las cuales puede realizarse utilizando O(L n ³ ) operaciones aritméticas, para una complejidad total en tiempo de ejecución de O( L ² n ⁴ ).

Kapoor y Vaidya ^[8] presentan otro algoritmo, que requiere O( L * log L * n ^3,67 * log n ) operaciones aritméticas.

Programación cuadrática no convexa

Si Q es indefinido (por lo que el problema no es convexo), entonces el problema es NP-hard . ^[9] Una forma sencilla de ver esto es considerar la restricción cuadrática no convexa x _i ² = x _i . Esta restricción es equivalente a requerir que x _i esté en {0,1}, es decir, x _i es una variable entera binaria. Por lo tanto, tales restricciones se pueden usar para modelar cualquier programa entero con variables binarias, que se sabe que es NP-hard.

Además, estos problemas no convexos pueden tener varios puntos estacionarios y mínimos locales. De hecho, incluso si Q tiene solo un valor propio negativo , el problema es (fuertemente) NP-duro . ^[10]

Además, encontrar un punto KKT de un programa cuadrático no convexo es difícil para CLS. ^[11]

Programación cuadrática de números enteros mixtos

Existen algunas situaciones en las que uno o más elementos del vector x deben tomar valores enteros . Esto conduce a la formulación de un problema de programación cuadrática entera mixta (MIQP). ^[12] Las aplicaciones de MIQP incluyen los recursos hídricos ^[13] y la construcción de fondos indexados . ^[14]

Solucionadores y lenguajes de programación

Extensiones

La optimización polinomial ^[15] es un marco más general, en el que las restricciones pueden ser funciones polinomiales de cualquier grado, no solo 2.

Véase también

• Programación cuadrática secuencial
• Programación lineal
• Método de la línea crítica

Referencias

1. Wright, Stephen J. (2015), "Optimización continua (programación lineal y no lineal)", en Nicholas J. Higham; et al. (eds.), The Princeton Companion to Applied Mathematics , Princeton University Press, págs. 281–293
2. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica (2.ª ed.). Berlín, Nueva York: Springer-Verlag . p. 449. ISBN. 978-0-387-30303-1..
3. Murty, Katta G. (1988). Complementariedad lineal, programación lineal y no lineal. Serie Sigma en Matemáticas Aplicadas. Vol. 3. Berlín: Heldermann Verlag. pp. xlviii+629 pp. ISBN 978-3-88538-403-8. MR  0949214. Archivado desde el original el 1 de abril de 2010.
4. Delbos, F.; Gilbert, J.Ch. (2005). "Convergencia lineal global de un algoritmo lagrangiano aumentado para resolver problemas de optimización cuadrática convexa" (PDF) . Journal of Convex Analysis . 12 : 45–69. Archivado (PDF) desde el original el 2022-10-09.
5. Gould, Nicholas IM; Hribar, Mary E.; Nocedal, Jorge (abril de 2001). "Sobre la solución de problemas de programación cuadrática con restricciones de igualdad que surgen en la optimización". SIAM J. Sci. Comput . 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555 . doi :10.1137/S1064827598345667. 
6. Kozlov, MK; SP Tarasov; Leonid G. Khachiyan (1979). "[Solubilidad polinomial de programación cuadrática convexa]". Doklady Akademii Nauk SSSR . 248 : 1049–1051.Traducido en: Matemáticas soviéticas - Doklady . 20 : 1108–1111. {{cite journal}}: Falta o está vacío |title=( ayuda )
7. Ye, Yinyu; Tse, Edison (1989-05-01). "Una extensión del algoritmo proyectivo de Karmarkar para programación cuadrática convexa". Programación matemática . 44 (1): 157–179. doi :10.1007/BF01587086. ISSN  1436-4646. S2CID  35753865.
8. Kapoor, S; Vaidya, PM (1986-11-01). "Algoritmos rápidos para programación cuadrática convexa y flujos de múltiples productos". Actas del decimoctavo simposio anual de la ACM sobre teoría de la computación - STOC '86 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 147–159. doi :10.1145/12130.12145. ISBN 978-0-89791-193-1. Número de identificación del sujeto  18108815.
9. Sahni, S. (1974). "Problemas relacionados con la computación" (PDF) . Revista SIAM sobre computación . 3 (4): 262–279. CiteSeerX 10.1.1.145.8685 . doi :10.1137/0203021. 
10. Pardalos, Panos M.; Vavasis, Stephen A. (1991). "La programación cuadrática con un valor propio negativo es (fuertemente) NP-hard". Journal of Global Optimization . 1 (1): 15–22. doi :10.1007/bf00120662. S2CID  12602885.
11. Fearnley, John; Goldberg, Paul W.; Hollender, Alexandros; Savani, Rahul (2023). "La complejidad de calcular soluciones KKT de programas cuadráticos". arXiv : 2311.13738 [cs.CC].
12. Lazimy, Rafael (1982-12-01). "Programación cuadrática entera mixta". Programación matemática . 22 (1): 332–349. doi :10.1007/BF01581047. ISSN  1436-4646. S2CID  8456219.
13. Propato Marco; Uber James G. (1 de julio de 2004). "Diseño de sistemas de refuerzo mediante programación cuadrática de enteros mixtos". Revista de planificación y gestión de recursos hídricos . 130 (4): 348–352. doi :10.1061/(ASCE)0733-9496(2004)130:4(348).
14. Cornuéjols, Gérard; Peña, Javier; Tütüncü, Reha (2018). Métodos de optimización en finanzas (2.ª ed.). Cambridge, Reino Unido: Cambridge University Press. pp. 167–168. ISBN 9781107297340.
15. Tuy, Hoang (2016), Tuy, Hoang (ed.), "Optimización polinomial", Análisis convexo y optimización global , Springer Optimization and Its Applications, vol. 110, Cham: Springer International Publishing, págs. 435–452, doi :10.1007/978-3-319-31484-6_12, ISBN 978-3-319-31484-6, consultado el 16 de diciembre de 2023

Lectura adicional

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). El problema de complementariedad lineal . Ciencias de la computación y computación científica. Boston, MA: Academic Press, Inc. pp. xxiv+762 pp. ISBN 978-0-12-192350-1.Señor 1150683  .
• Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP2, pág.245.
• Gould, Nicholas IM; Toint, Philippe L. (2000). "Una bibliografía sobre programación cuadrática" (PDF) . Informe interno del grupo de análisis numérico RAL 2000-1.

Enlaces externos

• Una página sobre programación cuadrática
• Guía de optimización de NEOS: Programación cuadrática
• Programación cuadrática Archivado el 8 de abril de 2023 en Wayback Machine
• Programación cúbica y más allá, en Stack Exchange de Investigación de Operaciones