Un problema de complementariedad es un tipo de problema de optimización matemática . Es el problema de optimizar (minimizar o maximizar) una función de dos variables vectoriales sujetas a ciertos requisitos (restricciones) que incluyen: que el producto interno de los dos vectores debe ser igual a cero, es decir, que sean ortogonales. [1] En particular para espacios vectoriales reales de dimensión finita, esto significa que, si uno tiene vectores X e Y con todas las componentes no negativas ( x i ≥ 0 y y i ≥ 0 para todos: en el primer cuadrante si es bidimensional, en el primer octante si es tridimensional), entonces para cada par de componentes x i y y i uno del par debe ser cero, de ahí el nombre de complementariedad . por ejemplo, X = (1, 0) e Y = (0, 2) son complementarios, pero X = (1, 1) e Y = (2, 0) no lo son. Un problema de complementariedad es un caso especial de desigualdad variacional .
Historia
Los problemas de complementariedad se estudiaron originalmente porque las condiciones de Karush-Kuhn-Tucker en la programación lineal y la programación cuadrática constituyen un problema de complementariedad lineal (LCP) o un problema de complementariedad mixto (MCP). En 1963, Lemke y Howson demostraron que, para juegos de dos personas, calcular un punto de equilibrio de Nash es equivalente a un LCP. En 1968 Cottle y Dantzig unificaron la programación lineal y cuadrática y los juegos bimatrix . Desde entonces, el estudio de los problemas de complementariedad y las desigualdades variacionales se ha expandido enormemente.
Las áreas de las matemáticas y la ciencia que contribuyeron al desarrollo de la teoría de la complementariedad incluyen: optimización , problemas de equilibrio , teoría de la desigualdad variacional , teoría del punto fijo , teoría del grado topológico y análisis no lineal .
Ver también
- Programación matemática con restricciones de equilibrio
- formato nl para representar problemas de complementariedad
Referencias
- ^ Billups, Stephen; Murty, Katta (2000). "Problemas de complementariedad" . Revista de Matemática Computacional y Aplicada . 124 (1–2): 303–318. Código bibliográfico : 2000JCoAM.124..303B . doi : 10.1016 / S0377-0427 (00) 00432-5 .
Otras lecturas
- Richard W. Cottle; Jong-Shi Pang; Richard E. Stone (1992). El problema de la complementariedad lineal . Prensa académica . ISBN 978-0-12-192350-1.
- George Isac (1992). Problemas de complementariedad . Saltador. ISBN 978-3-540-56251-1.
- George Isac (2000). Métodos topológicos en la teoría de la complementariedad . Saltador. ISBN 978-0-7923-6274-6.
- Francisco Facchinei; Jong-Shi Pang (2003). Desigualdades Variacionales de Dimensión Finita y Problemas de Complementariedad: v.1 y v.2 . Saltador. ISBN 978-0-387-95580-3.
- Murty, KG (1988). Complementariedad lineal, programación lineal y no lineal . Serie Sigma en Matemática Aplicada. 3 . Berlín: Heldermann Verlag. págs. xlviii + 629 págs. ISBN 3-88538-403-5. Señor 0949214 . Archivado desde el original el 1 de abril de 2010.
Colecciones
- Richard Cottle; F. Giannessi; Jacques Louis Lions, eds. (1980). Desigualdades variacionales y problemas de complementariedad: teoría y aplicaciones . John Wiley e hijos . ISBN 978-0-471-27610-4.
- Michael C. Ferris; Jong-Shi Pang, eds. (1997). Problemas de complementariedad y variación: estado del arte . SIAM . ISBN 978-0-89871-391-6.