Problema de complementariedad lineal

En la teoría de la optimización matemática , el problema de complementariedad lineal (PCL) surge con frecuencia en la mecánica computacional y abarca la conocida programación cuadrática como un caso particular. Fue propuesto por Cottle y Dantzig en  1968. ^{[ 1 ] [ 2 ] [ 3 ]}

Dada una matriz real M y un vector q , el problema de complementariedad lineal LCP( q , M ) busca vectores z y w que satisfagan las siguientes restricciones:

• ${\displaystyle w,z\geqslant 0,}$(es decir, cada componente de estos dos vectores es no negativo )
• ${\displaystyle z^{T}w=0}$o equivalentemente${\displaystyle \sum \nolimits _ {i}w_ {i}z_ {i} = 0.}$Esta es la condición de complementariedad , ya que implica que, para todo${\displaystyle i}$, como máximo uno de${\displaystyle w_{i}}$y${\displaystyle z_{i}}$puede ser positivo.
• ${\displaystyle w=Mz+q}$

Una condición suficiente para la existencia y unicidad de una solución a este problema es que M sea simétrica definida positiva . Si M es tal que LCP( q , M ) tiene una solución para cada q , entonces M es una matriz Q. Si M es tal que LCP( q , M ) tiene una solución única para cada q , entonces M es una matriz P. Ambas caracterizaciones son suficientes y necesarias. ^{[ 4 ]}

El vector w es una variable de holgura ^{[ 5 ]} y , por lo tanto, generalmente se descarta después de encontrar z . De este modo, el problema también puede formularse como:

• ${\displaystyle Mz+q\geqslant 0}$
• ${\displaystyle z\geqslant 0}$
• ${\displaystyle z^{\mathrm {T} }(Mz+q)=0}$(la condición de complementariedad)

Encontrar una solución al problema de complementariedad lineal está asociado con la minimización de la función cuadrática.

${\displaystyle f(z)=z^{T}(Mz+q)}$

sujeto a las restricciones

${\displaystyle {Mz}+q\geqslant 0}$

${\displaystyle z\geqslant 0}$

Estas restricciones garantizan que f siempre sea no negativo. El mínimo de f es 0 en z si y solo si z resuelve el problema de complementariedad lineal.

Si M es definida positiva , cualquier algoritmo para resolver problemas cuadráticos (estrictamente) convexos puede resolver el problema de mínimos cuadrados. Se han utilizado durante décadas algoritmos de pivoteo con intercambio de bases especialmente diseñados, como el algoritmo de Lemke y una variante del algoritmo simplex de Dantzig . Además de tener una complejidad temporal polinómica, los métodos de punto interior también son eficaces en la práctica.

Además, un problema de programación cuadrática planteado como minimizar${\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}$sujeto a${\displaystyle Ax\geqslant b}$así como${\displaystyle x\geqslant 0}$con simetría Q

es lo mismo que resolver el LCP con

${\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}$

Esto se debe a que las condiciones de Karush-Kuhn-Tucker del problema QP se pueden escribir como:

${\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}}$

donde v son los multiplicadores de Lagrange en las restricciones de no negatividad, λ son los multiplicadores en las restricciones de desigualdad y s son las variables de holgura para las restricciones de desigualdad. La cuarta condición se deriva de la complementariedad de cada grupo de variables ( x , s ) con su conjunto de vectores KKT (multiplicadores de Lagrange óptimos) siendo ( v , λ ) . En ese caso,

${\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}}$

Si se relaja la restricción de no negatividad sobre x , la dimensionalidad del problema LCP se puede reducir al número de desigualdades, siempre que Q sea no singular (lo cual está garantizado si es definida positiva ). Los multiplicadores v ya no están presentes, y las primeras condiciones KKT se pueden reescribir como:

${\displaystyle Qx=A^{T}{\lambda }-c}$

o:

${\displaystyle x=Q^{-1}(A^{T}{\lambda }-c)}$

Premultiplicando ambos lados por A y restando b obtenemos:

${\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,}$

El lado izquierdo, debido a la segunda condición KKT, es s . Sustituyendo y reordenando:

${\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,}$

Llama ahora

${\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}}$

Tenemos un LCP, debido a la relación de complementariedad entre las variables de holgura s y sus multiplicadores de Lagrange λ . Una vez resuelto, podemos obtener el valor de x a partir de λ mediante la primera condición de KKT.

Finalmente, también es posible manejar restricciones de igualdad adicionales:

${\displaystyle A_{eq}x=b_{eq}}$

Esto introduce un vector de multiplicadores de Lagrange μ , con la misma dimensión que${\displaystyle b_{eq}}$.

Es fácil verificar que M y Q para el sistema LCP${\displaystyle s=M{\lambda }+Q}$ahora se expresan como:

${\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}}$

A partir de λ podemos recuperar ahora los valores de x y del multiplicador de Lagrange de las igualdades μ :

${\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}}$

De hecho, la mayoría de los solucionadores QP trabajan en la formulación LCP, incluyendo el método del punto interior , el pivoteo principal/complementario y los métodos de conjunto activo . ^{[ 1 ] [ 2 ]} Los problemas LCP también pueden resolverse mediante el algoritmo de cruce , ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ]} por el contrario, para problemas de complementariedad lineal, el algoritmo de cruce termina finitamente solo si la matriz es una matriz suficiente. ^{[ 8 ] [ 9 ]} Una matriz suficiente es una generalización tanto de una matriz definida positiva como de una matriz P , cuyos menores principales son cada uno positivo. ^{[ 8 ] [ 9 ] [ 10 ]} Tales LCP pueden resolverse cuando se formulan abstractamente utilizando la teoría de matroides orientados . ^{[ 11 ] [ 12 ] [ 13 ]}

• Teoría de la complementariedad
• Los motores de física de tipo impulso/restricción para juegos utilizan este enfoque.
• Dinámica de contacto Dinámica de contacto con el enfoque no suave.
• Los juegos bimatriciales se pueden reducir a LCP.

• Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; Blanco, Neil ; Ziegler, Gunter (1999). "10 programación lineal". Matroides orientadas . Prensa de la Universidad de Cambridge. págs. 417– 479. doi : 10.1017/CBO9780511586507 . ISBN  978-0-521-77750-6. MR 1744046 . 
• Cottle, RW; Dantzig, GB (1968). "Teoría del pivote complementario de la programación matemática" . Álgebra lineal y sus aplicaciones . 1 : 103–125 . doi : 10.1016/0024-3795(68)90052-9 .
• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). El problema de la 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-1MR 1150683 .​ 
• Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (marzo-abril de 1989). "Matrices suficientes y el problema de la complementariedad lineal". Álgebra lineal y sus aplicaciones . 114–115 : 231–249 . doi : 10.1016/0024-3795(89)90463-1 . MR 0986877 . 
• Csizmadia, Zsolt; Illés, Tibor (2006). "Nuevos algoritmos de tipo cruzado para problemas de complementariedad lineal con matrices suficientes" (PDF) . Optimization Methods and Software . 21 (2): 247– 266. doi : 10.1080/10556780500095009 . S2CID 24418835 . 
• Fukuda, Komei ; Namiki, Makoto (marzo de 1994). "Sobre los comportamientos extremos del método del índice mínimo de Murty". Mathematical Programming . 64 (1): 365–370 . doi : 10.1007/BF01582581 . MR 1286455. S2CID 21476636 .  
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos cruzados: una nueva perspectiva sobre los algoritmos de pivote". Mathematical Programming, Series B. Artículos del 16.º Simposio Internacional sobre Programación Matemática celebrado en Lausana, 1997. 79 ( 1–3 ) : 369–395 . CiteSeerX 10.1.1.36.9373 . doi : 10.1007 / BF02614325 . MR 1464775. S2CID 2794181. Preimpresión Postscript .   
• den Hertog, D.; Roos, C.; Terlaky, T. (1 de julio de 1993). "El problema de la complementariedad lineal, matrices suficientes y el método de cruce" (PDF) . Álgebra lineal y sus aplicaciones . 187 : 1–14 . doi : 10.1016/0024-3795(93)90124-7 .
• Murty, Katta G. (enero de 1972). "Sobre el número de soluciones al problema de complementariedad y las propiedades de expansión de los conos complementarios" (PDF) . Álgebra lineal y sus aplicaciones . 5 (1): 65–108 . doi : 10.1016/0024-3795(72)90019-5 . hdl : 2027.42/34188 .
• Murty, KG (1988). Complementariedad lineal, programación lineal y no lineal . Serie Sigma en Matemáticas Aplicadas. Vol.  3. Berlín: Heldermann Verlag. ISBN 978-3-88538-403-8MR 0949214. Versión PDF actualizada y gratuita en el sitio web de Katta G. Murty . Archivado del original el 1 de abril de 2010. 
• Taylor, Joshua Adam (2015). Optimización convexa de sistemas de potencia . Cambridge University Press. ISBN 9781107076877.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para programación lineal: una revisión de los desarrollos teóricos recientes". Annals of Operations Research . Degeneración en problemas de optimización. 46–47 (1): 203–233 . CiteSeerX 10.1.1.36.7658 . doi : 10.1007/BF02096264 . ISSN 0254-5330 . MR 1260019. S2CID 6058077 .    
• Todd, Michael J. (1985). "Programación lineal y cuadrática en matroides orientados" . Journal of Combinatorial Theory . Serie B. 39 (2): 105– 133. doi : 10.1016/0095-8956(85)90042-5 . MR 0811116 . 

• R. Chandrasekaran. "Juegos bimatriciales" (PDF) . págs. 5–7 . Consultado el 18 de diciembre de 2015 . 

• LCPSolve : un procedimiento sencillo en GAUSS para resolver un problema de complementariedad lineal.
• Siconos /Numerics es una implementación de código abierto (GPL) en C del algoritmo de Lemke y otros métodos para resolver LCP y MLCP.