Programación cuadrática

La programación cuadrática ( English quadratic Programming , QP ) es el proceso de resolver un tipo especial de problema de optimización , a saber, el problema de optimización (minimización o maximización) de una función cuadrática de varias variables bajo restricciones lineales sobre estas variables. La programación cuadrática es un caso especial de programación no lineal .

Planteamiento del problema

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

Dado:

real n - vector dimensional c ,
matriz simétrica real n × n -dimensional Q ,
matriz real A de m × n -dimensional
vector m -dimensional real b ,

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

minimiza	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
bajo condiciones	$A\mathbf {x} \leq \mathbf {b} ,$

donde x T denota el vector transpuesto . La notación A x ≤ b significa que cualquier elemento del vector A x no excede al elemento correspondiente del vector b .

Un problema de programación relacionado, Problema cuadrático con restricciones cuadráticas tiene restricciones cuadráticas en las variables.

Métodos de solución

Se utilizan varios métodos para valores comunes, entre ellos

Método del punto interior
Método de configuración activa [2]
Método Lagrangiano Generalizado [3]
método del gradiente conjugado
Método de proyección de gradiente
Modificación del método simplex [2] [4]

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

Restricciones - Igualdades

El problema de la programación cuadrática es algo más simple si Q es definida positiva y todas las restricciones son iguales (sin desigualdades), ya que en este caso es posible reducir el problema a resolver un sistema de ecuaciones lineales. Si usamos multiplicadores de Lagrange y buscamos el extremo del Lagrangiano, podemos mostrar fácilmente que la solución al problema

minimizar	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
bajo condiciones	$B\mathbf {x} =\mathbf {d}$

determinado por el sistema de ecuaciones lineales

{\begin{bmatrix}Q&B^{T}\\B&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix }} }-\mathbf {c} \\\mathbf {d} \end{bmatriz}}

donde es el conjunto de multiplicadores de Lagrange que aparecen junto con la solución . $\lambda$ ${\matemáticas x}$

La forma más fácil de resolver este sistema es resolverlo por métodos directos (por ejemplo, usando la descomposición LU , que es muy conveniente para problemas pequeños). Para problemas grandes, surgen algunas dificultades inusuales, más notables cuando el problema no es definido positivo (incluso si es definido positivo), lo que hace que sea potencialmente muy difícil encontrar un buen enfoque matemático y hay muchos enfoques dependientes del problema. $q$ .

Si el número de restricciones no es igual al número de variables, se puede intentar un ataque relativamente simple reemplazando las variables de tal manera que las restricciones se satisfagan incondicionalmente. Por ejemplo, digamos que (pasar a valores no nulos es bastante fácil). Considere las restricciones ${\ estilo de visualización \ mathbf {d} = 0}$

B\mathbf {x} =0

Introducimos un nuevo vector definido por la igualdad ${\matemáticas}$

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

donde tiene la dimensión menos el número de restricciones. Después ${\matemáticas}$ ${\matemáticas x}$

BZ\mathbf {y} =0

y si la matriz se elige de modo que , las igualdades en las restricciones siempre se mantendrán. Encontrar una matriz significa encontrar el núcleo de una matriz , lo cual es más o menos fácil, dependiendo de la estructura de la matriz . Sustituyendo el nuevo vector en las condiciones iniciales, obtenemos un problema cuadrático sin restricciones: $Z$ ${\ estilo de visualización BZ = 0}$ $Z$ $B$ $B$

{\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad { \tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y }

y la solución se puede encontrar resolviendo la ecuación

Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c}

Bajo algunas restricciones sobre la matriz reducida , será definida positiva. Puede escribir una variante del método del gradiente conjugado , en la que no es necesario calcular explícitamente la matriz [5] . $q$ $Z^{T}QZ$ $Z$

Dualidad lagrangiana

El problema dual de Lagrange para la programación cuadrática es también un problema de programación cuadrática. Para entender esto, detengámonos en el caso con una matriz definida positiva Q. Escribamos los multiplicadores de Lagrange de la función $c=0$

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

Si definimos la función dual (lagrangiana) como , buscamos un límite inferior utilizando la definición positiva de la matriz Q: ${\ estilo de visualización g (\ lambda)}$ ${\ estilo de visualización g (\ lambda) = \ inf _ {x} L (x, \ lambda)}$ $L$ ${\ estilo de visualización \ nabla _ {x} L (x, \ lambda) = 0}$

x^{*}=-Q^{-1}A^{T}\lambda.

Por lo tanto, la función dual es igual a

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

y el problema dual de Lagrange para el problema original es

minimizar	$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b$
bajo condiciones	${\ estilo de visualización \ lambda \ geqslant 0}$ .

Además de la teoría de la dualidad de Lagrange, existen otros pares duales de problemas (por ejemplo, la dualidad de Wolfe ).

Dificultad

Para una matriz definida positiva Q , el método del elipsoide resuelve el problema en tiempo polinomial [6] . Si, por otro lado, Q no es definida positiva, entonces el problema se vuelve NP-difícil [7] . De hecho, incluso si Q tiene un solo valor propio negativo , el problema es NP-difícil [8] .

Paquetes de soluciones y lenguajes de script

Nombre	Descripción
OBJETIVOS	Sistema de modelado y resolución de problemas de optimización y programación
ALGLIB	Biblioteca de programas (C++, .NET) para análisis numérico con doble licencia (GPL/propietario).
AMPL	Un lenguaje de modelado popular para la optimización matemática a gran escala.
APMonitor	Modelado y optimización para problemas de LP (Programación lineal), QP (Programación cuadrática), NLP (Programación no lineal), MILP (Programación entera), MINLP (Programación no lineal de enteros mixtos) y DAE (Ecuaciones algebraicas diferenciales) en MATLAB y Pitón.
CGAL	Un paquete informático de geometría de código abierto que incluye un sistema para resolver problemas de programación cuadrática.
CPLEX	Popular sistema de resolución de problemas con API (C, C++, Java, .Net, Python, Matlab y R). Gratis para uso académico.
Buscador de soluciones en Excel	Un sistema de resolución de problemas no lineal adaptado para hojas de cálculo, en el que los cálculos de funciones se basan en el valor de las celdas. La versión base está disponible como complemento estándar para Excel.
GAMS	Sistema de simulación de alto nivel para optimización matemática
Gurobi	Un sistema para resolver problemas con algoritmos paralelos para problemas de programación lineal a gran escala, problemas de programación cuadrática y problemas de enteros mixtos. Gratis para uso académico.
IMSL_	Conjunto de funciones matemáticas y estadísticas que un programador puede incluir en su aplicación.
IPOPT	El paquete IPOPT (Interior Point OPTimizer) es un paquete de programación para grandes problemas no lineales.
Artelys	Paquete comercial integrado para optimización no lineal
arce	Lenguaje de programación de propósito general para matemáticas. Maple usa el comando QPSolve para resolver problemas cuadráticos . Archivado el 12 de mayo de 2021 en Wayback Machine .
MATLAB	Lenguaje de programación de propósito general orientado a matrices para cálculos numéricos. Para resolver problemas de programación cuadrática en MATLAB, además del producto básico de MATLAB, se requiere el complemento “Optimization Toolbox”
Matemática	Un lenguaje de programación de propósito general para matemáticas, que incluye capacidades simbólicas y numéricas.
MOSEK	Sistema para la resolución de problemas de optimización a gran escala, incluye API para varios lenguajes (C++, Java, .Net, Matlab y Python)
Biblioteca numérica NAG	Conjunto de procedimientos matemáticos y estadísticos desarrollados por Numerical Algorithms Group para varios lenguajes de programación (C, C++, Fortran, Visual Basic, Java y C#) y paquetes (MATLAB, Excel, R, LabVIEW). La sección de optimización de la biblioteca NAG incluye procedimientos para problemas de programación cuadrática con matrices de restricciones densas y dispersas, así como procedimientos para optimizar funciones lineales y no lineales, sumas de cuadrados de funciones lineales y no lineales. La biblioteca NAG contiene procedimientos para la optimización local y global, así como para problemas de programación de enteros.
OptimJ	Un lenguaje de modelado de optimización basado en Java, de libre distribución, que admite múltiples sistemas de decisión de objetivos. Hay un complemento para Eclipse [9] [10]
R	Paquete informático multiplataforma de uso general con licencia GPL (consulte la sección quadprog Archivado el 19 de junio de 2017 en Wayback Machine de este paquete). Traducido a javascript Archivado el 11 de abril de 2017 en Wayback Machine bajo la licencia MIT . Traducido a C# Archivado el 8 de abril de 2015 en Wayback Machine bajo la LGPL .
SAS /OR	Un sistema para resolver problemas lineales, enteros, combinatorios, no lineales, no diferenciables, problemas en redes y optimización con restricciones. Lenguaje de modelado algebraico OPTMODEL Archivado el 8 de septiembre de 2016 en Wayback Machine y varias soluciones verticales destinadas a tareas específicas están completamente integradas con \|SAS/.
Solucionador de	Un sistema de modelado matemático y resolución de problemas basado en un lenguaje declarativo basado en reglas de producción. El sistema es comercializado por Universal Technical Systems, Inc. Archivado el 1 de abril de 2022 en Wayback Machine .
TOMLAB	Admite optimización global, programación entera, todos los tipos de mínimos cuadrados, programación cuadrática lineal para MATLAB . TOMLAB es compatible con los sistemas de solución Gurobi, CPLEX , SNOPT y KNITRO .

Véase también

Notas

↑ Nocedal, Wright, 2006 , p. 449.
↑ 12 Murty , 1988 , pág. xlviii+629.
↑ Delbos, Gilbert, 2005 , pág. 45–69.
↑ Künzi, Crelle, 1965 , p. 161-179.
↑ Gould, Hribar, Nocedal, 2001 , p. 1376-1395
↑ Kozlov, Tarasov, Khachiyan, 1980 , p. 1049–1051.
↑ Sahni, 1974 , pág. 262–279.
↑ Pardalos y Vavasis, 1991 , p. 15–22.
↑ Zesch, Hellingrath, 2010 .
↑ Burkov, Chaibdraa, 2010 .

Literatura

G.P. Künzi, W. Crelle. Programación no lineal. - Moscú: "Radio Soviética", 1965.
Jorge Nocedal, Stephen J. Wright. Optimización Numérica . — 2do. - Berlín, Nueva York: Springer-Verlag , 2006. - Pág . 449 . - ISBN 978-0-387-30303-1 .
Katta G Murty. Complementariedad lineal, programación lineal y no lineal . - Berlín: Heldermann Verlag, 1988. - V. 3. - C. xlviii + 629 pp.. - (Serie Sigma en Matemática Aplicada). — ISBN 3-88538-403-5 .
F. Delbos, J. Ch. Gilberto. Convergencia lineal global de un algoritmo Lagrangiano aumentado para resolver problemas de optimización cuadrática convexa // Journal of Convex Analysis. - 2005. - T. 12 . - S. 45-69 .
Félix Zesch, Bernd Hellingrath. Un modelo de optimización para líneas de montaje de modelos mixtos // Planificación Integrada de Producción-Distribución. — 2010.
Andriy Burkov, Brahim Chaibdraa. Actas de la Vigésima Cuarta Conferencia AAAI sobre Inteligencia Artificial (AAAI-10). — Atlanta, EE. UU.: AAAI Press, 2010.
Nicholas IM Gould, Mary E. Hribar, Jorge Nocedal. Sobre la solución de problemas de programación cuadrática con restricciones de igualdad que surgen en la optimización. - Revista SIAM de Computación Científica, 2001. - V. 23 , no. 4 . - S. 1376-1395 .
M. K. Kozlov, S. P. Tarasov, L. G. Khachiyan. Resolubilidad de polinomios de programación cuadrática convexa, Zh. Vychisl. Matemáticas. y estera física.- 1980. - T. 20, , núm. 5 .
S. Sahni. Problemas relacionados con la computación // SIAM Journal on Computing. - 1974. - T. 3 . - S. 262-279 . -doi : 10.1137/ 0203021 .
Panos M. Pardalos, Stephen A. Vavasis. La programación cuadrática con un valor propio negativo es NP-hard // Journal of Global Optimization. - 1991. - Vol. 1 , número. 1 . - S. 15-22 . -doi : 10.1007/ bf00120662 .
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. El problema de la complementariedad lineal. - Boston, MA: Academic Press, Inc., 1992. - C. xxiv + 762 pp.. - (Ciencias de la Computación y Computación Científica). — ISBN 0-12-192350-9 .
Michael R. Garey, David S. Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman, 1979. - ISBN 0-7167-1045-5 . A6: MP2, pág.245.
Nicholas IM Gould, Philippe L. Toint. Una bibliografía de programación cuadrática (PDF) . Informe interno del grupo de análisis numérico RAL 2000-1 (2000). (indefinido)

Enlaces

Una página sobre QP Archivado el 7 de junio de 2011 en Wayback Machine .
Guía de optimización de NEOS: Programación cuadrática Archivado el 18 de junio de 2017 en Wayback Machine .
Resolver un problema de programación cuadrática (QP) de ejemplo. Archivado el 10 de mayo de 2015 en Wayback Machine .