Ir al contenido

Lema de Shapley–Folkman

De Wikipedia, la enciclopedia libre
A la izquierda, cuatro conjuntos no convexos de puntos rojos. A la derecha su suma de Minkowski. Todos tienen sus envolventes convexas sombreadas en rosa. Se puede observar que el punto (+) del conjunto en la derecha se obtiene como la suma de dos puntos en las envolventes (arriba izquierda) y dos puntos en los conjuntos (abajo izquierda).

El lema de Shapley-Folkman es el resultado de una geometría convexa con aplicaciones en economía matemática que describe la Suma de Minkowski en un espacio vectorial. La adición de Minkowski se define como la adición de los miembros de los conjuntos: por ejemplo, agregar el conjunto que consiste en los enteros cero y uno a sí mismo produce el conjunto que consiste en cero, uno y dos:

{0, 1} + {0, 1} = {0 + 0, 0 + 1, 1 + 0, 1 + 1} = {0, 1, 2}.

El lema de Shapley-Folkman y los resultados relacionados proporcionan una respuesta afirmativa a la pregunta: "¿Es la suma de muchos conjuntos casi convexa ?" [1]​ Un conjunto se define como convexo si cada segmento de línea que une dos de sus puntos es un subconjunto en el conjunto: por ejemplo, el disco sólido   es un conjunto convexo pero el círculo   no lo es, porque el segmento de línea une dos puntos distintos   no es un subconjunto del círculo. El lema de Shapley-Folkman sugiere que si el número de conjuntos sumados excede la dimensión del espacio vectorial, entonces su suma de Minkowski es aproximadamente convexa.[2]​

El lema de Shapley-Folkman se introdujo como un paso en la prueba del teorema de Shapley-Folkman, que establece un límite superior en la distancia entre la suma de Minkowski y su envolvente convexa. El casco convexo de un conjunto Q es el conjunto convexo más pequeño que contiene Q. Esta distancia es cero si y solo si la suma es convexa. El teorema vinculado a la distancia depende de la dimensión D y de las formas de los conjuntos de suma y resta, pero no del número de conjuntos sumatorios N, cuando N > D. Las formas de una subcolección de solo D summand-sets determinan el límite en la distancia entre el promedio de N de Minkowski:

1⁄N (Q1 + Q2 + ... + QN)

y su casco convexo. A medida que N aumenta hasta el infinito, el límite disminuye a cero (para summand-sets de tamaño uniformemente acotado).[3]​ El límite superior del teorema de Shapley-Folkman se redujo por el corolario de Starr (alternativamente, el teorema de Shapley-Folkman-Starr).

El lema de Lloyd Shapley y Jon Folkman fue publicado por primera vez por el economista Ross M. Starr, quien estaba investigando la existencia de equilibrios económicos mientras estudiaba con Kenneth Arrow.[2]​ En su artículo, Starr estudió una economía convexificada, en la cual los conjuntos no convexos fueron reemplazados por sus cascos convexos; Starr demostró que la economía convexificada tiene equilibrios que se aproximan por "cuasi-equilibrios" de la economía original; además, demostró que todo cuasiequilibrio tiene muchas de las propiedades óptimas de los equilibrios verdaderos, que se ha comprobado que existen para las economías convexas. Siguiendo el documento de Starr de 1969, los resultados de Shapley-Folkman-Starr han sido ampliamente utilizados para mostrar que los resultados centrales de la teoría económica (convexa) son buenas aproximaciones para las economías grandes con no convexidades; por ejemplo, los cuasi-equilibrios se aproximan a los equilibrios de una economía convexificada. "La derivación de estos resultados en forma general ha sido uno de los principales logros de la teoría económica de la posguerra", escribió Roger Guesnerie.[4]​ El tema de los conjuntos no convexos en economía ha sido estudiado por muchos premios Nobel, además de Lloyd Shapley, que ganó el premio en 2012: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008) y Paul Samuelson (1970); el tema complementario de conjuntos convexos en economía ha sido enfatizado por estos galardonados, junto con Leonid Hurwicz, Leonid Kantorovich (1975) y Robert Solow (1987).

El lema Shapley-Folkman también tiene aplicaciones en optimización y teoría de la probabilidad.[3]​ En la teoría de optimización, el lema Shapley-Folkman se ha utilizado para explicar la solución exitosa de problemas de minimización que son sumas de muchas funciones.</ref>[5]​[6]​ El lema de Shapley-Folkman también se ha utilizado en pruebas de la "Ley de los grandes números" para conjuntos aleatorios, un teorema que se ha demostrado solo para conjuntos convexos.[7]​[8]​

Referencias

[editar]
  1. ↑ Howe (1979, p. 1): Howe, Roger (3 de noviembre de 1979), On the tendency toward convexity of the vector sum of sets, Cowles Foundation discussion papers 538, Box 2125 Yale Station, New Haven, CT 06520: Cowles Foundation for Research in Economics, Yale University, consultado el 1 de enero de 2011 .
  2. ↑ a b Starr (1969)
  3. ↑ a b Starr (2008)
  4. ↑ Guesnerie (1989, p. 138)
  5. ↑ (Ekeland, 1999, pp. 357–359): Published in the first English edition of 1976, Ekeland's appendix proves the Shapley–Folkman lemma, also acknowledging Lemaréchal's experiments on page 373.
  6. ↑ Bertsekas (1996, pp. 364–381) acknowledging Ekeland (1999) on page 374 and Aubin y Ekeland (1976) on page 381: Bertsekas, Dimitri P. (1996). «5.6 Large scale separable integer programming problems and the exponential method of multipliers». Constrained optimization and Lagrange multiplier methods (Reprint of (1982) Academic Press edición). Belmont, MA: Athena Scientific. pp. xiii+395. ISBN 1-886529-04-3. MR 690767.  Bertsekas (1996, pp. 364–381) describes an application of Lagrangian dual methods to the scheduling of electrical power plants ("unit commitment problems"), where non-convexity appears because of integer constraints: Bertsekas, Dimitri P.; Lauer, Gregory S.; Sandell, Nils R., Jr.; Posbergh, Thomas A. (January 1983). «Optimal short-term scheduling of large-scale power systems». IEEE Transactions on Automatic Control. AC-28 (Proceedings of 1981 IEEE Conference on Decision and Control, San Diego, CA, December 1981, pp. 432–443): 1-11. doi:10.1109/tac.1983.1103136. Consultado el 2 de febrero de 2011. 
  7. ↑ Artstein y Vitale (1975, pp. 881–882): Artstein, Zvi; Vitale, Richard A. (1975), «A strong law of large numbers for random compact sets», The Annals of Probability 3 (5): 879-882, JSTOR 2959130, MR 385966, Zbl 0313.60012, doi:10.1214/aop/1176996275 .
  8. ↑ Puri y Ralescu (1985, pp. 154–155): Puri, Madan L.; Ralescu, Dan A. (1985). «Limit theorems for random compact sets in Banach space». Mathematical Proceedings of the Cambridge Philosophical Society 97 (1): 151-158. MR 764504. doi:10.1017/S0305004100062691. 
Obtenido de «https://es.wikipedia.org/w/index.php?title=Lema_de_Shapley–Folkman&oldid=160940424»