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 multivariante 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á relacionado específicamente con la noción más reciente de "programación de computadoras". 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 verdadero -valued, n -dimensional vector c ,
- una matriz Q simétrica real n × n- dimensional ,
- una matriz real A m × n- dimensional , y
- un vector real b dimensional m ,
El objetivo de la programación cuadrática es encontrar un vector x n- dimensional , que
minimizar sujeto a
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 a la entrada correspondiente del vector b (desigualdad de componentes).
Mínimos cuadrados
Como caso especial cuando Q es simétrico positivo-definido , la función de costo se reduce a mínimos cuadrados:
minimizar sujeto a
donde Q = R T R se desprende de la descomposición de Cholesky de Q y c = - R T d . A la inversa, cualquier programa de mínimos cuadrados restringidos de este tipo se puede enmarcar de manera equivalente como un QP, incluso para una matriz R genérica no cuadrada .
Generalizaciones
Cuando se minimiza una función f en la vecindad de algún punto de referencia x 0 , Q se establece en su matriz hessiana H ( f ( x 0 )) y c se establece en su gradiente ∇ f ( x 0 ) . Se puede plantear un problema de programación relacionado, la programación cuadrática restringida cuadráticamente , agregando restricciones cuadráticas a las variables.
Métodos de solución
Para problemas generales, se utilizan comúnmente una variedad de métodos, que incluyen
- punto interior ,
- conjunto activo , [3]
- Lagrangiano aumentado , [4]
- gradiente conjugado ,
- proyección de gradiente ,
- extensiones del algoritmo simplex . [3]
En el caso en el que Q es definida positiva , 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 hay restricciones de igualdad; específicamente, el proceso de solución es lineal. Usando multiplicadores de Lagrange y buscando el extremo del Lagrange, se puede mostrar fácilmente que la solución al problema de igualdad restringida
viene dado por el sistema lineal
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, factorización LU ), que para problemas pequeños es muy práctica. Para problemas grandes, el sistema presenta 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 hay muchos enfoques para elegir dependiendo de la problema. [5]
Si las restricciones no acoplan las variables con demasiada fuerza, un ataque relativamente simple es cambiar las variables para que las restricciones se satisfagan incondicionalmente. Por ejemplo, suponga que d = 0 (generalizar a un valor distinto de cero es sencillo). Mirando las ecuaciones de restricción:
introducir una nueva variable y definida por
donde y tiene una dimensión de x menos el número de restricciones. Luego
y si se elige Z de manera que EZ = 0, la ecuación de restricción siempre se cumplirá. Encontrar tales Z conlleva encontrar el espacio nulo de E , que es más o menos sencilla en función de la estructura de E . La sustitución en la forma cuadrática da un problema de minimización sin restricciones:
cuya solución viene dada por:
Bajo ciertas condiciones en Q , la matriz reducida Z T QZ será definida positiva. Es posible escribir una variación en el método del gradiente conjugado que evita el cálculo explícito de Z . [6]
Dualidad lagrangiana
El dual lagrangiano de un QP es también un QP. Para ver esto, centrémonos en el caso donde c = 0 y Q es positivo definido. Escribimos la función lagrangiana como
Definiendo la función dual (lagrangiana) g (λ) como, encontramos un mínimo de L , usandoy definición positiva de Q :
Por tanto, la función dual es
y entonces el dual lagrangiano del QP es
Además de la teoría de la dualidad de Lagrange, existen otros emparejamientos de dualidad (por ejemplo , Wolfe , etc.).
Complejidad
Para Q definida positiva , el método elipsoide resuelve el problema en tiempo polinomial (débilmente) . [7] Si, por otro lado, Q es indefinido, entonces el problema es NP-difícil . [8] De hecho, incluso si Q tiene solo un valor propio negativo , el problema es (fuertemente) NP-difícil . [9]
Restricciones de enteros
Hay algunas situaciones en las que uno o más elementos del vector x necesitarán tomar valores enteros . Esto conduce a la formulación de un problema de programación cuadrática de enteros mixtos (MIQP). [10] Las aplicaciones del MIQP incluyen los recursos hídricos [11] y la construcción de fondos indexados . [12]
Solucionadores y lenguajes de scripting (programación)
Nombre | Breve información |
---|---|
OBJETIVOS | Un sistema de software para modelar y resolver problemas de tipo optimización y programación. |
ALGLIB | Biblioteca numérica con licencia dual (GPL / propietaria) (C ++, .NET). |
AMPL | Un lenguaje de modelado popular para la optimización matemática a gran escala. |
APMonitor | Suite de modelado y optimización para sistemas LP , QP, NLP , MILP , MINLP y DAE en MATLAB y Python. |
Artelys Knitro | Un paquete integrado para la optimización no lineal |
CGAL | Un paquete de geometría computacional de código abierto que incluye un solucionador de programación cuadrática. |
CPLEX | Solucionador popular con una API (C, C ++, Java, .Net, Python, Matlab y R). Gratis para académicos. |
Función Excel Solver | Un solucionador no lineal ajustado a hojas de cálculo en las que las evaluaciones de funciones se basan en las celdas de nuevo cálculo. Versión básica disponible como complemento estándar para Excel. |
JUEGOS | Un sistema de modelado de alto nivel para la optimización matemática |
GNU Octave | Un lenguaje de programación gratuito (su licencia es GPLv 3) de propósito general y orientado a matrices para computación numérica, similar a MATLAB. La programación cuadrática en GNU Octave está disponible a través de su comando qp |
Gurobi | Solucionador con algoritmos paralelos para programas lineales a gran escala, programas cuadráticos y programas de enteros mixtos. Gratis para uso académico. |
IMSL | Un conjunto de funciones matemáticas y estadísticas que los programadores pueden integrar en sus aplicaciones de software. |
IPOPT | IPOPT (Interior Point OPTimizer) es un paquete de software para optimización no lineal a gran escala. |
Arce | Lenguaje de programación de propósito general para matemáticas. La resolución de un problema cuadrático en Maple se logra mediante su comando QPSolve . |
MATLAB | Un lenguaje de programación de propósito general y orientado a matrices para computación numérica. La programación cuadrática en MATLAB requiere Optimization Toolbox además del producto básico de MATLAB |
Mathematica | Un lenguaje de programación de propósito general para matemáticas, que incluye capacidades numéricas y simbólicas. |
MOSEK | Un solucionador de optimización a gran escala con API para varios lenguajes (C ++, Java, .Net, Matlab y Python). |
Biblioteca numérica NAG | Una colección de rutinas matemáticas y estadísticas desarrolladas por Numerical Algorithms Group para múltiples lenguajes de programación (C, C ++, Fortran, Visual Basic, Java y C #) y paquetes (MATLAB, Excel, R, LabVIEW). El capítulo Optimización de la biblioteca NAG incluye rutinas para problemas de programación cuadrática con matrices de restricciones lineales dispersas y no dispersas, junto con rutinas para la optimización de sumas de cuadrados lineales, no lineales de funciones lineales o no lineales con restricciones no lineales, acotadas o sin restricciones . La biblioteca NAG tiene rutinas para la optimización local y global, y para problemas continuos o enteros. |
Pitón | Lenguaje de programación de alto nivel con enlaces para la mayoría de los solucionadores disponibles. La programación cuadrática está disponible a través de la función solve_qp o llamando directamente a un solucionador específico. |
R (Fortran) | Marco de cálculo estadístico multiplataforma universal con licencia GPL . |
SAS / OR | Un conjunto de solucionadores para optimización lineal, entera, no lineal, sin derivadas, de red, combinatoria y de restricciones; el lenguaje de modelado algebraico OPTMODEL; y una variedad de soluciones verticales dirigidas a problemas / mercados específicos, todos los cuales están completamente integrados con el Sistema SAS . |
TK Solver | Sistema de software de modelado matemático y resolución de problemas basado en un lenguaje declarativo basado en reglas, comercializado por Universal Technical Systems, Inc .. |
TOMLAB | Admite optimización global, programación de enteros, todo tipo de mínimos cuadrados, programación lineal, cuadrática y sin restricciones para MATLAB . TOMLAB admite solucionadores como Gurobi , CPLEX , SNOPT y KNITRO . |
XPRESS | Solucionador de programas lineales a gran escala, programas cuadráticos, programas generales no lineales y de enteros mixtos. Tiene API para varios lenguajes de programación, también tiene un lenguaje de modelado Mosel y trabaja con AMPL, GAMS . Gratis para uso académico. |
Ver también
- Programación cuadrática secuencial
- Programación lineal
- Método de línea crítica
Referencias
- ^ 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
- ^ 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..
- ^ a b Murty, Katta G. (1988). Complementariedad lineal, programación lineal y no lineal . Serie Sigma en Matemática Aplicada. 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.
- ^ 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.
- ^ Búsqueda de Google.
- ^ Gould, Nicholas IM; Hribar, Mary E .; Nocedal, Jorge (abril de 2001). "Sobre la solución de problemas de programación cuadrática restringida de igualdad que surgen en la optimización". SIAM J. Sci. Computación . 23 (4): 1376-1395. CiteSeerX 10.1.1.129.7555 . doi : 10.1137 / S1064827598345667 .
- ^ Kozlov, MK; SP Tarasov; Leonid G. Khachiyan (1979). "[Solvabilidad polinomial de programación cuadrática convexa]". Doklady Akademii Nauk SSSR . 248 : 1049-1051. Traducido en: Matemáticas soviéticas - Doklady . 20 : 1108-1111. Falta o vacío
|title=
( ayuda ) - ^ Sahni, S. (1974). "Problemas relacionados con la computación" (PDF) . Revista SIAM de Computación . 3 (4): 262-279. CiteSeerX 10.1.1.145.8685 . doi : 10.1137 / 0203021 .
- ^ Pardalos, Panos M .; Vavasis, Stephen A. (1991). "La programación cuadrática con un valor propio negativo es (fuertemente) NP-difícil". Revista de optimización global . 1 (1): 15-22. doi : 10.1007 / bf00120662 . S2CID 12602885 .
- ^ 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 .
- ^ 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) .
- ^ 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.
Otras lecturas
- Cottle, Richard W .; Pang, Jong-Shi; Stone, 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 NP-Completeness . WH Freeman. ISBN 978-0-7167-1045-5. A6: MP2, pág.245.
- Gould, Nicholas 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 QP
- Guía de optimización NEOS: programación cuadrática
- Programación cuadrática