Problema de complementariedad lineal

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

Formulación

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 no es negativo)
• ${\displaystyle z^{T}w=0}$o equivalentemente Esta es la condición de complementariedad , ya que implica que, para todo , como máximo uno de y puede ser positivo. ${\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}$ ${\displaystyle i}$ ${\displaystyle w_{i}}$ ${\displaystyle z_{i}}$
• ${\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 positiva-definida . 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 . Por lo tanto, el problema también se puede formular como:

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

Minimización cuadrática convexa: condiciones mínimas

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 sea siempre no negativa. 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 QP (estrictamente) convexos puede resolver el LCP. Los algoritmos de pivoteo de intercambio de base especialmente diseñados, como el algoritmo de Lemke y una variante del algoritmo simplex de Dantzig , se han utilizado durante décadas. Además de tener complejidad temporal polinómica, los métodos de punto interior también son efectivos en la práctica.

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

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 de x , la dimensionalidad del problema LCP se puede reducir al número de desigualdades, siempre que Q no sea singular (lo que 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 los dos 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)\,}$

Llamando 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 que lo resolvemos, podemos obtener el valor de x a partir de λ a través de la primera condición KKT.

Por último, también es posible gestionar 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 ahora se expresan como: ${\displaystyle s=M{\lambda }+Q}$

${\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 λ ahora podemos recuperar los valores tanto de x como del multiplicador de Lagrange de 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 de QP trabajan con la formulación LCP, incluyendo el método de punto interior , pivoteo principal/complementariedad y métodos de conjunto activo . ^{[1] [2]} Los problemas LCP pueden ser resueltos también por el algoritmo criss-cross , ^{[6] [7] [8] [9]} por el contrario, para problemas de complementariedad lineal, el algoritmo criss-cross termina finitamente sólo 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 positivos. ^{[8] [9] [10]} Dichos LCP pueden ser resueltos cuando son formulados de manera abstracta usando la teoría de matroides orientados . ^{[11] [12] [13]}

Véase también

• Teoría de la complementariedad
• Motor de física 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 Bimatrix se pueden reducir a LCP.

Notas

1. Murty (1988).
2. Cottle, Pang y Stone (1992).
3. Cottle y Dantzig (1968).
4. Murty (1972).
5. Taylor (2015), pág. 172.
6. Fukuda y Namiki (1994).
7. Fukuda y Terlaky (1997).
8. den Hertog, Roos y Terlaky (1993).
9. Csizmadia & Illés (2006).
10. Cottle, Pang y Venkateswaran (1989).
11. Todd (1985).
12. Terlaky y Zhang (1993).
13. Björner y otros (1999).

Referencias

• 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.Señor 1744046  .
• Cottle, RW; Dantzig, GB (1968). "Teoría pivote complementaria 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 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  .
• Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (marzo-abril de 1989). "Matrices suficientes y el problema de 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 criss-cross 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". Programación matemática . 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 entrecruzados: una nueva visión de los algoritmos pivote". Programación matemática, serie B. Documentos del 16.º Simposio internacional sobre programación matemática celebrado en Lausana en 1997. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181. Preimpresión de Postscript.
• den Hertog, D.; Roos, C.; Terlaky, T. (1 de julio de 1993). "El problema de complementariedad lineal, matrices suficientes y el método criss-cross" (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-8. MR  0949214. Versión PDF actualizada y gratuita en el sitio web de Katta G. Murty. Archivado desde el 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 encuesta sobre desarrollos teóricos recientes". Anales de investigación de operaciones . 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.

Lectura adicional

• R. Chandrasekaran. "Bimatrix games" (PDF) . pp. 5–7 . Consultado el 18 de diciembre de 2015 .

Enlaces externos

• LCPSolve: un procedimiento simple en GAUSS para resolver un problema de complementariedad lineal
• Implementación GPL de código abierto de Siconos /Numerics en C del algoritmo de Lemke y otros métodos para resolver LCP y MLCP