Programación cuadrática

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

Formulación del problema

El problema de programación cuadrática con n variables y m se pueden formular de la siguiente manera. Dado:

• un valor real, n-dimensional vector c,
• an n×n- matriz simétrica real dimensionada Q,
• an m×n- matriz real dimensionada A, y
• an m-dimensional vector real b,

el objetivo de la programación cuadrática es encontrar un vector n-dimensional x, eso será

minimizar	12xTQx+cTx{displaystyle {tfrac}{2}mathbf {x} ^{mathrm {T}Qmathbf {x} +mathbf {c} ^{mathrm {T}mathbf {x}
sujeto a	Ax⪯ ⪯ b,{displaystyle Amathbf {x} preceq mathbf {b}

donde x^T indica la transposición vectorial de x, y la notación Ax ⪯ b significa que cada entrada del vector Ax es menor o igual que la entrada correspondiente del vector b (desigualdad por componentes).

Mínimos cuadrados

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

minimizar	12.. Rx− − d.. 2{fnMicroc} {1}{2}fnción Mathbf {x} {2}
sujeto a	Ax⪯ ⪯ b,{displaystyle Amathbf {x} preceq mathbf {b}

donde sigue Q = R^TR 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 QP, incluso para una matriz genérica R 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 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.

Métodos de solución

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

• punto interior,
• activo,
• Lagrangian aumentada,
• conyugal gradiente,
• proyección gradiente,
• extensiones del algoritmo simplex.

En el caso en que Q sea 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. Al usar multiplicadores de Lagrange y buscar el extremo del Lagrangiano, se puede demostrar fácilmente que la solución al problema de igualdad restringida

Minimize12xTQx+cTx{displaystyle {text{Minimize}quad {tfrac}{2}mathbf {x} ^{mathrm {T}Qmathbf {x} +mathbf {c} ^{mathrm {T}mathbf {x}

sujeto aEx=d{displaystyle {text{subject to}quad} Emathbf {x} =mathbf {d}

está dado por el sistema lineal

[QE⊤ ⊤ E0][xλ λ ]=[− − cd]{displaystyle {begin{bmatrix}Q {begin{bmatrix}mathbf {x}\\\\\lambdaend{bmatrix}}={begin{bmatrix}-mathbbff {c} {\\\\\\\\\\\\\\\\\\fn}}} {\\\\\\\\\\\\\\\\\\\\\\fn}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

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 para problemas pequeños es muy práctica. Para problemas grandes, el sistema plantea algunas dificultades inusuales, sobre todo que el problema nunca es positivo definido (incluso si Q lo es), por lo que es potencialmente muy difícil encontrar un buen enfoque numérico, y hay muchos enfoques para elegir dependiendo del problema.

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 distinto de cero es sencillo). Mirando las ecuaciones de restricción:

Ex=0{displaystyle Emathbf {x} =0}

introducir una nueva variable y definida por

ZSí.=x{displaystyle Zmathbf {y} =mathbf {x}

donde y tiene una dimensión de x menos el número de restricciones Después

EZSí.=0{fnK}

y si se elige Z para 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. Sustituyendo en la forma cuadrática da un problema de minimización sin restricciones:

12x⊤ ⊤ Qx+c⊤ ⊤ x⟹ ⟹ 12Sí.⊤ ⊤ Z⊤ ⊤ QZSí.+()Z⊤ ⊤ c)⊤ ⊤ Sí.{fnMicrosoft} {fnMicrosoft} {f} {f} {f}f} {f} {f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}

cuya solución viene dada por:

Z⊤ ⊤ QZSí.=− − Z⊤ ⊤ c{displaystyle Z^{top }QZmathbf {y} =-Z^{top }Mathbf {c}

Bajo ciertas condiciones en Q, la matriz reducida Z^TQZ será definido positivo. Es posible escribir una variación del método de gradiente conjugado que evita el cálculo explícito de Z.

Dualidad lagrangiana

El dual lagrangiano de un QP también es un QP. Para ver esto, centrémonos en el caso donde c = 0 y Q es definido positivo. Escribimos la función lagrangiana como

L()x,λ λ )=12x⊤ ⊤ Qx+λ λ ⊤ ⊤ ()Ax− − b).{displaystyle L(x,lambda)={tfrac {1}{2}x^{top }Qx+lambda ^{top }(Ax-b).}

Definición de la función dual (Lagrangian) g(λ) como g()λ λ )=infxL()x,λ λ ){displaystyle g(lambda)=inf _{x}L(x,lambda)}, encontramos un infimum de L, utilizando Silencio Silencio xL()x,λ λ )=0{displaystyle nabla _{x}L(x,lambda)=0} y determinación positiva de Q:

xAlternativa Alternativa =− − Q− − 1A⊤ ⊤ λ λ .{displaystyle x^{*}=-Q^{-1}A^{top }lambda.}

Por lo tanto, la función dual es

g()λ λ )=− − 12λ λ ⊤ ⊤ AQ− − 1A⊤ ⊤ λ λ − − λ λ ⊤ ⊤ b,{displaystyle g(lambda)=-{tfrac {1}{2}lambda - 'lambda ^{top }b,}

y entonces el dual lagrangiano del QP es

maximizarλ λ ≥ ≥ 0− − 12λ λ ⊤ ⊤ AQ− − 1A⊤ ⊤ λ λ − − λ λ ⊤ ⊤ b{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 la dualidad lagrangiana, existen otros pares de dualidad (por ejemplo, Wolfe, etc.).

Complejidad

Para Q definido positivo, el método del elipsoide resuelve el problema en tiempo polinomial (débil). Si, por otro lado, Q es indefinido, entonces el problema es NP-difícil. Puede haber varios puntos estacionarios y mínimos locales para estos problemas no convexos. De hecho, incluso si Q tiene solo un valor propio negativo, el problema es (fuertemente) NP-difícil.

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). Las aplicaciones de MIQP incluyen recursos hídricos y la construcción de fondos indexados.

Lenguajes de resolución y scripting (programación)