programación cuadrática

Resolver 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 de optimización matemática que involucran funciones cuadráticas . Específicamente, se busca optimizar (minimizar o maximizar) una función cuadrática multivariada sujeta a restricciones lineales sobre las variables. La programación cuadrática es un tipo de programación no lineal .

"Programación" en este contexto 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 a la noción 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 n dimensiones y valor real ,
• una matriz simétrica real n × n -dimensional Q ,
• una matriz real A m × n -dimensional , y
• un vector real m -dimensional b ,

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

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

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 deriva de la descomposición de Cholesky de Q y c = − R ^T d . Por el contrario, cualquier programa de mínimos cuadrados restringidos puede enmarcarse 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 la vecindad de algún punto de referencia x ₀ , Q se establece en su matriz de Hesse H ( f ( x ₀ )) y c se establece en su gradiente ∇ f ( x ₀ ) . Un problema de programación relacionado, la programación cuadrática con restricciones cuadráticas , se puede plantear agregando restricciones cuadráticas a las variables.

Métodos de solución

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

• 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 definido positivo , el problema es un caso especial del campo más general de optimización convexa .

Restricciones de igualdad

La programación cuadrática es particularmente simple cuando Q es definida positiva y solo existen restricciones de igualdad; específicamente, el proceso de solución es lineal. Utilizando multiplicadores de Lagrange y buscando el extremo del lagrangiano, se puede demostrar fácilmente que la solución al problema de igualdad restringida

${\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 a x .

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

Si las restricciones no acoplan las variables demasiado estrechamente, un ataque relativamente simple es cambiar las variables para que las restricciones se cumplan incondicionalmente. Por ejemplo, supongamos que d = 0 (generalizar a un valor distinto de cero es sencillo). Mirando 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 de 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 tal Z implica encontrar el espacio nulo de E , que es más o menos simple dependiendo de la estructura de E. Sustituir en forma cuadrática da 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} }$

Bajo ciertas condiciones en Q , la matriz reducida Z ^T QZ será definida positiva. Es posible escribir una variación del método del gradiente conjugado que evite 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 ver esto centrémonos en el caso donde c = 0 y Q es definido positivo. 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 mínimo de L , usando una definición 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 lagrangiana de la dualidad, existen otros pares de dualidades (por ejemplo, Wolfe , etc.).

Complejidad del 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 desde la programación lineal hasta 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 se puede realizar usando O(L n ³ ) operaciones aritméticas, para una complejidad de tiempo de ejecución total 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-difícil . ^[9] Una forma sencilla de ver esto es considerar la restricción cuadrática no convexa x _i ² = x _i . Esta restricción equivale a requerir que x _i esté en {0,1}, es decir, x _i sea 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-duro.

Además, estos problemas no convexos pueden tener varios puntos estacionarios y mínimos locales. De hecho, incluso si Q tiene sólo un valor propio negativo , el problema es (fuertemente) NP-difícil . ^[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 enteros mixtos

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

Solvers y lenguajes de scripting (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.

Ver también

• Programación cuadrática secuencial
• Programación lineal
• Método de 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 . pag. 449.ISBN _ 978-0-387-30303-1..
3. Murty, Katta G. (1988). Complementariedad lineal, programación lineal y no lineal. Serie Sigma en Matemática Aplicada. vol. 3. Berlín: Heldermann Verlag. págs. xlviii+629 págs. ISBN 978-3-88538-403-8. SEÑOR  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) . Revista de análisis convexo . 12 : 45–69. Archivado (PDF) desde el original el 9 de octubre de 2022.
5. Gould, Nicolás IM; Hribar, María E.; Nocedal, Jorge (abril de 2001). "Sobre la solución de los problemas de programación cuadrática restringida por la igualdad que surgen en la optimización". SIAM J. Ciencias. Computación . 23 (4): 1376-1395. CiteSeerX 10.1.1.129.7555 . doi :10.1137/S1064827598345667. 
6. Kozlov, MK; SP Tarasov; Leonid G. Khachiyan (1979). "[Solubilidad polinómica de la 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. Sí, Yinyu; Tse, Edison (1 de mayo de 1989). "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 (1 de noviembre de 1986). "Algoritmos rápidos para programación cuadrática convexa y flujos de múltiples productos". Actas del decimoctavo simposio anual de ACM sobre teoría de la informática - STOC '86 . Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 147-159. doi :10.1145/12130.12145. ISBN 978-0-89791-193-1. S2CID  18108815.
9. Sahni, S. (1974). "Problemas relacionados computacionalmente" (PDF) . Revista SIAM de 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-dura". Revista de optimización global . 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 (1 de diciembre de 1982). "Programación cuadrática de enteros mixtos". 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 sistema 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. págs. 167-168. ISBN 9781107297340.
15. Tuy, Hoang (2016), Tuy, Hoang (ed.), "Optimización polinomial", Análisis convexo y optimización global , Optimización de Springer y sus aplicaciones, Cham: Springer International Publishing, vol. 110, págs. 435–452, doi :10.1007/978-3-319-31484-6_12, ISBN 978-3-319-31484-6, recuperado el 16 de diciembre de 2023

Otras lecturas

• Cottle, Richard W.; Pang, Jong-Shi; Piedra, Richard E. (1992). El problema de la complementariedad lineal . Informática y Computación Científica. Boston, MA: Academic Press, Inc. págs. xxiv+762 págs. 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 integridad NP . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP2, pág.245.
• Gould, Nicolás IM; Toint, Philippe L. (2000). "Una bibliografía de 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
• Programación cúbica y más allá, en el intercambio de pilas de investigación de operaciones