Lema de Shapley–Folkman
El lema de Shapley-Folkman és el resultat d'una geometria convexa en aplicacions en economia matemàtica que descriu la Sumixca de Minkowski en un espai vectorial. L'adició de Minkowski es definix com l'adició dels membres dels conjunts: per eixemple, agregar el conjunt que consistix en els sancers zero i un a sí mateixa produïx el conjunt que consistix en zero, un i dos:
- {0, 1} + {0, 1} = {0 + 0, 0 + 1, 1 + 0, 1 + 1} = {0, 1, 2}.
El lema de Shapley-Folkman i els resultats relacionats proporcionen una resposta afirmativa a la pregunta: "¿És la suma de molts conjunts casi convexa ?" [1] Un conjunt es definix com convexo si cada segment de llínea que unix dos dels seus punts és un subconjunt en el conjunt: per eixemple, el disc sòlit és un conjunt convexo pero el círcul no ho és, perque el segment de llínea unix dos punts distints no és un subconjunt del círcul. El lema de Shapley-Folkman sugerix que si el número de conjunts sumats excedix la dimensió de l'espai vectorial, llavors la seua suma de Minkowski és aproximadament convexa.[2]
El lema de Shapley-Folkman es va introduir com un pas en la prova de la teorema de Shapley-Folkman, que establix un llímit superior en la distància entre la suma de Minkowski i la seua envolvente convexa. El caixco convexo d'un conjunt Q és el conjunt convexo més chicotet que conté Q. Esta distància és zero si i solament si la suma és convexa. La teorema vinculada a la distància depén de la dimensió D i de les formes dels conjunts de suma i resta, pero no del número de conjunts sumatorios N, quan N > D. Les formes d'una subcolección de sol D summand-sets determinen el llímit en la distància entre el promig de N de Minkowski:
- Plantilla:Frac (Q1 + Q2 + ... + QN)
i el seu caixco convexo. A mida que N aumenta fins al infinit, el llímit disminuïx a zero (per a summand-sets de tamany uniformemente acotat).[3] El llímit superior de la teorema de Shapley-Folkman es va reduir pel corolari de Starr (alternativament, la teorema de Shapley-Folkman-Starr).
El lema de Lloyd Shapley i Jon Folkman va ser publicat per primera volta per l'economiste Ross M. Starr, qui estava investigant l'existència d'equilibris econòmics mentres estudiava en Kenneth Arrow.[2] En el seu artícul, Starr va estudiar una economia convexificada, en la qual els conjunts no convexos varen ser reemplaçats pels seus caixcos convexos; Starr va demostrar que l'economia convexificada té equilibris que s'aproximen per "cuasi-equilibris" de l'economia original; ademés, va demostrar que tot cuasiequilibrio té moltes de les propietats òptimes dels equilibris verdaders, que s'ha comprovat que existixen per a les economies convexas. Seguint el document de Starr de 1969, els resultats de Shapley-Folkman-Starr han segut àmpliament utilisats per a mostrar que els resultats centrals de la teoria econòmica (convexa) són bones aproximacions per a les economies grans en no convexidades; per eixemple, els cuasi-equilibris s'aproximen als equilibris d'una economia convexificada. "La derivació d'estos resultats en forma general ha segut un dels principals guanys de la teoria econòmica de la posguerra", va escriure Roger Guesnerie.[4] El tema dels conjunts no convexos en economia ha segut estudiat per molts premis Nobel, ademés de Lloyd Shapley, que va guanyar el premi en 2012: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008) i Paul Samuelson (1970); el tema complementari de conjunts convexos en economia ha segut emfatisat per estos guardonats, junt en Leonid Hurwicz, Leonid Kantorovich (1975) i Robert Solow (1987).
El lema Shapley-Folkman també té aplicacions en optimisació i teoria de la provabilitat.[3] En la teoria d'optimisació, el lema Shapley-Folkman s'ha utilisat per a explicar la solució exitosa de problemes de minimisació que són sumes de moltes funcions.</ref>[5][6] El lema de Shapley-Folkman també s'ha utilisat en proves de la "Llei dels grans números" per a conjunts aleatoris, una teorema que s'ha demostrat solament per a conjunts convexos.[7][8]
Referències
[editar | editar còdic]- ↑ Howe (1979, p. 1): Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ 2,0 2,1 Starr (1969)
- ↑ 3,0 3,1 Starr (2008)
- ↑ Guesnerie (1989, p. 138)
- ↑ Plantilla:Harv: 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.
- ↑ 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ó, Belmont, MA: Athena Scientific, pp. xiii+395. ISBN 1-886529-04-3.
Bertsekas (1996, pp. 364–381) descrius an application of Lagrangian dual methods to the scheduling of electrical power plants ("unit commitment problems"), where senar-convexity appears because of integer constraints:
IEEE Transactions on Automatic Control.AC-28(Proceedings of 1981 IEEE Conference on Decision and Control, Sant Diego, CA, December 1981, pp. 432–443)
- 1–11.doi:10.1109/tac.1983.1103136.Consultat el 2 de febrer de 2011.
- ↑ Artstein y Vitale (1975, pp. 881–882): Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ Puri y Ralescu (1985, pp. 154–155): (1985).Mathematical Proceedings of the Cambridge Philosophical Society.97(1)
- 151–158.doi:10.1017/S0305004100062691.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Lema de Shapley–Folkman» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.