Programación cuadrática

Como caso especial cuando Q es simétrica definida positiva , la función de coste se reduce a mínimos cuadrados:

donde Q = R ^T R se obtiene de la descomposición de Cholesky de Q y c = − R ^T d . Por el contrario, cualquier programa de mínimos cuadrados restringidos de este tipo puede plantearse de forma 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 la vecindad de un punto de referencia _x₀ , Q se define como su matriz hessiana H ( f ( x₀ ₎ ) y c como su gradiente ∇f ( x₀ _{) . Un problema} de programación relacionado, la programación cuadrática con restricciones cuadráticas , se puede plantear añadiendo restricciones cuadráticas a las variables.

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

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

${\displaystyle {\text{sujeto a}}\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 aparecen en la solución junto con x .

La forma más sencilla de abordar este sistema es mediante la solución directa (por ejemplo, la factorización LU ), que resulta muy práctica para problemas pequeños. Para problemas grandes, el sistema plantea algunas dificultades inusuales, sobre todo porque el problema nunca es definido positivo (aunque Q lo sea), lo que dificulta enormemente encontrar un buen método numérico, y existen muchos métodos entre los que elegir, dependiendo del problema.

Si las restricciones no acoplan demasiado las variables, un ataque relativamente sencillo consiste en cambiar las variables de modo que las restricciones se satisfagan incondicionalmente. Por ejemplo, supongamos que d = 0 (generalizar a valores distintos de cero es sencillo). Observando 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 satisfará. Encontrar dicho Z implica encontrar el espacio nulo de E , lo cual es más o menos sencillo 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} }$

Bajo ciertas condiciones sobre 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 ]}

Para Q definida positiva , el problema de minimización es convexo . Por lo tanto, el método del elipsoide puede utilizarse para resolver el problema en tiempo (débilmente) polinomial . Esto fue demostrado explícitamente en 1979 por Kozlov, Tarasov y Khachiyan. ^{[ 6 ]}

Ye y Tse ^{[ 7 ]} presentan un algoritmo de tiempo polinomial, que extiende el algoritmo de Karmarkar de programación lineal a 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 utilizando 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.

Cuando Q no es definida positiva (por lo que el problema no es convexo), la programación cuadrática es NP-difícil . Una forma de demostrarlo es mediante el teorema de Motzkin-Straus . ^{[ 9 ]} Este teorema establece que, para cualquier grafo no dirigido G , un cierto programa cuadrático asociado a G tiene un máximo que es función del número de clique de G. Calcular el número de clique de un grafo es un problema NP-difícil bien conocido; por lo tanto, resolver el programa cuadrático también es NP-difícil. Algunos casos especiales importantes también son NP-difíciles:

• Sahni ^{[ 10 ]} demostró la NP-dureza para el caso en que Q es definida negativa (tiene n valores propios negativos);
• Pardalos y Vavasis ^{[ 11 ]} demostraron la NP-dureza (fuerte) siempre que Q tenga al menos un valor propio negativo . Lo hacen mostrando una reducción del problema de la camarilla a un programa cuadrático particular con variables w , x ₁ ... x _n , y _1,2 ... y _(n-1),n , z y función objetivo z - w ² . Demuestran que el grafo de entrada tiene una camarilla de tamaño k, si y solo si el programa cuadrático correspondiente tiene una solución con valor 0.

Además, encontrar un punto KKT de un programa cuadrático no convexo es CLS-difícil. ^{[ 12 ]}