Programación cuadrática

Este artículo necesita la atención de un experto en Matemáticas . El problema específico es: Algunos elementos de esta página necesitan aclaración y/o verificación por parte de un experto. Consulte la página de discusión para obtener más detalles. WikiProject Mathematics puede ayudar a reclutar a un experto. ( Febrero de 2017 )

La programación cuadrática ( QP ) es el proceso de resolver ciertos problemas matemáticos de optimización que involucran funciones cuadráticas . En concreto, 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]

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 n -dimensional x , que

minimizar	${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$
sujeto a	${\displaystyle A\mathbf {x} \preceq \mathbf {b},}$

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).

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

minimizar	${\displaystyle {\tfrac {1}{2}}\|R\mathbf {x} -\mathbf {d} \|^{2}}$
sujeto a	${\displaystyle A\mathbf {x} \preceq \mathbf {b} ,}$

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 .

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.

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 .

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]

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.).

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.

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]

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]

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.

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

• 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.Sr. 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.

• 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