En la teoría de la 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. Cottle y Dantzig lo propusieron en 1968. [1] [2] [3]
Formulación
Dada una matriz real M y el vector q , el LCP problema complementariedad lineal ( q , M ) tiene por objeto vectores z y w que cumplan las siguientes restricciones:
- (es decir, cada componente de estos dos vectores no es negativo)
- o equivalente Esta es la condición de complementariedad , ya que implica que, para todos, a lo sumo uno de y puede ser positivo.
Una condición suficiente para la existencia y unicidad de una solución a este problema es que M sea simétrico positivo-definido . Si M es tal que LCP ( q , M ) tiene una solución para cada q , entonces M es una Q-matriz . Si M es tal que LCP ( q , M ) tiene una solución única para cada q , entonces M es una P-matriz . 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 . Como tal, el problema también se puede formular como:
- (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 minimizar la función cuadrática
sujeto a las limitaciones
Estas restricciones aseguran 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 positivo definido , cualquier algoritmo para resolver (estrictamente) QP convexos puede resolver el LCP. Los algoritmos pivotantes de intercambio de bases 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 una complejidad de tiempo polinomial, los métodos de punto interior también son efectivos en la práctica.
Además, un problema de programación cuadrática establecido como minimizar sujeto a así como con Q simétrico
es lo mismo que resolver el LCP con
Esto se debe a que las condiciones de Karush-Kuhn-Tucker del problema QP se pueden escribir como:
con v los multiplicadores de Lagrange en las restricciones de no negatividad, λ los multiplicadores en las restricciones de desigualdad y s las variables de holgura para las restricciones de desigualdad. La cuarta condición deriva de la complementariedad de cada grupo de variables ( x , s ) con su conjunto de vectores KKT (multiplicadores óptimos de Lagrange) siendo ( v , λ ) . En ese caso,
Si la restricción de no negatividad sobre x se relaja, la dimensionalidad del problema LCP se puede reducir al número de desigualdades, siempre que Q no sea singular (lo cual está garantizado si es positivo definido ). Los multiplicadores v ya no están presentes y las primeras condiciones KKT se pueden reescribir como:
o:
pre-multiplicando los dos lados por A y restando b obtenemos:
El lado izquierdo, debido a la segunda condición KKT, es s . Sustituir y reordenar:
Llamando ahora
tenemos un LCP, debido a la relación de complementariedad entre las variables de holgura sy sus multiplicadores de Lagrange λ . Una vez que lo resolvemos, podemos obtener el valor de x desde λ hasta la primera condición KKT.
Finalmente, también es posible manejar restricciones de igualdad adicionales:
Esto introduce un vector de multiplicadores de Lagrange μ , con la misma dimensión que.
Es fácil verificar que M y Q para el sistema LCP ahora se expresan como:
A partir de λ ahora podemos recuperar los valores tanto de x como del multiplicador de igualdad de Lagrange μ :
De hecho, la mayoría de los solucionadores de QP trabajan en la formulación de LCP, incluido el método de punto interior , el pivote de principal / complementariedad y los métodos de conjunto activo . [1] [2] Los problemas de LCP también pueden resolverse mediante el algoritmo entrecruzado , [6] [7] [8] [9] a la inversa, para problemas de complementariedad lineal, el algoritmo entrecruzado termina de manera finita 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 principales menores son cada uno positivo. [8] [9] [10] Tales LCP pueden resolverse cuando se formulan de manera abstracta utilizando la teoría de la matriz orientada . [11] [12] [13]
Ver 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 de Bimatrix se pueden reducir a un LCP.
Notas
- ↑ a b Murty (1988) .
- ↑ a b Cottle, Pang y Stone (1992) .
- ^ Cottle y Dantzig (1968) .
- ^ Murty (1972) .
- ^ Taylor (2015) , pág. 172 .
- ^ Fukuda y Namiki (1994) .
- ^ Fukuda y Terlaky (1997) .
- ↑ a b c den Hertog, Roos & Terlaky (1993) .
- ↑ a b c Csizmadia y Illés (2006) .
- ^ Cottle, Pang y Venkateswaran (1989) .
- ^ Todd (1985) .
- ^ Terlaky y Zhang (1993) .
- ^ Björner y col. (1999) .
Referencias
- Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil ; Ziegler, Günter (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 del pivote complementario de la programación matemática". Álgebra lineal y sus aplicaciones . 1 : 103-125.
- Cottle, Richard W .; Pang, Jong-Shi; Stone, Richard E. (1992). El problema de la complementariedad lineal . Informática y Computación Científica. Boston, MA: Academic Press, Inc. págs. Xxiv + 762 págs. ISBN 978-0-12-192350-1. Señor 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 . Señor 0986877 .
- Csizmadia, Zsolt; Illés, Tibor (2006). "Nuevos algoritmos de tipo cruzado para problemas de complementariedad lineal con matrices suficientes" (PDF) . Métodos y software de optimización . 21 (2): 247–266. doi : 10.1080 / 10556780500095009 . S2CID 24418835 .
- Fukuda, Komei ; Namiki, Makoto (marzo de 1994). "Sobre comportamientos extremos del método de índice mínimo de Murty". Programación matemática . 64 (1): 365–370. doi : 10.1007 / BF01582581 . Señor 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 de pivote". Programación Matemática, Serie B . Artículos del 16º Simposio Internacional de Programación Matemática celebrado en Lausana, 1997. 79 (1-3): 369–395. CiteSeerX 10.1.1.36.9373 . doi : 10.1007 / BF02614325 . Señor 1464775 . S2CID 2794181 . Preimpresión posdata .
- den Hertog, D .; Roos, C .; Terlaky, T. (1 de julio de 1993). "El problema de la complementariedad lineal, matrices suficientes y el método entrecruzado" (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 la complementariedad y las propiedades que atraviesan 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ática Aplicada. 3 . Berlín: Heldermann Verlag. ISBN 978-3-88538-403-8. Señor 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 . Prensa de la Universidad de Cambridge. ISBN 9781107076877.
- Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para la programación lineal: una encuesta sobre los desarrollos teóricos recientes". Anales de investigación operativa . 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 . Señor 1260019 . S2CID 6058077 .
- Todd, Michael J. (1985). "Programación lineal y cuadrática en matroides orientadas" . Revista de teoría combinatoria . Serie B 39 (2): 105-133. doi : 10.1016 / 0095-8956 (85) 90042-5 . Señor 0811116 .
Otras lecturas
- R. Chandrasekaran. "Juegos de Bimatrix" (PDF) . págs. 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 de GPL de código abierto Siconos / Numerics en C del algoritmo de Lemke y otros métodos para resolver LCP y MLCP