Λήμμα των Σάπλεϊ-Φόλκμαν: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε

Ενδογραμμικά

Έκδοση από την 16:26, 25 Ιουνίου 2014

Το λήμμα των Σάπλεϊ- Φόλκμαν είναι αποτέλεσμα της κυρτής γεωμετρίας με εφαρμογές στα οικονομικά μαθηματικά που περιγράφει την προσθήκη συνόλων του Μινικόφσκι σε ένα διανυσματικό χώρο. Η προσθήκη του Μινικόφσκι ορίζεται ως η πρόσθεση συνόλων, για παράδειγμα, προσθέτοντας το σύνολο που αποτελείται από τους ακέραιους μηδέν και ένα που αποδίδονται στον εαυτό τους και αποτελείται από μηδέν, ένα και δύο:

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

Το λήμμα των Σάπλεϊ- Φόλκμαν και τα σχετικά αποτελέσματα παρέχουν μια καταφατική απάντηση στο ερώτημα, "Είναι το άθροισμα των πολλών συνόλων κοντά στο να είναι κυρτό?"^[2] Ένα σύνολο ορίζεται να είναι κυρτό αν κάθε ευθύγραμμο τμήμα που ενώνει δύο σημεία της είναι υποσύνολο του συνόλου. Για παράδειγμα, ο στερεός δίσκος $\bullet$ είναι ένα κυρτό σύνολο, αλλά ο κύκλος $\circ$ δεν είναι, γιατί το τμήμα της γραμμής που συνδέει δύο διακριτά σημεία $\oslash$ δεν είναι ένα υποσύνολο του κύκλου. Το λήμμα των Σάπλεϊ- Φόλκμαν υποδηλώνει ότι αν ο αριθμός των συνόλων που αθροίζονται υπερβαίνει τη διάσταση του διανύσματος του χώρου, τότε το Μινικόφσκι άθροισμά τους είναι περίπου κυρτή.^[1]

Το λήμμα των Σάπλεϊ- Φόλκμαν εισήχθη ως ένα βήμα προς την απόδειξη του θεωρήματος των Σάπλεϊ- Φόλκμαν, το οποίο ορίζει ένα ανώτατο όριο για την Ευκλείδεια απόσταση μεταξύ του αθροίσματος Μινικόφσκι και το κυρτό του κύτους τους. Το κυρτό περίβλημα ενός συνόλου Q είναι το μικρότερο κυρτό σύνολο που περιέχει την Q. Αυτή η απόσταση είναι μηδέν αν και μόνο αν το άθροισμα είναι κυρτό. Το θεώρημα του δεσμευμένου εξαρτάται από την διάσταση D και τα σχήματα των summand-συνόλων, αλλά όχι από τον αριθμό των συνόλων summand-Ν, όταν τοwhen N > D. Τα σχήματα ενός μοναδικού υποσυνόλου ϋ summand καθορίζουν την δεσμευμένη απόσταση μεταξύ του μέσου όρου των Ν Μινοκόφσκι συνόλων

¹⁄_N (Q₁ + Q₂ + ... + Q_N)

και το κυρτό του κύτους του. Όσο το Ν πηγαίνει στο άπειρο, τα δεσμευμένα [[limit of a sequence|μειώνεται στο μηδέν] (για summand-σύνολα ομοιόμορφα και φραγμένου μεγέθους). ^[3] Το πάνω όριο του θεωρήματος των Σάπλεϊ- Φόλκμαν μειώθηκε από πόρισμα του Σταρ (εναλλακτικά, το θεώρημα Shapley-Folkman-Starr).

Το λήμμα των Λόιντ Σάπλει και Τζον Φόλκμαν δημοσιεύθηκε για πρώτη φορά από τον οικονομολόγο Ross M. Starr, ο οποίος ερευνούσε την ύπαρξη οικονομικής ισορροπίας ενώ σπούδαζε με τον Κένεθ Άροου. ^[1] Στο έγγραφό του, ο Σταρ μελέτησε την κυρτή μορφή της οικονομίας, όπου τα μη- κυρτά σύνολα αντικαταστάθηκαν από αντίστοιχα κυρτά˙ Ο Σταρ απέδειξε ότι η οικονομία έχει κυρτές ισορροπίες που προσεγγίζονται από τους "οιωνούς ισορροπίας" της αρχικής οικονομίας. Επιπλέον, αποδείχθηκε ότι κάθε οιωνός ισορροπίας έχει πολλές από τις καλύτερες δυνατές ιδιότητες της αληθινής ισορροπίας, τα οποία αποδείχθηκαν ότι υπάρχουν για κυρτές οικονομίες. Μετά την έκθεση του Σταρ το 1969, τα αποτελέσματα των Σάπλει- Φόλκμαν- Σταρ έχουν χρησιμοποιηθεί ευρέως για να δείξουν ότι τα βασικά αποτελέσματα των (κυρτών) οικονομικών θεωριών είναι καλής προσεγγίσεις σε μεγάλες οικονομίες μη κυρτές, για παράδειγμα, οιωνοί ισορροπίας σε στενή προσέγγιση ισορροπίας μίας κυρτής οικονομίας. «Η παραγωγή αυτών των αποτελεσμάτων σε γενική μορφή υπήρξε ένα από τα σημαντικότερα επιτεύγματα της μεταπολεμικής οικονομικής θεωρίας», έγραψε ο Roger Guesnerie. ^[4] Το θέμα των μη κυρτών συνόλων στα οικονομικά έχει μελετηθεί από πολλούς νομπελίστες, εκτός από τον Λόιντ Σάπλει που κέρδισε το βραβείο το 2012: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008),και Paul Samuelson (1970. Το συμπληρωματικό θέμα των κυρτών συνόλων στα οικονομικά έχει τονιστεί από τους βραβευθέντες, μαζί με τους Leonid Hurwicz, Leonid Kantorovich (1975), and Robert Solow (1987).

Το λήμμα των Σάπλεϊ- Φόλκμαν έχει εφαρμογές στη βελτιστοποίηση και στη θεωρία πιθανοτήτων. ^[3] Στη θεωρία βελτιστοποίησης, το λήμμα των Σάπλεϊ- Φόλκμαν έχει χρησιμοποιηθεί για να εξηγήσει την επιτυχή επίλυση των προβλημάτων ελαχιστοποίησης που είναι αποτέλεσμα πολλών συναρτήσεων. ^[5]^[6] Το λήμμα των Σάπλεϊ- Φόλκμαν έχει επίσης χρησιμοποιηθεί στις αποδείξεις των «νόμος των μέσων όρων" για τυχαία σύνολα, ένα θεώρημα που είχε αποδειχθεί μόνο για τα κυρτά σύνολα. ^[7]

Εισαγωγικό παράδειγμα

Για παράδειγμα, το υποσύνολο των ακεραίων {0, 1, 2} περιέχεται στο διάστημα των πραγματικών αριθμών [0, 2], το οποίο είναι κυρτό. Το λήμμα των Σάπλεϊ- Φόλκμαν συνεπάγεται ότι κάθε σημείο [0, 2] είναι το άθροισμα ενός ακέραιος από {0, 1} και ένος πραγματικού αριθμού από [0, 1].name="Carter94" >Carter (2001, p. 94)</ref>

Η απόσταση μεταξύ του κυρτού διαστήματος [0, 2], και του μη κυρτού συνόλου {0, 1, 2} ισούται με ένα και ένα δεύτερο

1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

Ωστόσο, η απόσταση μεταξύ του μέσου αθροίσματος Μινικόφσκι

1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}

και του κυρτού κύτους του [0, 1] είναι μόνο το 1/4, το οποίο είναι το μισό της απόστασης (1/2) μεταξύ summand του {0, 1} και [0, 1]. Καθώς προστίθενται μαζί περισσότερες σειρές, ο μέσος όρος του αθροίσματος τους "συμπληρώνει" το κυρτό του κύτους του. Η μέγιστη απόσταση μεταξύ του μέσου όρου και του κυρτού του κύτους του πλησιάζει το μηδέν, ο μέσος όρος περιλαμβάνει περισσότερα summands.^[8]

Προκαταρκτικά

Το λήμμα των Σάπλεϊ- Φόλκμαν εξαρτάται από τους ακόλουθους ορισμούς και τα αποτελέσματα από την κυρτή γεωμετρία.

Πραγματικοί διανυσματικοί χώροι

Ένας πραγματικός διανυσματικός χώρος των δύο διαστάσεων μπορεί να δοθεί σε ένα καρτεσιανό σύστημα συντεταγμένων στο οποίο κάθε σημείο προσδιορίζεται από ένα διατεταγμένο ζεύγος πραγματικών αριθμών, που ονομάζεται «συντεταγμένες», οι οποίες συνήθως συμβολίζονται με x και y. Δύο σημεία στο καρτεσιανό επίπεδο μπορούν να προστεθούν ως συντεταγμένες

(x₁, y₁) + (x₂, y₂) = (x₁+x₂, y₁+y₂)

Επίσης, ένα σημείο μπορεί να πολλαπλασιαστεί από κάθε πραγματικό αριθμό λ συντεταγμένων

λ (x, y) = (λx, λy).

Γενικότερα, κάθε πραγματικός διανυσματικός χώρος (πεπερασμένος) διάστασης D μπορεί να θεωρηθεί ως το σύνολο όλων των D-πλειάδων D πραγματικών αριθμών { (v₁, v₂, . . . , v_D) } για την οποία ορίζονται δύο πράξεις: πρόσθεση φορέα και πολλαπλασιασμό με έναν πραγματικό αριθμό. Για πεπερασμένης διάστασης διανυσματικούς χώρους, οι πράξεις της πρόσθεσης φορέα και σε πραγματικό αριθμό πολλαπλασιασμού μπορούν να οριστούν, ακολουθώντας το παράδειγμα του καρτεσιανού επιπέδου.^[9]

Κυρτά σύνολα

Σε ένα κυρτό σύνολο Q, το ευθύγραμμο τμήμα που συνδέει δύο οποιαδήποτε από τα σημεία του είναι ένα υποσύνολο του Q.

Σε ένα μη-κυρτό σύνολο Q, ένα σημείο σε κάποιο ευθύγραμμο τμήμα που ενώνει δύο από τα σημεία του δεν είναι μέλος της Q.

Τα ευθύγραμμα τμήματα ελέγχουν αν ένα υποσύνολο να είναι κυρτό.

Σε ένα πραγματικό διανυσματικό διάστημα, ένα μη-κενό σύνολο Q ορίζεται να είναι κυρτό αν, για κάθε ζεύγος από τα σημεία του, κάθε σημείο στο ευθύγραμμο τμήμα που τα ενώνει είναι ένα υποσύνολο του Q. Για παράδειγμα, ένας στερεός δίσκος $\bullet$ είναι κυρτός, αλλά ένας κύκλος $\circ$ δεν είναι, διότι δεν περιέχει ένα τμήμα της γραμμής που ενώνει τα σημεία του $\oslash$ , το μη κυρτό σύνολο τριών ακεραίων {0, 1, 2} περιέχεται στο διάστημα [0, 2], το οποίο είναι κυρτό. Για παράδειγμα, ένας στερεός κύβος είναι κυρτός. Ωστόσο, κάτι που είναι κοίλο ή χτυπημένο, για παράδειγμα, ένα ημισελήνο σχήμα , είναι μη κυρτά. Το κενό σύνολο είναι κυρτό, είτε εξ ορισμού ^[10] ή κενό, ανάλογα με το συγγραφέα.

Δηλαδή, ένα σύνολο Q είναι κυρτό αν, για όλα τα σημεία v₀ και v₁ στο Q και για κάθε πραγματικό αριθμό λ στο διάστημα [0,1], το σημείο

(1 − λ) v₀ + λv₁

είναι μέλος της Q.

Με μαθηματική επαγωγή, ένα σύνολο Q είναι κυρτό αν και μόνο αν κάθε κυρτός συνδυασμός των μελών της Q ανήκει επίσης στην Q. Εξ ορισμού, ένας κυρτός συνδυασμός ενός αναπροσαρμοσμένου υποσύνολο {v₀, v₁, . . . , v_D} του διανυσματικού χώρου είναι κάθε σταθμισμένος μέσος όρος λ₀v₀ + λ₁v₁ + . . . + λ_Dv_D,

για κάποιο δείκτη σύνολο των μη αρνητικών πραγματικών αριθμών {λ_d} που ικανοποιεί την εξίσωση

λ₀ + λ₁ + . . . + λ_D = 1.^[11]

Ο ορισμός ενός κυρτού συνόλου συνεπάγεται ότι το σημείο τομής των δύο κυρτών συνόλων είναι ένα κυρτό σύνολο. Γενικότερα, η τομή μιας οικογένειας κυρτών συνόλων είναι ένα κυρτό σύνολο. Ειδικότερα, η τομή δύο διακριτών συνόλων είναι το κενό σύνολο, το οποίο είναι κυρτό. ref name="Rock10" >Rockafellar (1997, p. 10)</ref>

Κυρτό κύτους

Για κάθε υποσύνολο Q ενός πραγματικού διανυσματικού χώρου, είναι κυρτό κύτους του Conv(Q) και μάλιστα είναι το ελάχιστο κυρτό σύνολο που περιέχει το Q. Έτσι Conv(Q) είναι η τομή όλων των κυρτών συνόλων που καλύπτουν το Q.Το κυρτό περίβλημα ενός συνόλου μπορεί ισοδύναμα να ορίζεται να είναι το σύνολο όλων των κυρτών συνδυασμών σημείων στο Q. ^[12] Για παράδειγμα, το κυρτό του κύτους του συνόλου των ακεραίων {0,1} είναι το κλειστό διάστημα των πραγματικών αριθμών [0,1], το οποίο περιέχει τον ακέραιο αριθμό τελικών σημείων. ^[8] Το κυρτό κύτους του μοναδιαίου κύκλου είναι ο δίσκος που περιέχει τον μοναδιαίο κύκλο.

Προσθήκη Μινικόφσκι

Σε έναν πραγματικό διανυσματικό χώρο, το άθροισμα Μινικόφσκι δύο (μη κενών) συνόλων Q₁ και Q₂ ορίζεται να είναι το σύνολο Q₁ + Q₂ που σχηματίζεται με την προσθήκη των στοιχείων από τα σύνολα summand

Q₁ + Q₂ = { q₁ + q₂ : q₁ ∈ Q₁ and q₂ ∈ Q₂ }.^[13]

Για παράδειγμα

{0, 1} + {0, 1} = {0+0, 0+1, 1+0, 1+1} = {0, 1, 2}.^[8] Με την αρχή της μαθηματικής επαγωγής, το άθροισμα Μινικόφσκι μιας πεπερασμένης οικογένειας (μη κενών) συνόλων

{Q_n : Q_n ≠ Ø and 1 ≤ n ≤ N }

είναι το σύνολο που σχηματίζεται από τα στοιχεία προσθήκης των διανυσμάτων

∑ Q_n = {∑ q_n : q_n ∈ Q_n}.^[14]

Κυρτό άθροισμα Μινικόφσκι

Το άθροισμα Minkowski συμπεριφέρεται καλά σε σχέση με την "κυρτοποίηση"-η λειτουργία της λήψης κυρτών. Συγκεκριμένα, για όλα τα υποσύνολα Q₁ και Q₂ ενός πραγματικού διανυσματικού χώρου, το κυρτό του κύτους του αθροίσματος Μινικόφσκι είναι το άθροισμα Μινικόφσκι των κυρτών τους. Δηλαδή,

Conv( Q₁ + Q₂ ) = Conv( Q₁ ) + Conv( Q₂ ).

Αυτό το αποτέλεσμα ισχύει γενικότερα, ως συνέπεια της αρχής της μαθηματικής επαγωγής. Για κάθε πεπερασμένη συλλογή των συνόλων,

Conv( ∑ Q_n ) = ∑ Conv( Q_n ).^[15]^[16]

Δηλώσεις

Η προηγούμενη ταυτότητα Conv( ∑ Q_n ) = ∑ Conv( Q_n )σημαίνει ότι, εάν ένα σημείο x βρίσκεται στο κυρτό του κύτους του αθροίσματος Μινικόφσκι των συνόλων N

x ∈ Conv( ∑ Q_n )

τότε το x έγκειται στο άθροισμα των κυρτών κύτους των summand συνόλων

x ∈ ∑ Conv( Q_n ).

Με τον ορισμό του Minkowski Επιπλέον, αυτή η τελευταία έκφραση σημαίνει ότι x = ∑ q_n for some selection of points q_n για κάποια επιλογή των σημείων qn στα κυρτά σύνολα των summand, δηλαδή, για κάθε q_n ∈ Conv(Q_n). Σε αυτή την αναπαράσταση, η επιλογή q_n summand σημείων εξαρτάται από το άθροισμα που έχει επιλεγεί το σημείο x.

Το λήμμα του Σάπλει και Φόλκμαν

Για αυτήν την αναπαράσταση του σημείου x, το λήμμα Σάπλει-Φόλκμαν αναφέρει ότι εάν η διάσταση D είναι μικρότερη από τον αριθμό των summands

D < N

Τότε η κυρτοποίηση είναι απαραίτητη μόνο για D-summand σύνολα, των οποίων η επιλογή εξαρτάται από x: Το σημείο έχει μια αναπαράσταση

x=\sum _{1\leq {d}\leq {D}}{q_{d}}+\sum _{D+1\leq {n}\leq {N}}{q_{n}}

για κάποια εκ νέου δημιουργία ευρετηρίου των συνόλων summand, αυτή η εκ νέου δημιουργία ευρετηρίου εξαρτάται από το συγκεκριμένο σημείο x που εκπροσωπείται. ^[17]

Το λήμμα Σάπλει- Φόλκμαν συνεπάγεται, για παράδειγμα, ότι σε κάθε σημείο του [0, 2] είναι το άθροισμα ενός ακέραιος από {0, 1} και eνός πραγματικού αριθμού από [0, 1].^[8]

Διάσταση ενός πραγματικού διανυσματικού χώρου

Αντίθετα, το λήμμα Σάπλει-Φόλκμαν χαρακτηρίζει τη διάσταση των πεπερασμένων διαστάσεων πραγματικών διανυσματικών χώρων. Δηλαδή, αν ένας διανυσματικός χώρος υπακούει στο λήμμα των Σάπλει-Φόλκμαν για ένα φυσικό αριθμό D, και για κανένα αριθμό μικρότερο από το D, τότε διάσταση είναι ακριβώς D.^[18] Το λήμμα Σάπλει-Φόλκμαν ισχύει μόνο για πεπερασμένης διάστασης διανυσματικών χώρων . ^[19]

Το θεώρημα Σάπλει-Φόλκμαν και τα επακόλουθά του Σταρ

Οι Σάπλει- Φόλκμαν χρησιμοποίησαν το λήμμα τους για να αποδείξουν το θεώρημα τους, που οριοθετεί την απόσταση μεταξύ ενός αθροίσματος Μινικόφσκι και του κυρτού κύτους του, το "άθροισμα" κύτους:

Το θεώρημα Σάπλει- Φόλκμαν αναφέρει ότι το τετράγωνο Ευκλείδειας απόστασης από οποιοδήποτε σημείο στο άθροισμα κύτους Conv( ∑ Q_n ) με το αρχικό (μη κύτος) άθροισμα ∑ Q_n οριοθετείται από το άθροισμα των τετραγώνων των D μεγαλύτερης των συνόλων Q_n ( οι ακτίνες των μικρότερων σφαιρών περικλείουν αυτά τα σύνολα). ^[20] Αυτό το δεσμευμένο είναι ανεξάρτητο από τον αριθμό των συνόλων summand-Ν (αν Ν> Δ).^[21]

Το θεώρημα Σάπλει- Φόλκμαν αναφέρει ένα όριο στην απόσταση μεταξύ του αθροίσματος Μινικόφσκι και του κυρτού του κύτους του, αυτή η απόσταση είναι μηδέν αν και μόνο αν το άθροισμα είναι κυρτό. Η δέσμευση της απόστασής εξαρτάται από την διάσταση D και για τα σχήματα των summand-συνόλων, αλλά όχι από τον αριθμό των summand-συνόλων Ν, όταν το Ν> D. ^[3]

Η περιφέρεια συχνά υπερβαίνει (και δεν μπορεί να είναι μικρότερη από) την εσωτερική ακτίνα:^[22]

Η εσωτερική ακτίνα ενός συνόλου Q_n ορίζεται να είναι ο μικρότερος αριθμός r τέτοια ώστε, για κάθε σημείο q στο κυρτό κύτους Q_n, υπάρχει μια σφαίρα ακτίνας r που περιέχει ένα υποσύνολο των Q_n των οποίων το κυρτό κύτος περιέχει q.

Ο Σταρ χρησιμοποιήσει την εσωτερική ακτίνα για να μειώσει το ανώτερο όριο που αναφέρεται στο θεώρημα Σάπλει-Φόλκμαν:

Το πόρισμα του Σταρ πάνω στο θεώρημα Σάπλει-Φόλκμαν αναφέρει ότι η τετραγωνισμένη Ευκλείδεια απόσταση από οποιοδήποτε σημείο x στο άθροισμα κύτους Conv( ∑ Q_n ) με το αρχικό (μη κύτος) άθροισμα ∑ Q_nοριοθετείται από το άθροισμα των τετραγώνων των D που είναι μεγαλύτερη της εσωτερικής ακτίνας του συνόλου Q_n.^[22]^[23]

Το πόρισμα του Σταρ αναφέρει ότι το άνω όριο για την Ευκλείδεια απόσταση μεταξύ του αθροίσματος Μινικόφσκι των Ν σύνολων και του κυρτού κύτους του αθροίσματος Μινικόφσκι. Αυτή η απόσταση μεταξύ του αθροίσματος και κυρτό περίβλημα του είναι μια μέτρηση της μη-κυρτότητας του συνόλου. Για απλότητα, η απόσταση αυτή ονομάζεται «μη κυρτότητα" του συνόλου (σε σχέση με τη μέτρηση του Σταρ). Έτσι, η δέσμευση του Σταρ για τη μη-κυρτότητα του αθροίσματος εξαρτάται μόνο από το αν η D είναι μεγαλύτερη της εσωτερικής ακτίνας των summand συνόλων. Ωστόσο, η δέσμευση του Σταρ δεν εξαρτάται από τον αριθμό των συνόλων summand-Ν, όταν το Ν> D. Για παράδειγμα, η απόσταση μεταξύ του κυρτού διαστήματος [0, 2], και του μη κυρτού σύνολου {0, 1, 2} ισούται με ένα δεύτερο.

1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

Έτσι, η δέσμευση του Σταρ στη μη κυρτότητα της μέσης

¹⁄_N ∑ Q_n

μειώνεται καθώς ο αριθμός των summands Ν αυξάνεται. Για παράδειγμα, η απόσταση μεταξύ του κατά μέσου όρου συνόλου

1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}

και του κυρτού κύτους του [0, 1] είναι μόνο το 1/4, το οποίο είναι το μισό της απόστασης (1/2) μεταξύ summand του {0, 1} και [0, 1]. Τα σχήματα ενός υποσυνόλου μόνον τα ϋ-summand σύνολα καθορίζουν τη δέσμευση από την απόσταση μεταξύ της μέσης συνόλου και του κυρτού συνόλου του. Έτσι, καθώς ο αριθμός των summands αυξάνεται στο άπειρο, τα δεσμευμένα μειώνονται στο μηδέν (για summand-σύνολα ομοιόμορφα οριοθετούνται μέγεθος). ^[3] Στην πραγματικότητα, η δέσμευση του Σταρ στη μη κυρτότητα αυτής της μέσης συνόλων μειώνεται στο μηδέν καθώς ο αριθμός των summands Ν αυξάνεται έως το άπειρο (όταν οι εσωτερικές ακτίνες όλων των summands οριοθετούνται από τον ίδιο αριθμό).^[3]

Αποδείξεις και υπολογισμοί

Η πρωτότυπη απόδειξη του λήμματος των Σάπλει-Φόλκμαν διαπίστωσε μόνο την ύπαρξη της παράστασης, αλλά δεν παρείχε έναν αλγόριθμο για τον υπολογισμό της παράστασης: Παρόμοιες αποδείξεις έχουν δοθεί από τους Arrow και Hahn, ^[24] Cassels, ^[25] και Schneider ^[26] μεταξύ άλλων. Μια αφηρημένη και κομψή απόδειξη από τον Ekeland έχει επεκταθεί από Artstein. ^[27]^[28] Οι διάφορες αποδείξεις έχουν εμφανιστεί σε αδημοσίευτα έγγραφα, επίσης. ^[2]^[29] Το 1981, ο Σταρ δημοσίευσε μια επαναληπτική μέθοδο για τον υπολογισμό μιας εκπροσώπησης ενός δοσμένου σημείου. Ωστόσο, η υπολογιστική απόδειξη του παρέχει πιο αδύναμη δέσμευση από ό, τι το αρχικό αποτέλεσμα.^[30]

Εφαρμογές

Το λήμμα Σάπλει-Φόλκμαν επιτρέπει στους ερευνητές να επεκτείνουν τα αποτελέσματα για τα αθροίσματα Μινικόφσκι στα κυρτά σύνολα σε αθροίσματα γενικών συνόλων, τα οποία δεν χρειάζεται να είναι κυρτά. Τέτοια αθροίσματα συνόλων προκύπτουν στην οικονομία, στη μαθηματική βελτιστοποίηση, και στη θεωρία πιθανοτήτων, σε κάθε μία από αυτές τις τρεις μαθηματικές επιστήμες, η μη-κυρτότητα είναι ένα σημαντικό χαρακτηριστικό των εφαρμογών.

Οικονομικά

Στα οικονομικά, οι προτιμήσεις του καταναλωτή ορίζονται πάνω από όλα τα «καλάθια» των εμπορευμάτων. Κάθε καλάθι εκπροσωπείται από ένα μη-αρνητικό διάνυσμα, των οποίων οι συντεταγμένες αντιπροσωπεύουν τις ποσότητες των εμπορευμάτων. Σε αυτό το σύνολο από τα καλάθια, μια καμπύλη αδιαφορίας ορίζεται για κάθε καταναλωτή. Η καμπύλη αδιαφορίας του καταναλωτή περιλαμβάνει όλα τα καλάθια των προϊόντων που ο καταναλωτής θεωρεί ότι είναι ισοδύναμα: Δηλαδή, για κάθε ζεύγος καλαθιών στην ίδια καμπύλη αδιαφορίας, οι καταναλωτές δεν προτιμούν ένα καλάθι περισσότερο από ένα άλλο. Μέσα από κάθε καλάθι εμπορευμάτων περνάει μια καμπύλη αδιαφορίας. Το σύνολο προτίμησης ενός καταναλωτή (σε σχέση με μια καμπύλη αδιαφορίας) είναι η ένωση της καμπύλης αδιαφορίας και όλα τα καλάθια αγαθών που ο καταναλωτής προτιμά επί της καμπύλης αδιαφορίας. Οι προτιμήσεις ενός καταναλωτή είναι κυρτές αν όλα αυτά τα σύνολα προτίμησης είναι κυρτά. ^[31]

Η βελτιστοποίηση των καλαθιών αγαθών συμβαίνει όταν η γραμμή του προϋπολογισμού υποστηρίζει το σύνολο προτιμήσεων του καταναλωτή, όπως φαίνεται στο διάγραμμα. Αυτό σημαίνει ότι το βέλτιστο καλάθι είναι στο υψηλότερο δυνατό σημείο της καμπύλη αδιαφορίας όταν δοθεί η γραμμή του προϋπολογισμού, η οποία ορίζεται από την άποψη το διάνυσμα τιμών και εισοδήματος του καταναλωτή (κληροδότημα vector). Έτσι, το σύνολο των βέλτιστων καλαθιών είναι η συνάρτηση των τιμών, και η λειτουργία αυτή ονομάζεται ζήτηση του καταναλωτή. Αν το σύνολο προτίμησης είναι κυρτό, τότε κάθε τιμή της ζήτησης του καταναλωτή είναι ένα κυρτό σύνολο, για παράδειγμα, ένα μοναδικό βέλτιστο καλάθι ή μία γραμμή τμημάτων των καλαθιών. ^[32]

Μη κυρτές προτιμήσεις

Image of a non-convex preference set with a concavity un-supported by the budget line — Όταν οι προτιμήσεις του καταναλωτή έχουν κοιλότητες, ο καταναλωτής μπορεί να πηδήξει μεταξύ δύο ξεχωριστών βέλτιστων καλαθιών.

Ωστόσο, εάν ένα σύνολο προτίμησης είναι μη-κυρτό, τότε ορισμένες τιμές καθορίζονται σε μια γραμμή του προϋπολογισμού που υποστηρίζει δύο ξεχωριστά βέλτιστα καλάθια. Για παράδειγμα, μπορούμε να φανταστούμε ότι, για ζωολογικούς κήπους, ένα λιοντάρι έχει κόστος όσο ένας αετό, και επιπλέον ότι ο προϋπολογισμός ενός ζωολογικού κήπου αρκεί για έναν αετό ή ένα λιοντάρι. Μπορούμε να υποθέσουμε, επίσης, ότι ένας φύλακας σε ζωολογικό κήπο βλέπει κάθε ζώο, εξίσου πολύτιμα. Στην περίπτωση αυτή, ο ζωολογικός κήπος θα αγοράζε είτε ένα λιοντάρι ή ένα αετό. Φυσικά, ένας σύγχρονος ζωολογικός κήπος δεν θέλει να αγοράσει το ήμισυ του αετού και το ήμισυ του λιονταριού (ή γρύπα)! Έτσι, οι προτιμήσεις του ζωολογικού είναι μη-κυρτό: Ο ζωολογικός κήπος προτιμά να έχουν ζώα που να μην είναι κυρτά ή και τα δύο.^[33]

Όταν τα σύνολα προτιμήσεων των καταναλωτών είναι μη-κυρτά,τότε (για ορισμένες τιμές), η ζήτηση των καταναλωτών δεν είναι συνδέεται. Μια ασύνδετη ζήτηση συνεπάγεται κάποια ασυνεχή συμπεριφορά του καταναλωτή, όπως συζητήθηκε από Harold Hotelling:

Αν οι καμπύλες αδιαφορίας για τις αγορές θεωρηθεί ότι διαθέτουν έναν κυματιστό χαρακτήρα, κυρτά προς την προέλευση, σε ορισμένες περιφέρειες και κοίλα σε άλλα, καταλήγουμε στο συμπέρασμα ότι μόνο τα τμήματα που είναι κυρτά προς την καταγωγή, μπορούν να θεωρηθούν ότι κατέχουν κάποια σημασία , δεδομένου ότι τα άλλα είναι ουσιαστικά μη παρατηρήσιμα. Μπορούν να ανιχνευθούν μόνο από τις ασυνέχειες που μπορεί να εμφανιστούν σε ζήτηση με διακύμανση στην τιμή-αναλογίες, οδηγεί σε ένα απότομα άλμα από ένα σημείο επαφής σε ένα χάσμα, όταν η ευθεία γραμμή περιστρέφεται. Ενώ οι εν λόγω ασυνέχειες μπορούν να αποκαλύψουν την ύπαρξη χασμάτων, ποτέ όμως δεν μπορούν να μετρήσουν το βάθος τους. Τα κοίλα τμήματα των καμπυλών αδιαφορίας και πολλών διαστάσεων γενίκευσής τους, εάν υπάρχουν, πρέπει να παραμείνουν για πάντα στην αφάνεια αμέτρητης. ^[34]

|mr=11939|ref=harv}}

Wold & Juréen (1953, p. 146): Wold, Herman· Juréen, Lars (in association with Wold) (1953). «8 Some further applications of preference fields (pp. 129–148)». Demand analysis: A study in econometrics. Wiley publications in statistics. New York: John Wiley and Sons, Inc. σελίδες xvi+358. MR 0064385.

</ref> και πάλι από τον Paul Samuelson, ο οποίος έγραψε ότι οι μη κυρτές είναι «τυλιγμένες στο αιώνιο σκοτάδι ...», ^[35] σύμφωνα με τον Diewert. ^[36] Παρ 'όλα αυτά, οι μη κυρτές προτιμήσεις φωτίστηκαν το 1959-1961 με μια σειρά από εργασίες στο The Journal of Political Economy (JPE). Οι κύριοι παράγοντες που συνέβαλαν ήταν ο Farrell, ^[37] Bator,^[38] ο Koopmans, ^[39] και ο Rothenberg.^[40] Ειδικότερα, η εργασία του Rothenberg ανέφερε την προσέγγιση της κυρτότητας αθροισμάτων των μη κυρτών συνόλων. ^[41] Αυτές οι JPE-εργασίες διεγείρονται από ένα έγγραφο από τους Lloyd Shapley και Martin Shubik, οι οποίες θεωρούνται κυρτές προτιμήσεις του καταναλωτή και εισήγαγαν την έννοια της «κατά προσέγγισης ισορροπίας». ^[42] Οι JPE εργασίες και η εργασία των Shapley-Shubik επηρέασε μια άλλη έννοια της «οιωνοί ισορροπίας», σύμφωνα με τον Robert Aumann. ^[43]^[44]

Η εργασία του Σταρ το 1969 και η σύγχρονη οικονομία

Picture of Kenneth Arrow — Kenneth Arrow (βραβείο Νόμπελ στα οικονομικά το 1972) βοήθησε τον Ross M. Starr να μελετήσει τις μη-κυρτές οικονομίες][^[45]

Οι προηγούμενες δημοσιεύσεις σχετικά με τη μη-κυρτότητα και τα οικονομικά συλλέχθηκαν σε μια σχολιασμένη βιβλιογραφία από τον Kenneth Arrow. Αποτέλεσαν τη βιβλιογραφία, ώστε ο [[Starr}}, ο οποίος ήταν τότε ένας προπτυχιακός φοιτητής του Arrow σε προηγμένα μαθήματα μαθηματικών-οικονομικών. ^[45] Στην πτυχιακή του ο Starr μελέτησε τη γενική ισορροπία της τεχνητής οικονομίας στην οποία αντικαταστάθηκαν οι μη κυρτές προτιμήσεις από τις κυρτές αυτών. Στη κυρτή οικονομία, σε κάθε επίπεδο τιμών, η συνολική ζήτηση θα ήταν το άθροισμα των κυρτών αιτημάτων των καταναλωτών. Οι ιδέες του Starr ενδιέφεραν τους μαθηματικούς Lloyd Shapley και Jon Folkman, οι οποίοι απόδειξαν το επώνομαζόμενο λήμμα και θεώρημα τους στην "ιδιωτική αλληλογραφία» τους, στην οποία αναφερόταν η εργασία του Starr.^[1]

Στη δημοσίευσή του 1969, ο Σταρ εφαρμόζει το θεώρημα Shapley-Folkman-Starr. Ο Σταρ απέδειξε ότι η κυρτή κύτους οικονομία έχει γενικές ισορροπίες που μπορούν να προσεγγίζονται με οιωνούς ισορροπίας της αρχικής οικονομίας, όταν ο αριθμός των πρακτόρων υπερβαίνει τη διάσταση των εμπορευμάτων: Συγκεκριμένα, ο Starr απέδειξε ότι υπάρχει τουλάχιστον ένας οιωνός ισορροπίας των τιμών p_opt με τις ακόλουθες ιδιότητες:

Για κάθε οιωνό ισορροπίας των τιμών p_opt, όλοι οι καταναλωτές μπορούν να επιλέξουν τα βέλτιστα καλάθια (μέγιστη προτιμώμενη και την ικανοποίηση των περιορισμών του προϋπολογισμού τους).

Στους οιωνούς ισορροπίας των τιμών p_opt στην κυρτή κύτους οικονομίας, της αγοράς κάθε καλό αγαθό είναι σε ισορροπία: η προμήθεια του ισούται με τη ζήτησή του.

Για κάθε οιωνό ισορροπίας, οι τιμές «σχεδόν καθαρό» στις αγορές για την αρχική οικονομία: ένα ανώτατο όριο για την απόσταση μεταξύ του συνόλου των ισορροπιών του κυρτού κύτους οικονομίας και το σύνολο των οιωνών ισορροπίας της αρχικής οικονομίας που ακολουθείται από το πόρισμα του Σταρ στο θεώρημα των Shapley–Folkman.^[46]

Ο Starr διαπίστωσε ότι

«Στο σύνολό τους, η διαφορά μεταξύ μιας κατανομής στην πλασματική οικονομία που παράγεται από [τη λήψη των κυρτών καταναλωτών και των παραγόμενων συνόλων] και κάποια κατανομή στην πραγματική οικονομία οριοθετείται κατά τρόπο που να είναι ανεξάρτητη από τον αριθμό των οικονομικών παραγόντων. Ως εκ τούτου, ο μέσος παράγοντας βιώνει μια απόκλιση από την προβλεπόμενη ενέργεια που εξαφανίζει τη σημασία, καθώς ο αριθμός των παραγόντων πηγαίνει στο άπειρο ». ^[47]

Μετά το 1969 η εργασία του Starr και τα αποτελέσματα των Shapley-Folkman-Starr έχουν χρησιμοποιηθεί ευρέως στην οικονομική θεωρία. Ο Roger Guesnerie συνοψίζει τις οικονομικές επιπτώσεις τους: «Μερικά βασικά αποτελέσματα που επιτεύχθηκαν με την παραδοχή της κυρτότητας παραμένει (περίπου) σχετικό σε περιπτώσεις όπου δεν υπάρχει κυρτότητα. Για παράδειγμα, σε οικονομίες με μεγάλη πλευρά κατανάλωσης, οι nonconvexities προτίμησεις δεν καταστρέφουν τα πρότυπα αποτελέσματα». ^[48] «Η παραγωγή αυτών των αποτελεσμάτων σε γενική μορφή υπήρξε ένα από τα σημαντικότερα επιτεύγματα της μεταπολεμικής οικονομικής θεωρίας», έγραψε ο Guesnerie.^[4] Το θέμα των μη κυρτών συνόλων στα οικονομικά έχει μελετηθεί από πολλούς νομπελίστες: Arrow (1972) , Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008), και Paul Samuelson (1970). Το συμπληρωματικό θέμα των κυρτών συνόλων στα οικονομικά έχει τονιστεί από αυτούς, μαζί με τους Leonid Hurwicz, Leonid Kantorovich (1975), και Robert Solow (1987). ^[49] Τα αποτελέσματα των Shapley-Folkman-Starr έχουν προβληθεί στην οικονομική βιβλιογραφία : στην μικροοικονομική θεωρία, ^[50] στην κλασική θεωρία της γενικής ισορροπίας, ^[51]^[52] , στα δημόσια οικονομικά ^[53] (συμπεριλαμβανομένων των ανεπαρκειών της αγοράς), ^[54] καθώς και στην θεωρία των παιγνίων, ^[55] στη μαθηματική οικονομία, ^[56] και στα εφαρμοσμένα μαθηματικά (για τους οικονομολόγους). ^[57]^[58] . Τα αποτελέσματα των Shapley-Folkman-Starr έχουν επίσης επηρεάσει την οικονομία της έρευνας με τη χρήση του μέτρου και της θεωρίας ολοκλήρωσης. ^[59]

Μαθηματική βελτιστοποίηση

Το λήμμα των Σάπλει-Φόλκμαν έχει χρησιμοποιηθεί για να εξηγήσει γιατί τα μεγάλα προβλήματα ελαχιστοποίησης με μη-κοιλότητα μπορούν σχεδόν να λυθούν (με επαναληπτικές μεθόδους των οποίων η σύγκλιση απόδειξης δηλώνεται μόνο για κυρτά προβλήματα). Το λήμμα των Σάπλει-Φόλκμαν έχει ενθαρρύνει τη χρήση των μεθόδων ελαχιστοποίησης των κυρτών σε άλλες εφαρμογές με αθροίσματα από πολλές λειτουργίες.^[60]

Προκαταρκτικά της θεωρίας βελτιστοποίησης

H μη γραμμική βελτιστοποίηση βασίζεται στους ακόλουθους ορισμούς συναρτήσεων:

Η γραφική παράσταση της συνάρτησης f είναι το σύνολο των ζευγών των επιχειρημάτων χ και αξιολογήσεων της συνάρτησης f (x)

Graph(f) = { (x, f(x) ) }

Η επιγραφή της πραγματικής συνάρτησης f είναι το σύνολο των σημείων πάνω από το γράφημα

Η συνάρτηση ημχ είναι μη- κυρτή

.]]

Epi(f) = { (x, u) : f(x) ≤ u }.

Μια πραγματική συνάρτηση ορίζεται να είναι μια κυρτή συνάρτηση αν η επιγραφή του είναι ένα κυρτό σύνολο. ^[61]

Για παράδειγμα, η τετραγωνική συνάρτηση f(x) = x² είναι κυρτή, όπως είναι η συνάρτηση απόλυτης τιμής g(x) = |x|. Ωστόσο, η ημιτονοειδής συνάρτηση (φωτογραφία) είναι μη-κυρτή στο διάστημα (0, π).

Πρόσθετα προβλήματα βελτιστοποίησης

Σε πολλά προβλήματα βελτιστοποίησης, η αντικειμενική συνάρτηση f είναι διαχωρίσιμη: δηλαδή, η f είναι το άθροισμα των πολλών summand λειτουργιών, καθένα από τα οποία έχει τη δική του επιχειρηματολογία:

f(x) = f( (x₁, ..., x_N) ) = ∑ f_n(x_n).

Για παράδειγμα, τα προβλήματα της γραμμικής βελτιστοποίησης είναι διαχωρίσιμα. Λαμβάνοντας υπόψη ένα διαχωρίσιμο πρόβλημα με μια βέλτιστη λύση, έχουμε καθορίσει τη βέλτιστη λύση

x_min = (x₁, ..., x_N)_min

με την ελάχιστη τιμή f(x_min). . Γι 'αυτό το διαχωρίσιμο πρόβλημα, θεωρούμε επίσης μια βέλτιστη λύση (x_min, f(x_min) ), όπου τα κυρτά λαμβάνονται από τις γραφικές παραστάσεις των συναρτήσεων summand. Μια τέτοια βέλτιστη λύση είναι το όριο μίας ακολουθίας των σημείων στο convexified πρόβλημα

(x_j, f(x_j) ) ∈ ∑ Conv (Graph( f_n ) ).^[5]Σφάλμα αναφοράς: Λείπει η ετικέτα κλεισίματος </ref> για την ετικέτα <ref>^[5]

^[62]

Η ανάλυση του Ekeland εξήγησε την επιτυχία των κυρτών μεθόδων ελαχιστοποίησης σε μεγάλα και σε διαχωρίσιμα προβλήματα, παρά τη μη κοιλότητα των λειτουργιών summand. Ο Ekeland και αργότερα οι συγγραφείς υποστήριξαν ότι η προσθετική διαχωρισιμότητα προκάλεσε ένα κυρτό συνολικό πρόβλημα, έστω και αν οι λειτουργίες summand ήταν μη-κυρτές. Το κρίσιμο βήμα σε αυτές τις δημοσιεύσεις είναι η χρήση του λήμματος Σάπλει-Φόλκμαν. ^[5]

^[62] ^[63] Το λήμμα των Σάπλει-Φόλκμαν έχει ενθαρρύνει τη χρήση των κυρτών μεθόδων ελαχιστοποίησης σε άλλες εφαρμογές με αθροίσματα από τις πολλές λειτουργίες.^[5]

^[6]

^[57]

^[60]

Πιθανότητες και θεωρία μέτρου

Τα κυρτά σύνολα συχνά μελετήθηκαν με τη θεωρία των πιθανοτήτων. Κάθε σημείο στο κυρτό του κύτους ενός (μη κενού) υποσυνόλου Q πεπερασμένου διαστάσεων είναι η αναμενόμενη τιμή ενός απλού τυχαίου φορέα που λαμβάνει τις τιμές της στο Q, ως συνέπεια του λήμματος Καραθεοδωρή. Έτσι, για ένα μη-κενό σύνολο Q, η συλλογή των αναμενόμενων τιμών των απλών, Q-αποτιμώνται τυχαία ως διανύσματα που ισούται με κυρτό του κύτους της Q. Αυτή η ισότητα σημαίνει ότι τα αποτελέσματα των Shapley-Folkman-Starr είναι χρήσιμα στη θεωρία πιθανοτήτων. ^[64] Στην άλλη κατεύθυνση, η θεωρία πιθανοτήτων παρέχει τα εργαλεία για να εξετάσει κυρτά γενικά σύνολα και οι Shapley-Folkman-Starr προκύπτουν συγκεκριμένα. ^[65] Τα αποτελέσματά Σάπλει-Φόλκμαν-Σταρ έχουν χρησιμοποιηθεί ευρέως στην πιθανολογική θεωρία των τυχαίων συνόλων ^[66], για παράδειγμα, να αποδείξει ένα νόμο των μεγάλων αριθμών,^[7] ^[67] ένα κεντρικό οριακό θεώρημα, ^[67]^[68] και μία αρχή μεγάλης απόκλισης. ^[69] Οι αποδείξεις των πιθανοτικών όριακών θεωρημάτων που χρησιμοποιούνται τα αποτελέσματα Shapley-Folkman-Starr αποφεύγουν την παραδοχή ότι όλα τα τυχαία σύνολα να είναι κυρτά.

Ένα μέτρο πιθανότητας είναι ένα πεπερασμένο μέτρο, και το λήμμα Shapley-Folkman έχει εφαρμογές στη μη πιθανολογική θεωρία μέτρου, όπως τις θεωρίες του όγκου και των μέτρων φορέα. Το λήμμα Shapley-Folkman επιτρέπει την τελειοποίηση της ανισότητας Brunn-Minkowski, που οριοθετεί τον όγκο των αθροισμάτων από την άποψη του όγκου των summand συνόλων τους.^[70] Ο όγκος του είναι καθορισμένος από την άποψη του μέτρου Lebesgue, η οποία ορίζεται σε υποσύνολα του Ευκλείδειου χώρο. Στη προχωρημένη μέτρο-θεωρία, το λήμμα Shapley-Folkman έχει χρησιμοποιηθεί για να αποδείξει το θεώρημα Lyapunov, το οποίο αναφέρει ότι το φάσμα ενός μέτρου φορέα είναι κυρτό. ^[71] Εδώ, η παραδοσιακή ένδειξη "ποικιλία" (εναλλακτικά, "εικόνα") είναι το σύνολο των αξιών που παράγονται από τη συνάρτηση. Ένα μέτρο φορέα είναι ένας φορέας-αποτιμώνται γενίκευση του μέτρου, για παράδειγμα, εάν τα p₁ και p₂ είναι μέτρα πιθανότητας ορίζεται με τον ίδιο μετρήσιμο χώρο, τότε το p₁ p₂ λειτουργίας του προϊόντος είναι ένα μέτρο φορέα, όπου p₁ p₂ ορίζεται για κάθε περιπτώσεις του ω που

(p₁ p₂)(ω)=(p₁(ω), p₂(ω)).

Το θεώρημα Lyapunov έχει χρησιμοποιηθεί στα οικονομικά, ^[43] ^[72] σε ("μπαμ-μπαμ") θεωρία ελέγχου, και στη στατιστική θεωρία. ^[73] Το θεώρημα Lyapunov έχει χαρακτηριστεί ως ένα συνεχές ομόλογό του λήμματος Σάπλει-Φίλκμαν, ^[3]το οποίο έχει αποκληθεί ένα διακριτό ανάλογο του θεωρήματος Lyapunov. ^[74]

Notes

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 Starr (1969)
↑ ^2,0 ^2,1 Howe (1979, p. 1): Howe, Roger (3 November 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, http://cowles.econ.yale.edu/P/cd/d05a/d0538.pdf, ανακτήθηκε στις 1 January 2011
↑ ^3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 Starr (2008)
↑ ^4,0 ^4,1 Guesnerie (1989, p. 138)
↑ ^5,0 ^5,1 ^5,2 ^5,3 ^5,4 (Ekeland 1999, σελίδες 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,0 ^6,1 Bertsekas (1996, pp. 364–381) acknowledging Ekeland (1999) on page 374 and Aubin & 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 έκδοση). Belmont, MA: Athena Scientific. σελίδες xiii+395. ISBN 1-886529-04-3. MR 0690767.

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. http://web.mit.edu/dimitrib/www/Unit_Comm.pdf. Ανακτήθηκε στις 2 February 2011.
↑ ^7,0 ^7,1 Artstein & 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, doi:10.1214/aop/1176996275, Πρότυπο:Euclid, Zbl 0313.60012, http://projecteuclid.org/euclid.aop/1176996275
↑ ^8,0 ^8,1 ^8,2 ^8,3 Σφάλμα αναφοράς: Σφάλμα παραπομπής: Λανθασμένο <ref>. Δεν υπάρχει κείμενο για τις παραπομπές με όνομα Carter94.
↑ Arrow & Hahn (1980, p. 375)
↑ Σφάλμα αναφοράς: Σφάλμα παραπομπής: Λανθασμένο <ref>. Δεν υπάρχει κείμενο για τις παραπομπές με όνομα Rock10.
↑ Arrow & Hahn (1980, p. 376), Rockafellar (1997, pp. 10–11), and Green & Heller (1981, p. 37)
↑ Arrow & Hahn (1980, p. 385) and Rockafellar (1997, pp. 11–12)
↑ Schneider (1993, p. xi) and Rockafellar (1997, p. 16)
↑ Rockafellar (1997, p. 17) and Starr (1997, p. 78)
↑ Schneider (1993, pp. 2–3)
↑ Arrow & Hahn (1980, p. 387)
↑ Starr (1969, pp. 35–36)
↑ Schneider (1993, p. 131)
↑ Schneider (1993, p. 140) credits this result to Borwein & O'Brien (1978): Borwein, J. M.; O'Brien, R. C. (1978). «Cancellation characterizes convexity». Nanta Mathematica (Nanyang University) 11: 100–102. ISSN 0077-2739. MR 510842.
↑ Schneider (1993, p. 129)
↑ Starr (1969, p. 36)
↑ ^22,0 ^22,1 Starr (1969, p. 37)
↑ Schneider (1993, pp. 129–130)
↑ Arrow & Hahn (1980, pp. 392–395)
↑ Cassels (1975, pp. 435–436)
↑ Schneider (1993, p. 128)
↑ Ekeland (1999, pp. 357–359)
↑ Artstein (1980, p. 180)
↑ Anderson, Robert M. (14 March 2005), «1 The Shapley–Folkman theorem», Economics 201B: Nonconvex preferences and approximate equilibria, Berkeley, CA: Economics Department, University of California, Berkeley, σελ. 1–5, http://elsa.berkeley.edu/users/anderson/Econ201B/NonconvexHandout.pdf, ανακτήθηκε στις 1 January 2011
↑ Starr, Ross M. (1981). «Approximation of points of convex hull of a sum of sets by points of the sum: An elementary approach». Journal of Economic Theory 25 (2): 314–317. doi:10.1016/0022-0531(81)90010-7. MR 640201. http://www.sciencedirect.com/science/article/B6WJ3-4CYGB4B-FB/2/9e65178b1c246365bee61dc19127175d.
↑ Mas-Colell (1985, pp. 58–61) and Arrow & Hahn (1980, pp. 76–79)
↑ Arrow & Hahn (1980, pp. 79–81)
↑ Starr (1969, p. 26): "After all, one may be indifferent between an automobile and a boat, but in most cases one can neither drive nor sail the combination of half boat, half car."
↑ Hotelling (1935, p. 74): Hotelling, Harold (January 1935). «Demand functions with limited budgets». Econometrica 3 (1): 66–78.
↑ Samuelson (1950, pp. 359–360):
It will be noted that any point where the indifference curves are convex rather than concave cannot be observed in a competitive market. Such points are shrouded in eternal darkness—unless we make our consumer a monopsonist and let him choose between goods lying on a very convex "budget curve" (along which he is affecting the price of what he buys). In this monopsony case, we could still deduce the slope of the man's indifference curve from the slope of the observed constraint at the equilibrium point.
Samuelson, Paul A. (November 1950). «The problem of integrability in utility theory». Economica. New Series 17 (68): 355–385. MR 43436.
"Eternal darkness" describes the Hell of John Milton's Paradise Lost, whose concavity is compared to the Serbonian Bog in Book II, lines 592–594:
A gulf profound as that Serbonian Bog
Betwixt Damiata and Mount Casius old,
Where Armies whole have sunk.
Milton's description of concavity serves as the literary epigraph prefacing chapter seven of Arrow & Hahn (1971, p. 169), "Markets with non-convex preferences and production", which presents the results of Starr (1969).
↑ 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. Farrell, M. J. (October 1961a). On Convexity, efficiency, and markets: A Reply. 69, σελ. 484–489. Farrell, M. J. (October 1961b). The Convexity assumption in the theory of competitive markets: Rejoinder. 69, σελ. 493.
↑ Bator, Francis M. (October 1961a). «On convexity, efficiency, and markets». The Journal of Political Economy 69 (5): 480–483. doi:10.1086/258540. Bator, Francis M. (October 1961b). On convexity, efficiency, and markets: Rejoinder. 69, σελ. 489.
↑ 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.
Koopmans (1961, p. 478) and others—for example, Farrell (1959, pp. 390–391) and Farrell (1961a, p. 484), Bator (1961, pp. 482–483), Rothenberg (1960, p. 438), and Starr (1969, p. 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]):
Tjalling C., Koopmans (1957). «Allocation of resources and the price system». Στο: Koopmans, Tjalling C. Three essays on the state of economic science. New York: McGraw–Hill Book Company. σελίδες 1–126. ISBN 0-07-035337-9.
↑ Rothenberg (1960, p. 447): Rothenberg, Jerome (October 1960). «Non-convexity, aggregation, and Pareto optimality». The Journal of Political Economy 68 (5): 435–468. doi:10.1086/258363. (Rothenberg, Jerome (October 1961). Comments on non-convexity. 69, σελ. 490–492. )
↑ Arrow & Hahn (1980, p. 182)
↑ Shapley & Shubik (1966, p. 806): Shapley, L. S.; Shubik, M. (October 1966). «Quasi-cores in a monetary economy with nonconvex preferences». Econometrica 34 (4): 805–827. doi:10.2307/1910101. Zbl 154.45303.
↑ ^43,0 ^43,1 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. MR 191623. 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. MR 172689.
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. MR 185073. http://www.sciencedirect.com/science/article/B6WK2-4CRJ2XG-1D4/2/761eda1b7acffb52fde213d766059f3c.
↑ Taking the convex hull of non-convex preferences had been discussed earlier by Wold (1943b, p. 243) and by Wold & Juréen (1953, p. 146), according to Diewert (1982, p. 552).
↑ ^45,0 ^45,1 Starr & Stinchcombe (1999, pp. 217–218): Starr, R. M.· Stinchcombe, M. B. (1999). «Exchange in a network of trading posts». Στο: Chichilnisky, Graciela. Markets, information and uncertainty: Essays in economic theory in honor of Kenneth J. Arrow. Cambridge: Cambridge University Press. σελίδες 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, p. 44)
↑ Guesnerie (1989, pp. 99)
↑ Mas-Colell (1987)
↑ Varian (1992, pp. 393–394): Varian, Hal R. (1992). «21.2 Convexity and size». Microeconomic Analysis (3rd έκδοση). W. W. Norton & Company. ISBN 978-0-393-95735-8. MR 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 differentiable approach. Econometric Society monographs. 9. Cambridge University Press. ISBN 0-521-26514-2. MR 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. σελίδες viii+251. ISBN 978-0-691-04189-6. MR 0389160.
↑ Starr (1997, p. 169): Starr, Ross M. (1997). «8 Convex sets, separation theorems, and non-convex sets in R^N (new chapters 22 and 25–26 in (2011) second ed.)». General equilibrium theory: An introduction (First έκδοση). Cambridge: Cambridge University Press. σελίδες xxiii+250. ISBN 0-521-56473-5. MR 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 (1988, pp. 63–65): Laffont, Jean-Jacques (1988). «3 Nonconvexities». 0-262-12127-1&id=O5MnAQAAIAAJ Fundamentals of public economics Check |url= value (βοήθεια). MIT. ISBN 0-262-12127-1. Εξωτερικός σύνδεσμος στο |publisher= (βοήθεια)
↑ 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) έκδοση). Cambridge, MA: MIT Press. σελίδες 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]. σελίδες x+164. ISBN 0-12-370180-5. MR 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. σελίδες xi+145. ISBN 0-521-28614-X. MR 0657578.
↑ ^57,0 ^57,1 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 έκδοση). Mineola, NY: Dover Publications, Inc. σελίδες xxxii+616. ISBN 978-0-486-46265-3. MR 2449499.
↑ Carter (2001, pp. 93–94, 143, 318–319, 375–377, and 416)
↑ Trockel (1984, p. 30): Trockel, Walter (1984). Market demand: An analysis of large economies with nonconvex preferences. Lecture notes in economics and mathematical systems. 223. Berlin: Springer-Verlag. σελίδες viii+205. ISBN 3-540-12881-6. MR 0737006.
↑ ^60,0 ^60,1 Bertsekas (1999, p. 496): Bertsekas, Dimitri P. (1999). «5.1.6 Separable problems and their geometry». Nonlinear Programming (Second έκδοση). Cambridge, MA.: Athena Scientific. σελίδες 494–498. ISBN 1-886529-00-0.
↑ Rockafellar (1997, p. 23)
↑ ^62,0 ^62,1 Ekeland, Ivar (1974). «Une estimation a priori en programmation non convexe» (στα French). Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Séries A et B 279: 149–151. ISSN 0151-0509. MR 395844.
↑ 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. MR 449695.
Aubin & Ekeland (1976) and Ekeland (1999, pp. 362–364) also considered the convex closure of a problem of non-convex minimization—that is, the problem defined as the closed convex hull of the epigraph of the original problem. Their study of duality gaps was extended by Di Guglielmo to the quasiconvex closure of a non-convex minimization problem—that is, the problem defined as the closed convex hull of the lower 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. MR 484418.
↑ Schneider & Weil (2008, p. 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. MR 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. MR 385711. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2075868&fulltextType=RA&fileId=S0305004100051884ER.
↑ 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. σελίδες 194–240. doi:10.1007/1-84628-150-4. ISBN 978-1-84996-949-9. MR 2132405.
↑ ^67,0 ^67,1 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. doi:10.1017/S0305004100062691. MR 764504. http://journals.cambridge.org/action/displayAbstract?aid=2087952.
↑ 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. MR 663901.
↑ 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. MR 1487361. http://www.ams.org/journals/proc/1999-127-08/S0002-9939-99-04788-7. Cerf uses applications of the Shapley–Folkman lemma from Puri & Ralescu (1985, pp. 154–155).
↑ Ruzsa (1997, p. 345): Ruzsa, Imre Z. (1997). «The Brunn–Minkowski inequality and nonconvex sets». Geometriae Dedicata 67 (3): 337–348. doi:10.1023/A:1004958110076. MR 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. MR 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. Vind's article was noted by the winner of the 1983 Nobel Prize in Economics, Gérard Debreu Debreu (1991, p. 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. Convexity 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.
↑ Artstein (1980, pp. 172–183) Artstein (1980) was republished in a festschrift for Robert J. Aumann, winner of the 2008 Nobel Prize in Economics: Artstein, Zvi (1995). «22 Discrete and continuous bang–bang and facial spaces or: Look for the extreme points». Στο: Hart, Sergiu· Neyman, Abraham. Game and economic theory: Selected contributions in honor of Robert J. Aumann. Ann Arbor, MI: University of Michigan Press. σελίδες 449–462. ISBN 0-472-10673-2.
↑ Mas-Colell (1978, p. 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. MR 514468. http://www.sciencedirect.com/science/article/B6VBY-4582G5H-2G/2/576b6893a9a730c3557fde0f52d3a9c2.

References

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 έκδοση). Amsterdam: North-Holland. ISBN 0-444-85497-5. MR 0439057.
Artstein, Zvi (1980). «Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points». SIAM Review 22 (2): 172–185. doi:10.1137/1022026. MR 564562.
Carter, Michael (2001). Foundations of mathematical economics. Cambridge, MA: MIT Press. σελίδες xx+649. ISBN 0-262-53192-5. MR 1865841. (Author's website with answers to exercises).
Diewert, W. E. (1982). «12 Duality approaches to microeconomic theory». Στο: Arrow, Kenneth Joseph· Intriligator, Michael D. Handbook of mathematical economics, Volume II. Handbooks in Economics. 1. Amsterdam: North-Holland Publishing Co. σελίδες 535–599. doi:10.1016/S1573-4382(82)02007-4. ISBN 978-0-444-86127-6. MR 0648778.
Ekeland, Ivar (1999) [1976]. «Appendix I: An a priori estimate in convex programming». Στο: Ekeland, Ivar· Temam, Roger. Convex analysis and variational problems. Classics in Applied Mathematics. 28 (Corrected reprinting of the North-Holland έκδοση). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). σελίδες 357–373. ISBN 0-89871-450-8. MR 1727362.
Green, Jerry· Heller, Walter P. (1981). «1 Mathematical analysis and convexity with applications to economics». Στο: Arrow, Kenneth Joseph· Intriligator, Michael D. Handbook of mathematical economics, Volume I. Handbooks in Economics. 1. Amsterdam: North-Holland Publishing Co. σελίδες 15–52. doi:10.1016/S1573-4382(81)01005-9. ISBN 0-444-86126-2. MR 0634800.
Guesnerie, Roger (1989). «First-best allocation of resources with nonconvexities in production». Στο: Cornet, Bernard· Tulkens, Henry. 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. σελίδες 99–143. ISBN 0-262-03149-3. MR 1104662.
Mas-Colell, A. (1987). «Non-convexity». Στο: Eatwell, John· Milgate, Murray· Newman, Peter. [[The New Palgrave Dictionary of Economics|The new Palgrave: A dictionary of economics]] (first έκδοση). Palgrave Macmillan. σελίδες 653–661. doi:10.1057/9780230226203.3173. (PDF file at Mas-Colell's homepage). URL–wikilink conflict (βοήθεια)
Rockafellar, R. Tyrrell (1997). Convex analysis. Princeton Landmarks in Mathematics (Reprint of the 1970 (MR 274683) Princeton Mathematical Series 28 έκδοση). Princeton, NJ: Princeton University Press. σελίδες xviii+451. ISBN 0-691-01586-4. MR 1451876.
Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of Mathematics and its Applications. 44. Cambridge: Cambridge University Press. σελίδες xiv+490. ISBN 0-521-35220-7. MR 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
Starr, Ross M. (2008). «Shapley–Folkman theorem». Στο: Durlauf, Steven N.· Blume, Lawrence E. [[The New Palgrave Dictionary of Economics|The new Palgrave dictionary of economics]] (Second έκδοση). Palgrave Macmillan. σελίδες 317–318 (1st ed.). doi:10.1057/9780230226203.1518. URL–wikilink conflict (βοήθεια)

External links

Anderson, Robert M. (2005), «1 The Shapley–Folkman theorem», Economics 201B: Nonconvex preferences and approximate equilibria, Berkeley, CA: Economics Department, University of California, Berkeley, σελ. 1–5, http://elsa.berkeley.edu/users/anderson/Econ201B/NonconvexHandout.pdf, ανακτήθηκε στις 15 January 2011
Howe, Roger (1979), On the tendency toward convexity of the vector sum of sets, Cowles Foundation discussion papers, 538, Box 2125 Yales Station, New Haven, CT 06520: Cowles Foundation for Research in Economics, Yale University, http://cowles.econ.yale.edu/P/cd/d05a/d0538.pdf, ανακτήθηκε στις 15 January 2011
Starr, Ross M. (2009), «8 Convex sets, separation theorems, and non-convex sets in R^N (Section 8.2.3 Measuring non-convexity, the Shapley–Folkman theorem)», General equilibrium theory: An introduction, σελ. 3–6, (Draft of second edition, from Starr's course at the Economics Department of the University of California, San Diego), http://www.econ.ucsd.edu/~rstarr/113Winter2010/Webpage/PDFonlyCUPsubmission/Chap8-2009/2009CHAP-08092109.pdf, ανακτήθηκε στις 15 January 2011
Starr, Ross M. (2007), Shapley–Folkman theorem, σελ. 1–3, (Draft of article for the second edition of New Palgrave Dictionary of Economics), http://www.econ.ucsd.edu/~rstarr/SFarticle.pdf, ανακτήθηκε στις 15 January 2011

Πρότυπο:Geometry-footer Πρότυπο:Microeconomics Πρότυπο:Use dmy dates

Πρότυπο:Link FA

[s69-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 Starr (1969)

[Howe-2] 2,0 ^2,1 Howe (1979, p. 1): Howe, Roger (3 November 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, http://cowles.econ.yale.edu/P/cd/d05a/d0538.pdf, ανακτήθηκε στις 1 January 2011

[Starr08-3] 3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 Starr (2008)

[g89-p138-4] 4,0 ^4,1 Guesnerie (1989, p. 138)

[Ekeland76-5] 5,0 ^5,1 ^5,2 ^5,3 ^5,4 (Ekeland 1999, σελίδες 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.

[Bertsekas82-6] 6,0 ^6,1 Bertsekas (1996, pp. 364–381) acknowledging Ekeland (1999) on page 374 and Aubin & 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 έκδοση). Belmont, MA: Athena Scientific. σελίδες xiii+395. ISBN 1-886529-04-3. MR 0690767.

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. http://web.mit.edu/dimitrib/www/Unit_Comm.pdf. Ανακτήθηκε στις 2 February 2011.

[ArtsteinVitale-7] 7,0 ^7,1 Artstein & 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, doi:10.1214/aop/1176996275, Πρότυπο:Euclid, Zbl 0313.60012, http://projecteuclid.org/euclid.aop/1176996275

[Carter94-8] 8,0 ^8,1 ^8,2 ^8,3 Σφάλμα αναφοράς: Σφάλμα παραπομπής: Λανθασμένο <ref>. Δεν υπάρχει κείμενο για τις παραπομπές με όνομα Carter94.

[9] Arrow & Hahn (1980, p. 375)

[Rock10-10] Σφάλμα αναφοράς: Σφάλμα παραπομπής: Λανθασμένο <ref>. Δεν υπάρχει κείμενο για τις παραπομπές με όνομα Rock10.

[11] Arrow & Hahn (1980, p. 376), Rockafellar (1997, pp. 10–11), and Green & Heller (1981, p. 37)

[12] Arrow & Hahn (1980, p. 385) and Rockafellar (1997, pp. 11–12)

[13] Schneider (1993, p. xi) and Rockafellar (1997, p. 16)

[14] Rockafellar (1997, p. 17) and Starr (1997, p. 78)

[Schneider-15] Schneider (1993, pp. 2–3)

[16] Arrow & Hahn (1980, p. 387)

[17] Starr (1969, pp. 35–36)

[18] Schneider (1993, p. 131)

[19] Schneider (1993, p. 140) credits this result to Borwein & O'Brien (1978): Borwein, J. M.; O'Brien, R. C. (1978). «Cancellation characterizes convexity». Nanta Mathematica (Nanyang University) 11: 100–102. ISSN 0077-2739. MR 510842.

[20] Schneider (1993, p. 129)

[21] Starr (1969, p. 36)

[Starr_1969_37-22] 22,0 ^22,1 Starr (1969, p. 37)

[23] Schneider (1993, pp. 129–130)

[24] Arrow & Hahn (1980, pp. 392–395)

[25] Cassels (1975, pp. 435–436)

[26] Schneider (1993, p. 128)

[27] Ekeland (1999, pp. 357–359)

[28] Artstein (1980, p. 180)

[29] Anderson, Robert M. (14 March 2005), «1 The Shapley–Folkman theorem», Economics 201B: Nonconvex preferences and approximate equilibria, Berkeley, CA: Economics Department, University of California, Berkeley, σελ. 1–5, http://elsa.berkeley.edu/users/anderson/Econ201B/NonconvexHandout.pdf, ανακτήθηκε στις 1 January 2011

[30] Starr, Ross M. (1981). «Approximation of points of convex hull of a sum of sets by points of the sum: An elementary approach». Journal of Economic Theory 25 (2): 314–317. doi:10.1016/0022-0531(81)90010-7. MR 640201. http://www.sciencedirect.com/science/article/B6WJ3-4CYGB4B-FB/2/9e65178b1c246365bee61dc19127175d.

[31] Mas-Colell (1985, pp. 58–61) and Arrow & Hahn (1980, pp. 76–79)

[32] Arrow & Hahn (1980, pp. 79–81)

[33] Starr (1969, p. 26): "After all, one may be indifferent between an automobile and a boat, but in most cases one can neither drive nor sail the combination of half boat, half car."

[34] Hotelling (1935, p. 74): Hotelling, Harold (January 1935). «Demand functions with limited budgets». Econometrica 3 (1): 66–78.

[35] Samuelson (1950, pp. 359–360):
It will be noted that any point where the indifference curves are convex rather than concave cannot be observed in a competitive market. Such points are shrouded in eternal darkness—unless we make our consumer a monopsonist and let him choose between goods lying on a very convex "budget curve" (along which he is affecting the price of what he buys). In this monopsony case, we could still deduce the slope of the man's indifference curve from the slope of the observed constraint at the equilibrium point.
Samuelson, Paul A. (November 1950). «The problem of integrability in utility theory». Economica. New Series 17 (68): 355–385. MR 43436.
"Eternal darkness" describes the Hell of John Milton's Paradise Lost, whose concavity is compared to the Serbonian Bog in Book II, lines 592–594:
A gulf profound as that Serbonian Bog
Betwixt Damiata and Mount Casius old,
Where Armies whole have sunk.
Milton's description of concavity serves as the literary epigraph prefacing chapter seven of Arrow & Hahn (1971, p. 169), "Markets with non-convex preferences and production", which presents the results of Starr (1969).

[Diewert-36] Diewert (1982, pp. 552–553)

[37] 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. Farrell, M. J. (October 1961a). On Convexity, efficiency, and markets: A Reply. 69, σελ. 484–489. Farrell, M. J. (October 1961b). The Convexity assumption in the theory of competitive markets: Rejoinder. 69, σελ. 493.

[38] Bator, Francis M. (October 1961a). «On convexity, efficiency, and markets». The Journal of Political Economy 69 (5): 480–483. doi:10.1086/258540. Bator, Francis M. (October 1961b). On convexity, efficiency, and markets: Rejoinder. 69, σελ. 489.

[39] 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.
Koopmans (1961, p. 478) and others—for example, Farrell (1959, pp. 390–391) and Farrell (1961a, p. 484), Bator (1961, pp. 482–483), Rothenberg (1960, p. 438), and Starr (1969, p. 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]):
Tjalling C., Koopmans (1957). «Allocation of resources and the price system». Στο: Koopmans, Tjalling C. Three essays on the state of economic science. New York: McGraw–Hill Book Company. σελίδες 1–126. ISBN 0-07-035337-9.

[Rothenberg-40] Rothenberg (1960, p. 447): Rothenberg, Jerome (October 1960). «Non-convexity, aggregation, and Pareto optimality». The Journal of Political Economy 68 (5): 435–468. doi:10.1086/258363. (Rothenberg, Jerome (October 1961). Comments on non-convexity. 69, σελ. 490–492. )

[ArrowHahn182-41] Arrow & Hahn (1980, p. 182)

[42] Shapley & Shubik (1966, p. 806): Shapley, L. S.; Shubik, M. (October 1966). «Quasi-cores in a monetary economy with nonconvex preferences». Econometrica 34 (4): 805–827. doi:10.2307/1910101. Zbl 154.45303.

[Aumann-43] 43,0 ^43,1 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. MR 191623. 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. MR 172689.
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. MR 185073. http://www.sciencedirect.com/science/article/B6WK2-4CRJ2XG-1D4/2/761eda1b7acffb52fde213d766059f3c.

[44] Taking the convex hull of non-convex preferences had been discussed earlier by Wold (1943b, p. 243) and by Wold & Juréen (1953, p. 146), according to Diewert (1982, p. 552).

[StarrArrow-45] 45,0 ^45,1 Starr & Stinchcombe (1999, pp. 217–218): Starr, R. M.· Stinchcombe, M. B. (1999). «Exchange in a network of trading posts». Στο: Chichilnisky, Graciela. Markets, information and uncertainty: Essays in economic theory in honor of Kenneth J. Arrow. Cambridge: Cambridge University Press. σελίδες 217–234. doi:10.2277/0521553555. ISBN 978-0-521-08288-4.

[46] Arrow & Hahn (1980, pp. 169–182). Starr (1969, pp. 27–33)

[47] Green & Heller (1981, p. 44)

[48] Guesnerie (1989, pp. 99)

[MasColell87-49] Mas-Colell (1987)

[50] Varian (1992, pp. 393–394): Varian, Hal R. (1992). «21.2 Convexity and size». Microeconomic Analysis (3rd έκδοση). W. W. Norton & Company. ISBN 978-0-393-95735-8. MR 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.

[51] 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 differentiable approach. Econometric Society monographs. 9. Cambridge University Press. ISBN 0-521-26514-2. MR 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. σελίδες viii+251. ISBN 978-0-691-04189-6. MR 0389160.

[52] Starr (1997, p. 169): Starr, Ross M. (1997). «8 Convex sets, separation theorems, and non-convex sets in R^N (new chapters 22 and 25–26 in (2011) second ed.)». General equilibrium theory: An introduction (First έκδοση). Cambridge: Cambridge University Press. σελίδες xxiii+250. ISBN 0-521-56473-5. MR 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.

[53] Laffont (1988, pp. 63–65): Laffont, Jean-Jacques (1988). «3 Nonconvexities». 0-262-12127-1&id=O5MnAQAAIAAJ Fundamentals of public economics Check |url= value (βοήθεια). MIT. ISBN 0-262-12127-1. Εξωτερικός σύνδεσμος στο |publisher= (βοήθεια)

[54] 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) έκδοση). Cambridge, MA: MIT Press. σελίδες 107–125. ISBN 0-262-19443-0.

[55] 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]. σελίδες x+164. ISBN 0-12-370180-5. MR 0700688.

[56] 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. σελίδες xi+145. ISBN 0-521-28614-X. MR 0657578.

[Aubin-57] 57,0 ^57,1 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 έκδοση). Mineola, NY: Dover Publications, Inc. σελίδες xxxii+616. ISBN 978-0-486-46265-3. MR 2449499.

[Carter-58] Carter (2001, pp. 93–94, 143, 318–319, 375–377, and 416)

[59] Trockel (1984, p. 30): Trockel, Walter (1984). Market demand: An analysis of large economies with nonconvex preferences. Lecture notes in economics and mathematical systems. 223. Berlin: Springer-Verlag. σελίδες viii+205. ISBN 3-540-12881-6. MR 0737006.

[Bertsekas99-60] 60,0 ^60,1 Bertsekas (1999, p. 496): Bertsekas, Dimitri P. (1999). «5.1.6 Separable problems and their geometry». Nonlinear Programming (Second έκδοση). Cambridge, MA.: Athena Scientific. σελίδες 494–498. ISBN 1-886529-00-0.

[Rock23-61] Rockafellar (1997, p. 23)

[Ekeland74-62] 62,0 ^62,1 Ekeland, Ivar (1974). «Une estimation a priori en programmation non convexe» (στα French). Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Séries A et B 279: 149–151. ISSN 0151-0509. MR 395844.

[AubinEkeland-63] 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. MR 449695.
Aubin & Ekeland (1976) and Ekeland (1999, pp. 362–364) also considered the convex closure of a problem of non-convex minimization—that is, the problem defined as the closed convex hull of the epigraph of the original problem. Their study of duality gaps was extended by Di Guglielmo to the quasiconvex closure of a non-convex minimization problem—that is, the problem defined as the closed convex hull of the lower 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. MR 484418.

[64] Schneider & Weil (2008, p. 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. MR 2455326.

[65] 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. MR 385711. http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2075868&fulltextType=RA&fileId=S0305004100051884ER.

[66] 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. σελίδες 194–240. doi:10.1007/1-84628-150-4. ISBN 978-1-84996-949-9. MR 2132405.

[PurRal85-67] 67,0 ^67,1 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. doi:10.1017/S0305004100062691. MR 764504. http://journals.cambridge.org/action/displayAbstract?aid=2087952.

[68] 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. MR 663901.

[69] 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. MR 1487361. http://www.ams.org/journals/proc/1999-127-08/S0002-9939-99-04788-7. Cerf uses applications of the Shapley–Folkman lemma from Puri & Ralescu (1985, pp. 154–155).

[70] Ruzsa (1997, p. 345): Ruzsa, Imre Z. (1997). «The Brunn–Minkowski inequality and nonconvex sets». Geometriae Dedicata 67 (3): 337–348. doi:10.1023/A:1004958110076. MR 1475877.

[Tardella-71] 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. MR 1040471.

[72] 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. Vind's article was noted by the winner of the 1983 Nobel Prize in Economics, Gérard Debreu Debreu (1991, p. 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. Convexity 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.

[Artstein-73] Artstein (1980, pp. 172–183) Artstein (1980) was republished in a festschrift for Robert J. Aumann, winner of the 2008 Nobel Prize in Economics: Artstein, Zvi (1995). «22 Discrete and continuous bang–bang and facial spaces or: Look for the extreme points». Στο: Hart, Sergiu· Neyman, Abraham. Game and economic theory: Selected contributions in honor of Robert J. Aumann. Ann Arbor, MI: University of Michigan Press. σελίδες 449–462. ISBN 0-472-10673-2.

[MCBlock78-74] Mas-Colell (1978, p. 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. MR 514468. http://www.sciencedirect.com/science/article/B6VBY-4582G5H-2G/2/576b6893a9a730c3557fde0f52d3a9c2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

[74]