Lemma Shapley – Folkman - Shapley–Folkman lemma

The Shapley – Folkmanlemma je výsledkem v konvexní geometrie s aplikacemi v matematická ekonomie který popisuje Minkowského doplnění z sady v vektorový prostor. Minkowského doplnění je definováno jako přidání sad členů: například přidání sady skládající se z celá čísla nula a jedna sama o sobě získá množinu skládající se z nuly, jedné a dvou:
- {0, 1} + {0, 1} = {0 + 0, 0 + 1, 1 + 0, 1 + 1} = {0, 1, 2}.
Lemma Shapley – Folkman a související výsledky poskytují kladnou odpověď na otázku: „Je součet mnoha množin blízký konvexní ?"[2] Sada je definována jako konvexní pokud každý úsečka spojení dvou jejích bodů je a podmnožina v sadě: Například těleso disk je konvexní množina, ale kruh není, protože úsečka spojující dva odlišné body není podmnožinou kruhu. Lemma Shapley – Folkman naznačuje, že pokud počet sečtených sad překročí dimenze vektorového prostoru, pak je jejich Minkowského součet přibližně konvexní.[1]
Lemma Shapley – Folkman bylo představeno jako krok v důkaz z Shapley – Folkman teorém, který uvádí horní hranice na vzdálenost mezi Minkowského součtem a jeho konvexní obal. The konvexní obal sadyQ je nejmenší konvexní sada, která obsahujeQ. Tato vzdálenost je nulová kdyby a jen kdyby součet je konvexní. Veta vázaná na vzdálenost závisí na dimenziD a na tvarech souřadnic součtu, ale ne na počtu souprav součtůN, když N > D. Tvary podsbírky pouzeD množinové soupravy určují vazbu na vzdálenost mezi Minkowskéhoprůměrný zN sady
- 1⁄N (Q1 + Q2 + ... + QN)
a jeho konvexní trup. Tak jakoN zvyšuje na nekonečno, svázaný klesá na nulu (pro množinové sady rovnoměrně ohraničené velikosti).[3] Horní mez věty Shapley-Folkman byla snížena o Starr důsledek (alternativně Věta Shapley – Folkman – Starr).
Lemma Lloyd Shapley a Jon Folkman byl poprvé publikován ekonomem Ross M. Starr, který vyšetřoval existenci ekonomické rovnováhy při studiu s Kenneth Arrow.[1] Starr ve svém příspěvku studoval a konvexní ekonomika, ve které byly nekonvexní sady nahrazeny jejich konvexními trupy; Starr dokázal, že konvexovaná ekonomika má rovnováhy, které jsou úzce aproximovány „kvazi-rovnováhou“ původní ekonomiky; navíc dokázal, že každá kvazi-rovnováha má mnoho optimálních vlastností skutečné rovnováhy, o nichž se prokázalo, že existují pro konvexní ekonomiky. Po článku Starra z roku 1969 byly výsledky Shapley – Folkman – Starr široce používány k prokázání, že ústřední výsledky (konvexní) ekonomické teorie jsou dobrou aproximací pro velké ekonomiky s nekonvexnostmi; například kvazi-rovnováha se blíží rovnováze konvexované ekonomiky. „Odvození těchto výsledků v obecné formě bylo jedním z hlavních úspěchů poválečné ekonomické teorie,“ napsal Roger Guesnerie.[4] Téma nekonvexní množiny v ekonomii bylo studováno mnoha Nositelé Nobelovy ceny, kromě Lloyda Shapleye, který získal cenu v roce 2012: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008) a Paul Samuelson (1970); doplňkové téma konvexní množiny v ekonomii tito laureáti zdůraznili spolu s Leonid Hurwicz, Leonid Kantorovič (1975) a Robert Solow (1987).
Lemma Shapley – Folkman má aplikace také v optimalizace a teorie pravděpodobnosti.[3] V teorii optimalizace bylo Shapley – Folkmanovo lemma použito k vysvětlení úspěšného řešení problémů minimalizace, které jsou součty mnoha funkce.[5][6] Lemma Shapley – Folkman bylo také použito v důkazy z "zákon průměrů" pro náhodné množiny, věta, která byla prokázána pouze pro konvexní množiny.[7]
Úvodní příklad
Například podmnožina celých čísel {0, 1, 2} je obsažena v interval z reálná čísla [0, 2], který je konvexní. Lemma Shapley – Folkman naznačuje, že každý bod v [0, 2] je součtem celého čísla od {0, 1} a reálného čísla od [0, 1].[8]
Vzdálenost mezi konvexním intervalem [0, 2] a nekonvexní množinou {0, 1, 2} se rovná jedné polovině
- 1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.
Vzdálenost mezi průměrný Minkowského součet
- 1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}
a jeho konvexní trup [0, 1] je pouze 1/4, což je poloviční vzdálenost (1/2) mezi jeho součtem {0, 1} a [0, 1]. Když se přidá více sad, průměr jejich součtu „vyplní“ jeho konvexní trup: Maximální vzdálenost mezi průměrem a jeho konvexním trupem se blíží nule, protože průměr zahrnuje více summands.[8]
Předkola
Lemma Shapley – Folkman závisí na následujících definicích a výsledcích z konvexní geometrie.
Skutečné vektorové prostory
A nemovitý vektorový prostor ze dvourozměry lze dát a Kartézský souřadnicový systém ve kterém je každý bod identifikován pomocí objednaný pár reálných čísel, nazývaných „souřadnice“, která jsou konvenčně označovánaX ay. Dva body v kartézské rovině mohou být přidané koordinovaně
- (X1, y1) + (X2, y2) = (X1+X2, y1+y2);
dále může být bod znásobeno každým reálným číslemλ koordinovaně
- λ (X, y) = (λx, λy).
Obecněji řečeno, jakýkoli skutečný vektorový prostor (konečné) dimenzeD lze zobrazit jako soubor ze všech D- n-tice zD reálná čísla { (proti1, proti2, . . . , protiD) } na kterých dvouoperace jsou definovány: vektorové přidání a násobení reálným číslem. U konečných trojrozměrných vektorových prostorů lze operace sčítání vektorů a násobení reálných čísel definovat po souřadnicích podle příkladu karteziánské roviny.[9]
Konvexní sady


Ve skutečném vektorovém prostoru, a neprázdný souborQ je definován jako konvexní pokud pro každý pár jeho bodů každý bod na úsečka který se k nim připojí je podmnožina zQ. Například těleso disk je konvexní, ale a kruh není, protože neobsahuje úsečku spojující její body; nekonvexní množina tří celých čísel {0, 1, 2} je obsažena v intervalu [0, 2], který je konvexní. Například těleso krychle je konvexní; vše, co je duté nebo promáčknuté, například a půlměsíc tvar, není konvexní. The prázdná sada je konvexní, buď z definice[10] nebo vakuově, v závislosti na autorovi.
Více formálně sadaQ je konvexní, pokud pro všechny bodyproti0 aproti1 vQ a za každé skutečné čísloλ v jednotkový interval [0,1], bod
- (1 − λ) proti0 + λv1
je člen zQ.
Podle matematická indukce, sadaQ je konvexní právě tehdy, když každý konvexní kombinace členůQ také patříQ. Podle definice a konvexní kombinace indexované podmnožiny {proti0, proti1, . . . , protiD} vektorového prostoru je libovolný vážený průměrλ0proti0 + λ1proti1 + . . . + λDprotiD, pro nějakou indexovanou množinu nezáporných reálných čísel {λd} splňující rovniciλ0 + λ1 + . . . + λD = 1.[11]
Definice konvexní množiny znamená, že průsečík dvou konvexních množin je konvexní množina. Obecněji řečeno, průsečík rodiny konvexních množin je konvexní množina. Zejména křižovatka dvou disjunktní sady je prázdná množina, která je konvexní.[10]
Konvexní obal

Pro každou podmnožinuQ skutečného vektorového prostoru, jeho konvexní obal Konv. (Q) je minimální konvexní sada, která obsahujeQ. Takto Conv (Q) je průsečík všech konvexních množin, které Pokrýt Q. Konvexní trup množiny lze ekvivalentně definovat jako množinu všech konvexních kombinací bodů vQ.[12] Například konvexní trup množiny celá čísla {0,1} je uzavřený interval z reálná čísla [0,1], který obsahuje celočíselné koncové body.[8] Konvexní trup jednotkový kruh je zavřený jednotka disku, který obsahuje jednotkovou kružnici.
Minkowského doplnění

V libovolném vektorovém prostoru (nebo algebraické struktuře s přidáním), , Minkowského součet dvou neprázdných sad je definována jako elementární operace (Viz také.[13])Například
Tato operace je jasně komutativní a asociativní při shromažďování neprázdných sad. Všechny takové operace se rozšiřují přesně definovaným způsobem na rekurzivní formy Podle principu indukce je to snadno vidět[14]
Konvexní slupky minkowských součtů
Minkowského doplněk se chová dobře, pokud jde o převzetí konvexních trupů. Konkrétně pro všechny podskupiny skutečného vektorového prostoru, , konvexní obal jejich Minkowského součtu je Minkowského součet jejich konvexních trupů. To znamená,
A indukcí z toho vyplývá
pro všechny a neprázdné podmnožiny , .[15][16]
Prohlášení

Podle předchozí identity pro každý bod v konvexních trupech jsou prvky, pro , v závislosti na a tak dále .
Lemma ze Shapleye a Folkmana

Práce s výše uvedeným nastavením, Lemma Shapley – Folkman uvádí, že ve výše uvedeném znázornění
nejvíce sčítanců je třeba brát striktně z konvexních trupů. To znamená, že existuje reprezentace výše uvedené formy, taková . Pokud je to nutné, zamíchejte indexy, to znamená, že bod má reprezentaci
kde pro a pro . Všimněte si, že opětovné indexování závisí na bodě.[17] Stručněji to říká lemma Shapley – Folkman
Jako příklad lze uvést každý bod je podle lemmatu součet prvku v a prvek v .[8]
Dimenze reálného vektorového prostoru
Naopak lemma Shapley – Folkman charakterizuje dimenze konečných trojrozměrných reálných vektorových prostorů. To znamená, že pokud se vektorový prostor podřídí lemu Shapley – Folkman pro a přirozené číslo D, a pro žádné číslo menší nežD, pak je jeho rozměr přesněD;[18] lemma Shapley – Folkman platí pouze pro konečně-dimenzionální vektorové prostory.[19]
Věta Shapley – Folkman a důsledek Starra

Shapley a Folkman použili své lemma k prokázání své věty, která ohraničuje vzdálenost mezi Minkowského součtem a jeho konvexním trupem, "konvexní"součet:
- The Věta Shapley – Folkman uvádí, že na druhou Euklidovská vzdálenost z kteréhokoli bodu konvexizovaného součtuKonv. (∑Qn ) na původní (nekonvexní) částku∑ Qn je omezen součtem čtvercůD největší circumradii souborůQn (poloměry nejmenší koule obklopující tyto sady ).[20] Tato vazba je nezávislá na počtu součtových sadN (liN > D).[21]
Věta Shapley – Folkman uvádí hranici na vzdálenost mezi Minkowského součtem a jeho konvexním trupem; tato vzdálenost je nula kdyby a jen kdyby součet je konvexní. Jejich vazba na vzdálenost závisí na dimenziD a na tvarech souřadnic součtu, ale ne na počtu souprav součtůN, když N > D.[3]
Cirkumradius často přesahuje (a nemůže být menší než) vnitřní poloměr:[22]
- The vnitřní poloměr sadyQn je definováno jako nejmenší číslor tak, že pro každý bodq v konvexním trupuQn, tady je koule poloměrur který obsahuje podmnožinuQn jehož konvexní trup obsahujeq.
Starr použil vnitřní poloměr ke snížení horní meze uvedené v Shapley-Folkmanově větě:
- Starrův důsledek k Shapley-Folkmanově větě uvádí, že čtvercová euklidovská vzdálenost od kteréhokoli boduX v konvexním součtuKonv. (∑Qn ) na původní (nekonvexní) částku∑ Qn je omezen součtem čtvercůD největší vnitřní poloměry soupravQn.[22][23]
Starrův důsledek uvádí horní hranice na euklidovské vzdálenosti mezi Minkowského součtemN množiny a konvexní trup Minkowského součtu; tato vzdálenost mezi součtem a jeho konvexním trupem je měřítkem nekonvexnosti množiny. Pro jednoduchost, tato vzdálenost se nazývá „nekonvexnost"množiny (s ohledem na Starrovo měření). Starrovo vázání na nekonvexnost součtu tedy závisí pouze naD největší vnitřní poloměry souprav součtu; Starrova vazba však nezávisí na počtu součtových sadN, kdyžN > DNapříklad vzdálenost mezi konvexním intervalem [0, 2] a nekonvexní množinou {0, 1, 2} se rovná jedné polovině
- 1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.
Takže Starr je vázán na nekonvexnost průměrný
- 1⁄N ∑ Qn
klesá s počtem sčítáníN Zvyšuje se například vzdálenost mezi průměrně soubor
- 1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}
a jeho konvexní trup [0, 1] je pouze 1/4, což je poloviční vzdálenost (1/2) mezi jeho součtem {0, 1} a [0, 1]. Tvary podkolekce pouzeD množinové soupravy určují vazbu na vzdálenost mezi průměrná sada a jeho konvexní trup; tedy, jak se počet sčítání zvyšuje na nekonečno, svázaný klesá na nulu (pro množinové sady rovnoměrně ohraničené velikosti).[3] Ve skutečnosti je Starr vázán na nekonvexnost této průměrné množiny klesá na nulu jako počet sčítáníN zvyšuje na nekonečno (když jsou vnitřní poloměry všech součtů ohraničeny stejným počtem).[3]
Důkazy a výpočty
Původní důkaz lemu Shapley – Folkman stanovil pouze existence zastoupení, ale neposkytl algoritmus pro výpočet reprezentace: Podobné důkazy poskytl Šíp a Hahn,[24] Cassels,[25] a Schneider,[26] mezi ostatními. Abstraktní a elegantní důkaz Ekeland byl rozšířen Artsteinem.[27][28] V nepublikovaných dokumentech se objevily také různé důkazy.[2][29] V roce 1981 zveřejnil Starr iterační metoda pro výpočet reprezentace daného sumárního bodu; jeho výpočetní důkaz však poskytuje slabší mez než původní výsledek.[30] Elementární důkaz o Shapley-Folkmanově lematu v konečně-dimenzionálním prostoru najdete v knize Bertsekas[31]společně s aplikacemi při odhadu rozdílu v dualitě v oddělitelných optimalizačních problémech a hrách s nulovým součtem.
Aplikace
Lemma Shapley – Folkman umožňuje vědcům rozšířit výsledky pro Minkowského součty konvexních množin na součty obecných množin, které nemusí být konvexní. Takové součty množin vznikají v ekonomika, v matematická optimalizace a v teorie pravděpodobnosti; v každé z těchto tří matematických věd je non-konvexita důležitým rysem aplikací.
Ekonomika

v ekonomika, spotřebitel předvolby jsou definovány přes všechny „koše“ zboží. Každý košík je reprezentován jako nezáporný vektor, jehož souřadnice představují množství zboží. Na této sadě košů, an křivka indiference je definován pro každého spotřebitele; křivka lhostejnosti spotřebitele obsahuje všechny koše komodit, které spotřebitel považuje za ekvivalentní: to znamená, že pro každý pár košů na stejné lhostejné křivce spotřebitel neupřednostňuje jeden koš před druhým. Každým košem komodit prochází jedna lhostejná křivka. Spotřebitel sada předvoleb (vzhledem k indiferenční křivce) je svaz indiferenční křivky a všech komoditních košů, které spotřebitel preferuje před indiferenční křivkou. Spotřebitel předvolby jsou konvexní pokud jsou všechny takové sady preferencí konvexní.[32]
Optimální koš zboží nastane tam, kde je rozpočtová položka podporuje sada preferencí spotřebitele, jak je znázorněno na obrázku. To znamená, že optimální koš je na nejvyšší možné křivce indiference dané rozpočtové linii, která je definována z hlediska cenového vektoru a příjmu spotřebitele (nadační vektor). Sada optimálních košů je tedy a funkce cen a tato funkce se nazývá spotřebitel poptávka. Pokud je sada preferencí konvexní, pak je za každou cenu poptávka spotřebitele konvexní sada, například jedinečný optimální koš nebo liniový segment košů.[33]
Konvexní preference

Pokud je však sada předvoleb nekonvexní, pak některé ceny určují rozpočtovou linii, která podporuje dvě samostatný optimální koše. Například si můžeme představit, že v zoologických zahradách lev stojí tolik jako orel, a dále, že rozpočet zoo postačuje pro jednoho orla nebo jednoho lva. Můžeme také předpokládat, že chovatel zoo považuje každé zvíře za stejně cenné. V tomto případě by zoo zakoupila buď jednoho lva nebo jednoho orla. Současný chovatel zoo samozřejmě nechce koupit polovinu orla a polovinu lva (nebo a griffin )! Preference chovatele zoo tedy nejsou konvexní: chovatel zoologické zahrady dává přednost tomu, aby měl kterékoli zvíře před jakoukoli striktně konvexní kombinací obou.[34]
Pokud sada preferencí spotřebitele není konvexní, pak (u některých cen) poptávka spotřebitele není připojeno; odpojená poptávka implikuje určité diskontinuální chování spotřebitele, jak je popsáno v Harold Hotelling:
Pokud si lze představit, že indiferenční křivky pro nákupy mají zvlněný charakter, v některých regionech konvexní vůči původu a v jiných konkávní, jsme nuceni dospět k závěru, že za důležitou lze považovat pouze části konvexní k původu , protože ostatní jsou v zásadě nepozorovatelní. Mohou být detekovány pouze diskontinuitami, které se mohou vyskytnout v poptávce se změnami cenových poměrů, což vede k náhlému skoku bodu tečnosti přes propast, když se přímka otáčí. Ale i když takové diskontinuity mohou odhalit existenci propastí, nikdy nemohou měřit jejich hloubku. Konkávní části lhostejných křivek a jejich vícerozměrné zobecnění, pokud existují, musí navždy zůstat nezměřitelnou neznámou.[35]
Obtíže při studiu nekonvexních preferencí byly zdůrazněny Herman Wold[36] a znovu Paul Samuelson, který napsal, že nekonvexity jsou „zahaleny věčností tma ... ",[37] podle Diewerta.[38]
Nicméně konvexní preference byly osvětleny od roku 1959 do roku 1961 sledem článků v The Journal of Political Economy (JPE). Hlavními přispěvateli byli Farrell,[39] Bator,[40] Koopmans,[41] a Rothenberg.[42] Zejména Rothenbergův článek pojednával o přibližné konvexitě součtů nekonvexních množin.[43] Tyto JPE-papíry stimulovaly příspěvek od Lloyd Shapley a Martin Shubik, který zvažoval konvexní preference spotřebitelů a zavedl koncept „přibližné rovnováhy“.[44] The JPE-papíry a papír Shapley – Shubik ovlivnily další představu „kvazi-rovnováhy“, kvůli Robert Aumann.[45][46]
Starrův dokument z roku 1969 a současná ekonomika

Předchozí publikace o nekonvexnost a ekonomika byly shromážděny v anotované bibliografii uživatelem Kenneth Arrow. Dal bibliografii Starr, který byl poté vysokoškolským studentem zapsaným do Arrowova (postgraduálního) pokročilého kurzu matematicko-ekonomické.[47] Ve své studijní práci Starr studoval obecnou rovnováhu umělé ekonomiky, ve které byly nekonvexní preference nahrazeny jejich konvexními trupy. V konvexní ekonomice, za každou cenu, agregátní poptávka byla součtem konvexních slupek požadavků spotřebitelů. Starrovy myšlenky zajímaly matematiky Lloyd Shapley a Jon Folkman, kteří prokázali své stejnojmenný lemma a věta v „soukromé korespondenci“, o čemž informoval Starr v publikaci z roku 1969.[1]
Ve své publikaci z roku 1969 použil Starr teorém Shapley – Folkman – Starr. Starr dokázal, že „konvexovaná“ ekonomika má obecné rovnováhy, které lze těsně přiblížit „kvazi-rovnováha„z původní ekonomiky, když počet agentů převyšuje rozměr zboží: Starr konkrétně dokázal, že existuje alespoň jedna kvazi-rovnováha cenpopt s následujícími vlastnostmi:
- Za ceny každé kvazi-rovnováhypoptsi všichni spotřebitelé mohou vybrat optimální koše (maximálně preferované a splňující jejich rozpočtová omezení).
- Za kvazi-rovnovážné cenypopt v konvexní ekonomice je trh každého zboží v rovnováze: jeho nabídka se rovná jeho poptávce.
- U každé kvazi-rovnováhy ceny „téměř vyčistily“ trhy původní ekonomiky: an horní hranice na vzdálenost mezi Starrovým důsledkem a Shapley-Folkmanovou větou vyplývá mezi množinou rovnováh „konvexované“ ekonomiky a množinou kvazi-rovnováh původní ekonomiky.[48]
Starr to stanovil
„v souhrnu je rozdíl mezi alokací ve fiktivní ekonomice generovaný [převzetím konvexních trupů všech souborů spotřeby a výroby] a určitou alokací v reálné ekonomice omezen způsobem, který je nezávislý na počtu ekonomických agenti. Proto se průměrný agent setkává s odchylkou od zamýšlených akcí, která zmizí ve významu, protože počet agentů jde do nekonečna “.[49]
Po článku Starra z roku 1969 byly výsledky Shapley – Folkman – Starr široce používány v ekonomické teorii. Roger Guesnerie shrnuli své ekonomické důsledky: „Některé klíčové výsledky získané za předpokladu konvexity zůstávají (přibližně) relevantní za okolností, kdy konvexita selže. Například v ekonomikách s velkou stranou spotřeby preferenční nekonvexity nezničí standardní výsledky.“[50] „Odvození těchto výsledků v obecné formě bylo jedním z hlavních úspěchů poválečné ekonomické teorie,“ napsal Guesnerie.[4] Téma nekonvexní množiny v ekonomii bylo studováno mnoha Nositelé Nobelovy ceny: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008) a Paul Samuelson (1970); doplňkové téma konvexní množiny v ekonomii tito laureáti zdůraznili spolu s Leonid Hurwicz, Leonid Kantorovič (1975) a Robert Solow (1987).[51] Výsledky Shapley – Folkman – Starr byly uvedeny v ekonomické literatuře: v mikroekonomie,[52] v teorii obecné rovnováhy,[53][54] v veřejná ekonomika[55] (počítaje v to selhání trhu ),[56] stejně jako v herní teorie,[57] v matematická ekonomie,[58] a v aplikovaná matematika (pro ekonomy).[59][60] Výsledky Shapley – Folkman – Starr také ovlivnily použití ekonomického výzkumu opatření a teorie integrace.[61]
Matematická optimalizace

Lemma Shapley – Folkman bylo použito k vysvětlení, proč je velké minimalizace problémy s nekonvexity lze téměř vyřešit (pomocí iterační metody jejichž důkazy o konvergenci jsou uvedeny pouze pro konvexní problémy ). Lemma Shapley – Folkman podpořilo použití metod konvexní minimalizace u jiných aplikací se součty mnoha funkcí.[62]
Přípravy teorie optimalizace
Nelineární optimalizace spoléhá na následující definice pro funkce:
- Graf(F) = { (X, F(X) ) }
- The epigraf a funkce se skutečnou hodnotou F je množina bodů výše graf

- Epi (F) = { (X, u) : F(X) ≤ u }.
- Funkce se skutečnou hodnotou je definována jako a konvexní funkce pokud je jeho epigraf konvexní množina.[63]
Například kvadratická funkce F(X) = X2 je konvexní, stejně jako absolutní hodnota funkceG(X) = |X|. Nicméně sinusová funkce (na obrázku) je na konvexní interval (0, π).
Problémy s aditivní optimalizací
V mnoha optimalizačních problémech Objektivní funkce f je oddělitelný: to znamená, F je součet mnoho funkce summand, z nichž každá má svůj vlastní argument:
- F(X) = F( (X1, ..., XN) ) = ∑ Fn(Xn).
Například problémy lineární optimalizace jsou oddělitelné. Vzhledem k oddělitelnému problému s optimálním řešením opravíme optimální řešení
- Xmin = (X1, ..., XN)min
s minimální hodnotouF(Xmin). U tohoto oddělitelného problému považujeme také optimální řešení (Xmin, F(Xmin) )k „konvexní problém", kde jsou konvexní trupy převzaty z grafů funkcí součtu. Takovým optimálním řešením je limit posloupnosti bodů v konvexním problému
Samozřejmě, daný optimální bod je součtem bodů v grafech původních součtů a malého počtu konvexních součtů podle Shapley – Folkmanova lematu.
Tuto analýzu publikoval Ivar Ekeland v roce 1974 vysvětlit zdánlivou konvexnost oddělitelných problémů s mnoha souhrny, navzdory nekonvexnosti souhrnných problémů. V roce 1973 mladý matematik Claude Lemaréchal byl překvapen jeho úspěchem s konvexní minimalizace metody na problémy, o nichž se vědělo, že nejsou konvexní; pro minimalizace nelineární problémy, řešení dvojí problém nemusí poskytovat užitečné informace pro řešení prvotního problému, pokud primární problém není konvexní a nevyhovuje omezení kvalifikace. Lemaréchalov problém byl aditivně oddělitelný a každá funkce summand byla nekonvexní; nicméně řešení dvojího problému poskytlo těsné přiblížení optimální hodnotě prvotního problému.[65][5][66] Ekelandova analýza vysvětlila úspěch metod konvexní minimalizace velký a oddělitelný problémy, a to navzdory nekonvexnosti sčítacích funkcí. Ekeland a pozdější autoři tvrdili, že aditivní separovatelnost způsobila přibližně konvexní agregovaný problém, přestože funkce summand byly nekonvexní. Zásadním krokem v těchto publikacích je použití lemu Shapley – Folkman.[5][66][67] Lemma Shapley – Folkman podpořilo použití metod konvexní minimalizace u jiných aplikací se součty mnoha funkcí.[5][6][59][62]
Teorie pravděpodobnosti a míry
Konvexní množiny jsou často studovány teorie pravděpodobnosti. Každý bod v konvexním trupu a (neprázdný ) podmnožinaQ konečně-dimenzionálního prostoru je očekávaná hodnota a jednoduchý náhodný vektor který bere své hodnoty dovnitřQ, jako důsledek Carathéodoryovo lemma. Tedy pro neprázdnou množinuQ, sběr očekávaných hodnot jednoduchého, Q-hodnocení náhodných vektorů se rovnáQje konvexní obal; tato rovnost znamená, že výsledky Shapley – Folkman – Starr jsou užitečné v teorii pravděpodobnosti.[68] V opačném směru poskytuje teorie pravděpodobnosti nástroje k obecnému zkoumání konvexních množin a konkrétně výsledky Shapley – Folkman – Starr.[69] Výsledky Shapley – Folkman – Starr byly široce používány v pravděpodobnostní teorie náhodných množin,[70] například prokázat a zákon velkých čísel,[7][71] A teorém centrálního limitu,[71][72] a a velké odchylky zásada.[73] Tyto důkazy o pravděpodobnostní limitní věty použil výsledky Shapley – Folkman – Starr, aby se vyhnul předpokladu, že všechny náhodné množiny jsou konvexní.
A míra pravděpodobnosti je konečný opatření, a Shapley – Folkmanovo lemma má aplikace v neprobabilní teorii míry, jako jsou teorie objem a ze dne vektorové míry. Lemma Shapley – Folkman umožňuje upřesnění Brunn – Minkowského nerovnost, který ohraničuje objem součtů z hlediska objemů jejich součtových sad.[74] Objem sady je definován v podmínkách Lebesgueovo opatření, který je definován na podmnožinách souboru Euklidovský prostor. V pokročilé teorii opatření bylo k prokázání použito Shapley – Folkmanovo lemma Lyapunovova věta, ve kterém se uvádí, že rozsah a vektorové opatření je konvexní.[75] Zde je tradiční výraz „rozsah"(alternativně," image ") je sada hodnot produkovaných funkcí vektorové opatření je zobecnění opatření s vektorovou hodnotou; například pokudp1 ap2 jsou pravděpodobnostní opatření definováno stejně měřitelný prostor, pak funkce produktu p1 p2 je vektorová míra, kdep1 p2 je definován pro každého událost ω podle
- (p1 p2)(ω)=(p1(ω), p2(ω)).
Lyapunovova věta byla použita v ekonomika,[45][76] v ("bang-bang" ) teorie řízení a v statistická teorie.[77] Lyapunovova věta byla nazývána a kontinuální protějšek lemu Shapley – Folkman,[3] který sám byl nazýván a diskrétní analog Lyapunovovy věty.[78]
Poznámky
- ^ A b C d E Starr (1969)
- ^ A b Howe (1979, str. 1) : Howe, Rogere (3. listopadu 1979). O tendenci k konvexitě vektorového součtu množin (PDF) (Zpráva). Diskusní příspěvky nadace Cowles Foundation. 538. Box 2125 Yale Station, New Haven, CT 06520: Cowlesova nadace pro výzkum v ekonomii, Univerzita Yale. Citováno 1. ledna 2011.CS1 maint: umístění (odkaz)
- ^ A b C d E F Starr (2008)
- ^ A b Guesnerie (1989, str. 138)
- ^ A b C d E (Ekeland 1999, s. 357–359): Příloha Ekelanda, publikovaná v prvním anglickém vydání z roku 1976, dokazuje lemma Shapley – Folkman, které rovněž uznává Lemaréchal experimenty na straně 373.
- ^ A b Bertsekas (1996, s. 364–381) potvrzující Ekeland (1999) na straně 374 a Aubin & Ekeland (1976) na straně 381:
Bertsekas, Dimitri P. (1996). "5.6 Problémy s oddělitelným celočíselným programováním ve velkém měřítku a exponenciální metoda multiplikátorů". Omezená optimalizace a Lagrangeovy multiplikační metody (Dotisk (1982) Academic Press ed.). Belmont, MA: Athena Scientific. str. xiii + 395. ISBN 1-886529-04-3. PAN 0690767.
Bertsekas (1996, s. 364–381) popisuje aplikaci Lagrangian dual metody k plánování z elektrické elektrárny ("problémy se závazky jednotky "), kde se objeví nekonvexnost z důvodu celočíselná omezení:
Bertsekas, Dimitri P.; Lauer, Gregory S .; Sandell, Nils R., Jr.; Posbergh, Thomas A. (leden 1983). „Optimální krátkodobé plánování rozsáhlých energetických systémů“ (PDF). Transakce IEEE na automatickém ovládání. 28 (1): 1–11. doi:10.1109 / tac.1983.1103136. Citováno 2. února 2011. Proceedings of 1981 IEEE Conference on Decision and Control, San Diego, CA, prosinec 1981, str. 432–443.
- ^ A b Artstein & Vitale (1975, s. 881–882): Artstein, Zvi; Vitale, Richard A. (1975). „Silný zákon velkých čísel pro náhodné kompaktní sady“. Annals of Probability. 3 (5): 879–882. doi:10.1214 / aop / 1176996275. JSTOR 2959130. PAN 0385966. Zbl 0313.60012. PE euclid.ss / 1176996275.
- ^ A b C d Carter (2001, str. 94)
- ^ Arrow & Hahn (1980, str. 375)
- ^ A b Rockafellar (1997, str. 10)
- ^ Arrow & Hahn (1980, str. 376), Rockafellar (1997, s. 10–11) a Green & Heller (1981, str. 37)
- ^ Arrow & Hahn (1980, str. 385) a Rockafellar (1997, s. 11–12)
- ^ Schneider (1993, str. xi) a Rockafellar (1997, str. 16)
- ^ Rockafellar (1997, str. 17) a Starr (1997, str. 78)
- ^ Schneider (1993, s. 2–3)
- ^ Arrow & Hahn (1980, str. 387)
- ^ Starr (1969, str. 35–36)
- ^ Schneider (1993, str. 131)
- ^ Schneider (1993, str. 140) připisuje tento výsledek Borwein & O'Brien (1978): Borwein, J. M.; O'Brien, R. C. (1978). Msgstr "Zrušení charakterizuje konvexnost". Nanta Mathematica (Nanyang University). 11: 100–102. ISSN 0077-2739. PAN 0510842.
- ^ Schneider (1993, str. 129)
- ^ Starr (1969, str. 36)
- ^ A b Starr (1969, str. 37)
- ^ Schneider (1993, s. 129–130)
- ^ Arrow & Hahn (1980, s. 392–395)
- ^ Cassels (1975, str. 435–436)
- ^ Schneider (1993, str. 128)
- ^ Ekeland (1999, str. 357–359)
- ^ Artstein (1980, str. 180)
- ^ Anderson, Robert M. (14. března 2005). „1 Věta Shapley – Folkman“ (PDF). Ekonomika 201B: Konvexní preference a přibližné rovnováhy. Berkeley, CA: Ekonomické oddělení, Kalifornská univerzita, Berkeley. s. 1–5. Citováno 1. ledna 2011.
- ^ Starr, Ross M. (1981). "Aproximace bodů konvexního trupu součtu množin podle bodů součtu: Elementární přístup". Journal of Economic Theory. 25 (2): 314–317. doi:10.1016/0022-0531(81)90010-7. PAN 0640201.
- ^ Bertsekas, Dimitri P. (2009). Konvexní teorie optimalizace. Belmont, MA .: Athena Scientific. ISBN 978-1-886529-31-1.
- ^ Mas-Colell (1985, s. 58–61) a Arrow & Hahn (1980, s. 76–79)
- ^ Arrow & Hahn (1980, s. 79–81)
- ^ Starr (1969, str. 26): „Koneckonců, člověk může být lhostejný mezi automobilem a člunem, ale ve většině případů nemůže ani řídit ani plout kombinací půl člunu a půl automobilu.“
- ^ Hotelling (1935, str. 74):Hotelling, Harold (Leden 1935). "Poptávkové funkce s omezeným rozpočtem". Econometrica. 3 (1): 66–78. doi:10.2307/1907346. JSTOR 1907346.
- ^ Wold (1943b.), s. 231 a 239–240): Wold, Hermane (1943b). „Syntéza analýzy čisté poptávkyII". Skandinavisk Aktuarietidskrift [Scandinavian Actuarial Journal]. 26: 220–263. doi:10.1080/03461238.1943.10404737. PAN 0011939.
Wold & Juréen (1953, str. 146): Wold, Herman; Juréen, Lars (ve spolupráci s Woldem) (1953). "8 Některé další aplikace preferenčních polí (str. 129–148)". Analýza poptávky: Studium ekonometrie. Publikace Wiley ve statistice. New York: John Wiley and Sons, Inc., str. Xvi + 358. PAN 0064385.
- ^ Samuelson (1950, str. 359–360):
Samuelson, Paul A. (Listopad 1950). "Problém integrovatelnosti v teorii užitečnosti". Economica. Nová řada. 17 (68): 355–385. doi:10.2307/2549499. JSTOR 2549499. PAN 0043436.Je třeba poznamenat, že jakýkoli bod, kde jsou indiferenční křivky spíše konvexní než konkávní, nelze na konkurenčním trhu pozorovat. Takové body jsou zahaleny věčnou temnotou - pokud ze svého spotřebitele neurobíme monopsonistu a nenecháme ho volit mezi zbožím ležícím na velmi konvexní „rozpočtové křivce“ (podle níž ovlivňuje cenu toho, co kupuje). V tomto případě monopsony bychom mohli odvodit sklon křivky lhostejnosti člověka od sklonu pozorovaného omezení v rovnovážném bodě.
„Věčná temnota“ popisuje peklo John Milton je ztracený ráj, jehož konkávnost je srovnávána s Serbonian Bog v Kniha II, řádky 592–594:
Milton's description of concavity serves as the literary epigraph prefacing chapter seven of Arrow & Hahn (1980, str. 169), "Markets with non-convex preferences and production", which presents the results of Starr (1969).Záliv hluboký jako ten srbský bažina
Betwixt Damiata a hora Casius staré,
Where Armies whole have sunk. - ^ Diewert (1982, pp. 552–553)
- ^ Farrell, M. J. (August 1959). "The Convexity assumption in the theory of competitive markets". The Journal of Political Economy. 67 (4): 371–391. doi:10.1086/258197. JSTOR 1825163.Farrell, M. J. (October 1961a). "On Convexity, efficiency, and markets: A Reply". Journal of Political Economy. 69 (5): 484–489. doi:10.1086/258541. JSTOR 1828538.Farrell, M. J. (October 1961b). "The Convexity assumption in the theory of competitive markets: Rejoinder". Journal of Political Economy. 69 (5): 493. doi:10.1086/258544. JSTOR 1828541.
- ^ Bator, Francis M. (October 1961a). "On convexity, efficiency, and markets". The Journal of Political Economy. 69 (5): 480–483. doi:10.1086/258540. JSTOR 1828537. Bator, Francis M. (October 1961b). "On convexity, efficiency, and markets: Rejoinder". Journal of Political Economy. 69 (5): 489. doi:10.1086/258542. JSTOR 1828539.
- ^ Koopmans, Tjalling C. (October 1961). "Convexity assumptions, allocative efficiency, and competitive equilibrium". The Journal of Political Economy. 69 (5): 478–479. doi:10.1086/258539. JSTOR 1828536.
Koopmans (1961, str. 478) and others—for example, Farrell (1959, pp. 390–391) and Farrell (1961a, str. 484), Bator (1961a, pp. 482–483), Rothenberg (1960, str. 438), and Starr (1969, str. 26)—commented on Koopmans (1957, pp. 1–126, especially 9–16 [1.3 Summation of opportunity sets], 23–35 [1.6 Convex sets and the price implications of optimality], and 35–37 [1.7 The role of convexity assumptions in the analysis]):
Koopmans, Tjalling C. (1957). "Allocation of resources and the price system". v Koopmans, Tjalling C (vyd.). Three essays on the state of economic science. New York: McGraw–Hill Book Company. pp. 1–126. ISBN 0-07-035337-9.
- ^ Rothenberg (1960, str. 447): Rothenberg, Jerome (October 1960). "Non-convexity, aggregation, and Pareto optimality". The Journal of Political Economy. 68 (5): 435–468. doi:10.1086/258363. JSTOR 1830308. (Rothenberg, Jerome (October 1961). "Comments on non-convexity". Journal of Political Economy. 69 (5): 490–492. doi:10.1086/258543. JSTOR 1828540.)
- ^ Arrow & Hahn (1980, str. 182)
- ^ Shapley & Shubik (1966, str. 806): Shapley, L. S.; Shubik, M. (Říjen 1966). "Quasi-cores in a monetary economy with nonconvex preferences". Econometrica. 34 (4): 805–827. doi:10.2307/1910101. JSTOR 1910101. Zbl 0154.45303.
- ^ A b Aumann (1966, pp. 1–2): Aumann, Robert J. (January 1966). "Existence of competitive equilibrium in markets with a continuum of traders". Econometrica. 34 (1): 1–17. doi:10.2307/1909854. JSTOR 1909854. PAN 0191623. Aumann (1966) uses results from Aumann (1964, 1965 ):
Aumann, Robert J. (January–April 1964). "Markets with a continuum of traders". Econometrica. 32 (1–2): 39–50. doi:10.2307/1913732. JSTOR 1913732. PAN 0172689.
Aumann, Robert J. (August 1965). "Integrals of set-valued functions". Journal of Mathematical Analysis and Applications. 12 (1): 1–12. doi:10.1016/0022-247X(65)90049-1. PAN 0185073.
- ^ Taking the convex hull of non-convex preferences had been discussed earlier by Wold (1943b, str. 243) and by Wold & Juréen (1953, str. 146), according to Diewert (1982, str. 552).
- ^ A b Starr & Stinchcombe (1999, pp. 217–218): Starr, R. M.; Stinchcombe, M. B. (1999). "Exchange in a network of trading posts". v Chichilnisky, Graciela (vyd.). Markets, information and uncertainty: Essays in economic theory in honor of Kenneth J. Arrow. Cambridge: Cambridge University Press. pp. 217–234. doi:10.2277/0521553555. ISBN 978-0-521-08288-4.
- ^ Arrow & Hahn (1980, pp. 169–182). Starr (1969, pp. 27–33)
- ^ Green & Heller (1981, str. 44)
- ^ Guesnerie (1989, pp. 99)
- ^ Mas-Colell (1987)
- ^ Varian (1992, pp. 393–394): Varian, Hal R. (1992). "21.2 Convexity and size". Microeconomic Analysis (3. vyd.). W. W. Norton & Company. ISBN 978-0-393-95735-8. PAN 1036734.
Mas-Colell, Whinston & Green (1995, pp. 627–630): Mas-Colell, Andreu; Whinston, Michael D .; Green, Jerry R. (1995). "17.1 Large economies and nonconvexities". Microeconomic theory. Oxford University Press. ISBN 978-0-19-507340-9.
- ^ Arrow & Hahn (1980, pp. 169–182)
Mas-Colell (1985, pp. 52–55, 145–146, 152–153, and 274–275): Mas-Colell, Andreu (1985). "1.L Averages of sets". The Theory of general economic equilibrium: A rozlišitelný přístup. Econometric Society monographs. 9. Cambridge University Press. ISBN 0-521-26514-2. PAN 1113262.
Hildenbrand (1974, pp. 37, 115–116, 122, and 168): Hildenbrand, Werner (1974). Core and equilibria of a large economy. Princeton studies in mathematical economics. 5. Princeton, N.J .: Princeton University Press. pp. viii+251. ISBN 978-0-691-04189-6. PAN 0389160.
- ^ Starr (1997, str. 169): Starr, Ross M. (1997). "8 Convex sets, separation theorems, and non-convex sets in RN (new chapters 22 and 25–26 in (2011) second ed.)". General equilibrium theory: An introduction (První vydání). Cambridge: Cambridge University Press. pp. xxiii+250. ISBN 0-521-56473-5. PAN 1462618.
Ellickson (1994, pp. xviii, 306–310, 312, 328–329, 347, and 352): Ellickson, Bryan (1994). Competitive equilibrium: Theory and applications. Cambridge University Press. doi:10.2277/0521319889. ISBN 978-0-521-31988-1.
- ^ Laffont, Jean-Jacques (1988). "3. Nonconvexities". Fundamentals of public economics. MIT Lis. str. 63–65. ISBN 0-262-12127-1.
- ^ Salanié (2000, pp. 112–113 and 107–115): Salanié, Bernard (2000). "7 Nonconvexities". Microeconomics of market failures (English translation of the (1998) French Microéconomie: Les défaillances du marché (Economica, Paris) ed.). Cambridge, MA: MIT Press. pp. 107–125. ISBN 0-262-19443-0.
- ^ Ichiishi (1983, pp. 24–25): Ichiishi, Tatsuro (1983). Game theory for economic analysis. Economic theory, econometrics, and mathematical economics. New York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. x+164. ISBN 0-12-370180-5. PAN 0700688.
- ^ Cassels (1981, pp. 127 and 33–34): Cassels, J. W. S. (1981). "Appendix A Convex sets". Economics for mathematicians. London Mathematical Society lecture note series. 62. Cambridge, New York: Cambridge University Press. pp. xi+145. ISBN 0-521-28614-X. PAN 0657578.
- ^ A b Aubin (2007, pp. 458–476): Aubin, Jean-Pierre (2007). "14.2 Duality in the case of non-convex integral criterion and constraints (especially 14.2.3 The Shapley–Folkman theorem, pages 463–465)". Mathematical methods of game and economic theory (Reprint with new preface of 1982 North-Holland revised English ed.). Mineola, NY: Dover Publications, Inc. pp. xxxii+616. ISBN 978-0-486-46265-3. PAN 2449499.
- ^ Carter (2001, pp. 93–94, 143, 318–319, 375–377, and 416)
- ^ Trockel (1984, str. 30): Trockel, Walter (1984). Market demand: An analysis of large economies with nonconvex preferences. Lecture Notes in Economics and Mathematical Systems. 223. Berlín: Springer-Verlag. pp. viii+205. ISBN 3-540-12881-6. PAN 0737006.
- ^ A b Bertsekas (1999, str. 496): Bertsekas, Dimitri P. (1999). "5.1.6 Separable problems and their geometry". Nonlinear Programming (Druhé vydání.). Cambridge, MA.: Athena Scientific. pp. 494–498. ISBN 1-886529-00-0.
- ^ Rockafellar (1997, str. 23)
- ^ The limit of a sequence je členem closure of the original set, which is the smallest uzavřená sada that contains the original set. The Minkowski sum of two closed sets need not be closed, so the following zařazení can be strict
- Clos(P) + Clos(Q) ⊆ Clos( Clos(P) + Clos(Q) );
- ^ Lemaréchal (1973, str. 38): Lemaréchal, Claude (April 1973). Utilisation de la dualité dans les problémes non convexes [Use of duality for non–convex problems] (Report) (in French). Domaine de Voluceau, Rocquencourt, 78150 Le Chesnay, Francie: IRIA (now INRIA), Laboratoire de recherche en informatique et automatique. p. 41.CS1 maint: umístění (odkaz). Lemaréchal's experiments were discussed in later publications:
Aardal (1995, pp. 2–3): Aardal, Karen (Březen 1995). "Optima interview Claude Lemaréchal" (PDF). Optima: Mathematical Programming Society Newsletter. 45: 2–4. Citováno 2. února 2011.
Hiriart-Urruty & Lemaréchal (1993, pp. 143–145, 151, 153, and 156): Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "XII Abstract duality for practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlín: Springer-Verlag. pp. 136–193 (and bibliographical comments on pp. 334–335). ISBN 3-540-56852-2. PAN 1295240.
- ^ A b Ekeland, Ivar (1974). "Une estimation a priori en programmation non convexe". Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Séries A et B (in French). 279: 149–151. ISSN 0151-0509. PAN 0395844.
- ^ Aubin & Ekeland (1976, pp. 226, 233, 235, 238, and 241): Aubin, J. P.; Ekeland, I. (1976). "Estimates of the duality gap in nonconvex optimization". Mathematics of Operations Research. 1 (3): 225–245. doi:10.1287/moor.1.3.225. JSTOR 3689565. PAN 0449695.
Aubin & Ekeland (1976) a Ekeland (1999, pp. 362–364) also considered the konvexní uzavření of a problem of non-convex minimization—that is, the problem defined as the Zavřeno konvexní trup z epigraf of the original problem. Their study of duality gaps was extended by Di Guglielmo to the quasiconvex closure of a non-convex minimalizace problem—that is, the problem defined as the Zavřeno konvexní trup z dolní level sets:
Di Guglielmo (1977, pp. 287–288): Di Guglielmo, F. (1977). "Nonconvex duality in multiobjective optimization". Mathematics of Operations Research. 2 (3): 285–291. doi:10.1287/moor.2.3.285. JSTOR 3689518. PAN 0484418.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Schneider & Weil (2008, str. 45): Schneider, Rolf; Weil, Wolfgang (2008). Stochastic and integral geometry. Probability and its applications. Springer. doi:10.1007/978-3-540-78859-1. ISBN 978-3-540-78858-4. PAN 2455326.
- ^ Cassels (1975, pp. 433–434): Cassels, J. W. S. (1975). "Measures of the non-convexity of sets and the Shapley–Folkman–Starr theorem". Mathematical Proceedings of the Cambridge Philosophical Society. 78 (3): 433–436. doi:10.1017/S0305004100051884. PAN 0385711.
- ^ Molchanov (2005, pp. 195–198, 218, 232, 237–238 and 407): Molchanov, Ilya (2005). "3 Minkowski addition". Theory of random sets. Probability and its applications. London: Springer-Verlag London Ltd. pp.194 –240. doi:10.1007/1-84628-150-4. ISBN 978-1-84996-949-9. PAN 2132405.
- ^ A b Puri & 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. Bibcode:1985MPCPS..97..151P. doi:10.1017/S0305004100062691. PAN 0764504.
- ^ Weil (1982, pp. 203, and 205–206): Weil, Wolfgang (1982). "An application of the central limit theorem for Banach-space–valued random variables to the theory of random sets". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete [Probability Theory and Related Fields]. 60 (2): 203–208. doi:10.1007/BF00531823. PAN 0663901.
- ^ Cerf (1999, pp. 243–244): Cerf, Raphaël (1999). "Large deviations for sums of i.i.d. random compact sets". Proceedings of the American Mathematical Society. 127 (8): 2431–2436. doi:10.1090/S0002-9939-99-04788-7. PAN 1487361. Cerf uses applications of the Shapley–Folkman lemma from Puri & Ralescu (1985, pp. 154–155).
- ^ Ruzsa (1997, str. 345): Ruzsa, Imre Z. (1997). "The Brunn–Minkowski inequality and nonconvex sets". Geometriae Dedicata. 67 (3): 337–348. doi:10.1023/A:1004958110076. PAN 1475877.
- ^ Tardella (1990, pp. 478–479): Tardella, Fabio (1990). "A new proof of the Lyapunov convexity theorem". SIAM Journal on Control and Optimization. 28 (2): 478–481. doi:10.1137/0328026. PAN 1040471.
- ^ Vind (1964, pp. 168 and 175): Vind, Karl (May 1964). "Edgeworth-allocations in an exchange economy with many traders". International Economic Review. 5 (2): 165–77. doi:10.2307/2525560. JSTOR 2525560. Vind's article was noted by the winner of the 1983 Nobelova cena za ekonomii, Gérard Debreu. Debreu (1991, str. 4) wrote:
The concept of a convex set (i.e., a set containing the segment connecting any two of its points) had repeatedly been placed at the center of economic theory before 1964. It appeared in a new light with the introduction of integration theory in the study of economic competition: If one associates with every agent of an economy an arbitrary set in the commodity space and if one averages those individual sets over a collection of insignificant agents, then the resulting set is necessarily convex. [Debreu appends this footnote: "On this direct consequence of a theorem of A. A. Lyapunov, see Vind (1964)."] But explanations of the ... functions of prices ... can be made to rest on the convexity of sets derived by that averaging process. Konvexnost in the commodity space obtained by aggregation over a collection of insignificant agents is an insight that economic theory owes ... to integration theory. [Italics added]
Debreu, Gérard (March 1991). "The Mathematization of economic theory". The American Economic Review. 81 (Presidential address delivered at the 103rd meeting of the American Economic Association, 29 December 1990, Washington, DC): 1–7. JSTOR 2006785.
- ^ Artstein (1980, pp. 172–183) Artstein (1980) was republished in a slavnostní svátek pro Robert J. Aumann, winner of the 2008 Nobelova cena za ekonomii: Artstein, Zvi (1995). "22 Discrete and continuous bang–bang and facial spaces or: Look for the extreme points". In Hart, Sergiu; Neyman, Abraham (eds.). Game and economic theory: Selected contributions in honor of Robert J. Aumann. Ann Arbor, MI: University of Michigan Press. pp. 449–462. ISBN 0-472-10673-2. Archivovány od originál on 24 May 2011.
- ^ Mas-Colell (1978, str. 210): Mas-Colell, Andreu (1978). "A note on the core equivalence theorem: How many blocking coalitions are there?". Journal of Mathematical Economics. 5 (3): 207–215. doi:10.1016/0304-4068(78)90010-1. PAN 0514468.
Reference
- Arrow, Kenneth J.; Hahn, Frank H. (1980) [1971]. General competitive analysis. Advanced Textbooks in Economics. 12 (reprint of San Francisco, CA: Holden-Day, Inc. Mathematical Economics Texts 6 vyd.). Amsterdam: Severní Holandsko. ISBN 0-444-85497-5. PAN 0439057.
- Artstein, Zvi (1980). "Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points". Recenze SIAM. 22 (2): 172–185. doi:10.1137/1022026. JSTOR 2029960. PAN 0564562.
- Carter, Michael (2001). Foundations of mathematical economics. Cambridge, MA: MIT Press. pp. xx+649. ISBN 0-262-53192-5. PAN 1865841. (Web autora s answers to exercises ). Archivovány od originál on 15 September 2006.
- Diewert, W. E. (1982). "12 Duality approaches to microeconomic theory". v Arrow, Kenneth Joseph; Intriligator, Michael D (eds.). Handbook of mathematical economics, Volume II. Handbooks in Economics. 1. Amsterdam: North-Holland Publishing Co. pp. 535–599. doi:10.1016/S1573-4382(82)02007-4. ISBN 978-0-444-86127-6. PAN 0648778.
- Ekeland, Ivar (1999) [1976]. "Appendix I: An a priori estimate in convex programming". In Ekeland, Ivar; Temam, Roger (eds.). Convex analysis and variational problems. Classics in Applied Mathematics. 28 (Corrected reprinting of the North-Holland ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). pp. 357–373. ISBN 0-89871-450-8. PAN 1727362.
- Green, Jerry; Heller, Walter P. (1981). "1 Mathematical analysis and convexity with applications to economics". v Arrow, Kenneth Joseph; Intriligator, Michael D (eds.). Handbook of mathematical economics, Volume Já. Handbooks in Economics. 1. Amsterdam: North-Holland Publishing Co. pp. 15–52. doi:10.1016/S1573-4382(81)01005-9. ISBN 0-444-86126-2. PAN 0634800.
- Guesnerie, Roger (1989). "First-best allocation of resources with nonconvexities in production". In Cornet, Bernard; Tulkens, Henry (eds.). Contributions to Operations Research and Economics: The twentieth anniversary of CORE (Papers from the symposium held in Louvain-la-Neuve, January 1987). Cambridge, MA: MIT Press. pp. 99–143. ISBN 0-262-03149-3. PAN 1104662.
- Mas-Colell, A. (1987). "Non-convexity". v Eatwell, John; Milgate, Murray; Newman, Peter (eds.). The new Palgrave: A dictionary of economics (první vydání). Palgrave Macmillan. pp. 653–661. doi:10.1057/9780230226203.3173. ISBN 9780333786765. (PDF file at Mas-Colell's homepage ).
- Rockafellar, R. Tyrrell (1997). Convex analysis. Princeton Landmarks in Mathematics. Princeton, NJ: Princeton University Press. pp. xviii+451. ISBN 0-691-01586-4. PAN 1451876.. Reprint of the 1970 (PAN274683 ) Princeton Mathematical Series 28
- Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of Mathematics and its Applications. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN 0-521-35220-7. PAN 1216521.
- Starr, Ross M. (1969). "Quasi-equilibria in markets with non-convex preferences (Appendix 2: The Shapley–Folkman theorem, pp. 35–37)". Econometrica. 37 (1): 25–38. doi:10.2307/1909201. JSTOR 1909201.
- Starr, Ross M. (2008). "Shapley–Folkman theorem". v Durlauf, Steven N.; Blume, Lawrence E (eds.). The new Palgrave dictionary of economics (Druhé vydání.). Palgrave Macmillan. pp. 317–318 (1st ed.). doi:10.1057/9780230226203.1518. ISBN 978-0-333-78676-5.
externí odkazy
- Anderson, Robert M. (March 2005). "1 The Shapley–Folkman theorem" (PDF). Economics 201B: Nonconvex preferences and approximate equilibria. Berkeley, CA: Economics Department, University of California, Berkeley. pp. 1–5. Citováno 15. ledna 2011.
- Howe, Roger (Listopad 1979). On the tendency toward convexity of the vector sum of sets (PDF) (Zpráva). Cowles Foundation discussion papers. 538. Box 2125 Yales Station, New Haven, CT 06520: Cowles Foundation for Research in Economics, Yale University. Citováno 15. ledna 2011.CS1 maint: umístění (odkaz)
- Starr, Ross M. (Září 2009). "8 Convex sets, separation theorems, and non-convex sets in RN (Section 8.2.3 Measuring non-convexity, the Shapley–Folkman theorem)" (PDF). General equilibrium theory: An introduction. pp. 3–6. doi:10.1017/CBO9781139174749. ISBN 9781139174749. PAN 1462618. (Draft of second edition, from Starr's course at the Economics Department of the University of California, San Diego).
- Starr, Ross M. (Květen 2007). "Shapley–Folkman theorem" (PDF). s. 1–3. (Draft of article for the second edition of New Palgrave Dictionary of Economics). Citováno 15. ledna 2011.