Λήμμα των Σάπλεϊ-Φόλκμαν

 Αυτό το λήμμα χρειάζεται επιμέλεια ώστε να ανταποκρίνεται σε υψηλότερες προδιαγραφές ορθογραφικής και συντακτικής ποιότητας ή μορφοποίησης.
Αίτιο: μετάφραση λέξεων, διόρθωση συνδέσμων
Για περαιτέρω βοήθεια, δείτε τα λήμματα πώς να επεξεργαστείτε μια σελίδα και τον οδηγό μορφοποίησης λημμάτων.
The Shapley–Folkman lemma depicted by a diagram with two panes, one on the left and the other on the right. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. Comparing the left array and the right pane, one confirms that the right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.
Το λήμμα των Σάπλει-Φόλκμαν απεικονίζεται από το άθροισμα Μινικόφσκι σε τέσσερα σύνολα. Το σημείο (+) στο κυρτό του κύτους του αθροίσματος Μινικόφσκι των τεσσάρων μη κυρτών συνόλων (δεξιά) είναι το άθροισμα των τεσσάρων σημείων (+) από τα (αριστερά) συνόλων δύο σημείων σε δύο μη-κυρτά σύνολα συν δύο σημεία στα ύφαλα κυρτά δύο σύνολα. Τα κυρτά κύτη είναι σκιασμένα ροζ. Τα αρχικά σύνολα, το καθένα έχει ακριβώς δύο σημεία (εμφανίζονται ως κόκκινες κουκκίδες).)[1]

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

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

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

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

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

και το κυρτό του κύτους του. Όσο το Ν πηγαίνει στο άπειρο, τα δεσμευμένα μειώνεται στο μηδέν (για summand-σύνολα ομοιόμορφα και φραγμένου μεγέθους).[3] Το πάνω όριο του θεωρήματος των Σάπλεϊ- Φόλκμαν μειώθηκε από πόρισμα του Σταρ (εναλλακτικά, το θεώρημα Shapley-Folkman-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].[8]

Η απόσταση μεταξύ του κυρτού διαστήματος [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. Δύο σημεία στο καρτεσιανό επίπεδο μπορούν να προστεθούν ως συντεταγμένες

(x1, y1) + (x2, y2) = (x1+x2, y1+y2)

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

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

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

Κυρτά σύνολα

Illustration of a convex set, which looks somewhat like a disk: A (green) convex set contains the (black) line-segment joining the points x and y. The entire line-segment is a subset of the convex set.
Σε ένα κυρτό σύνολο Q, το ευθύγραμμο τμήμα που συνδέει δύο οποιαδήποτε από τα σημεία του είναι ένα υποσύνολο του Q.
Illustration of a green non-convex set, which looks somewhat like a boomerang or cashew nut. The black line-segment joins the points x and y of the green non-convex set. Part of the line segment is not contained in the green non-convex set.
Σε ένα μη-κυρτό σύνολο Q, ένα σημείο σε κάποιο ευθύγραμμο τμήμα που ενώνει δύο από τα σημεία του δεν είναι μέλος της Q.
Τα ευθύγραμμα τμήματα ελέγχουν αν ένα υποσύνολο να είναι κυρτό.

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

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

(1 − λ) v0 + λv1

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

Με μαθηματική επαγωγή, ένα σύνολο Q είναι κυρτό αν και μόνο αν κάθε κυρτός συνδυασμός των μελών της Q ανήκει επίσης στην Q. Εξ ορισμού, ένας κυρτός συνδυασμός ενός αναπροσαρμοσμένου υποσύνολο {v0, v1, . . . , vD} του διανυσματικού χώρου είναι κάθε σταθμισμένος μέσος όρος λ0v0 + λ1v1 + . . . + λDvD,

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

λ0 + λ1 + . . .  + λD = 1.[11]

Ο ορισμός ενός κυρτού συνόλου συνεπάγεται ότι το σημείο τομής των δύο κυρτών συνόλων είναι ένα κυρτό σύνολο. Γενικότερα, η τομή μιας οικογένειας κυρτών συνόλων είναι ένα κυρτό σύνολο. Ειδικότερα, η τομή δύο διακριτών συνόλων είναι το κενό σύνολο, το οποίο είναι κυρτό.[10]

Κυρτό κύτους

A picture of a smoothed triangle, like a triangular (Mexican) tortilla-chip or a triangular road-sign. Each of the three rounded corners is drawn with a red curve. The remaining interior points of the triangular shape are shaded with blue.
Στο κυρτό κύτους του κόκκινου συνόλου, κάθε μπλε σημείο είναι ένας κυρτός συνδυασμός με μερικά κόκκινα σημεία

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

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

Three squares are shown in the non-negative quadrant of the Cartesian plane. The square Q1=[0,1]×[0,1] is green. The square Q2=[1,2]×[1,2] is brown, and it sits inside the turquoise square Q1+Q2=[1,3]×[1,3].
Η Μινικόφσκι πρόσθεση συνόλων. Το άθροισμα των τετραγώνων Q1=[0,1]2 και Q2=[1,2]2 είναι το τετράγωνο Q1+Q2=[1,3]2.

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

Q1 + Q2 = { q1 + q2 : q1 ∈ Q1 and q2 ∈ Q2 }.[13]

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

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

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

∑ Qn = {∑ qn : qn ∈ Qn}.[14]

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

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

Conv( Q1 + Q2 ) = Conv( Q1 ) + Conv( Q2 ).

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

Conv(  ∑ Qn  ) = ∑ Conv( Qn ).[15][16]

Δηλώσεις

The Shapley–Folkman lemma depicted by a diagram with two panes, one on the left and the other on the right. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. The right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.
Η προσθήκη Μινικόφσκι και τα κυρτά κύτους. Τα δεκαέξι σκούρα κόκκινα σημεία (στα δεξιά) σχηματίζουν το Minkowski άθροισμα των τεσσάρων μη κυρτών συνόλων (στα αριστερά), καθένα από τα οποία αποτελείται από ένα ζευγάρι κόκκινα σημεία. Τα κυρτά κύτοι τους (σκιασμένη ροζ) περιέχουν θετικά-σημεία (+): Το δεξιά θετικό πρόσημο είναι το άθροισμα του αριστεράς θετικού προσήμου.

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

x ∈ Conv( ∑ Qn )

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

x ∈ ∑ Conv( Qn ).

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

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

Picture of Lloyd Shapley
Ο νικητής του Βραβείου Νόμπελ στα Οικονομικά το 2012, Lloyd Shapley απέδειξε το λήμμα Shapley-Folkman με τον Jon Folkman.[1]

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

D < N

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

όπου qd ανήκει στο κυρτό του κύτους του Qd για το D (ή μικρότερες) summand-σύνολα και qn ανήκει στην ίδια Qn με τις υπόλοιπες ομάδες. Δηλαδή,

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

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

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

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

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

A blue disk contains red points. A smaller green disk sits in the largest concavity in among these red points.
Ο περιγεγραμμένος κύκλος (μπλε) και η εσωτερική ακτίνα (πράσινο) από ένα σύνολο σημείων (σκούρο κόκκινο, με το κυρτό κύτους του να εμφανίζεται ως το πιο ανοιχτό κόκκινο διακεκομμένες γραμμές). Η εσωτερική ακτίνα είναι μικρότερη από την ακτίνα του κύκλου εκτός από τα υποσύνολα ενός ενιαίου κύκλου, για τα οποία είναι ίσα.

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

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

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

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

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

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

  • Το πόρισμα του Σταρ πάνω στο θεώρημα Σάπλει-Φόλκμαν αναφέρει ότι η τετραγωνισμένη Ευκλείδεια απόσταση από οποιοδήποτε σημείο x στο άθροισμα κύτους Conv( ∑ Qn ) με το αρχικό (μη κύτος) άθροισμα ∑ Qnοριοθετείται από το άθροισμα των τετραγώνων των D που είναι μεγαλύτερη της εσωτερικής ακτίνας του συνόλου Qn.[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|.

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

1⁄N ∑ Qn

μειώνεται καθώς ο αριθμός των 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]

Εφαρμογές

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

Οικονομικά

The nonnegative quadrant of the Cartesian plane appears. A blue straight-line slopes downward as a secant joining two points, one on each of the axes. This blue line is tangent to a red curve that touches it at a marked point, whose coordinates are labeled Qx and Qy.
Ο καταναλωτής προτιμά κάθε καλάθι αγαθών πάνω στην καμπύλη αδιαφορίας I3 από κάθε καλάθι της I2 . Το καλάθι (Qx, Qy), όπου η γραμμή του προϋπολογισμού (μπλε) αναπαριστά την I2, είναι η βέλτιστη, αλλά και εφικτή, σε αντίθεση με κάθε καλάθι που βρίσκεται στο I3 το οποίο είναι ανέφικτο.

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

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

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

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

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

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

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

An image of a convex preference set being supported by a budget line.
With "quasi-equilibrium" prices, the budget-line supports the convex hull of the indifference curve.

Οι δυσκολίες της μελέτης σε μη κυρτές προτιμήσεις τονίζεται από τον Herman Wold[35] και πάλι από τον Paul Samuelson, ο οποίος έγραψε ότι οι μη κυρτές είναι «τυλιγμένες στο αιώνιο σκοτάδι ...»,[36] σύμφωνα με τον Diewert.[37]

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

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

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

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

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

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

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

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

Μετά το 1969 η εργασία του Starr και τα αποτελέσματα των Shapley-Folkman-Starr έχουν χρησιμοποιηθεί ευρέως στην οικονομική θεωρία. Ο Roger Guesnerie συνοψίζει τις οικονομικές επιπτώσεις τους: «Μερικά βασικά αποτελέσματα που επιτεύχθηκαν με την παραδοχή της κυρτότητας παραμένει (περίπου) σχετικό σε περιπτώσεις όπου δεν υπάρχει κυρτότητα. Για παράδειγμα, σε οικονομίες με μεγάλη πλευρά κατανάλωσης, οι nonconvexities προτίμησεις δεν καταστρέφουν τα πρότυπα αποτελέσματα».[49] «Η παραγωγή αυτών των αποτελεσμάτων σε γενική μορφή υπήρξε ένα από τα σημαντικότερα επιτεύγματα της μεταπολεμικής οικονομικής θεωρίας», έγραψε ο 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).[50] Τα αποτελέσματα των Shapley-Folkman-Starr έχουν προβληθεί στην οικονομική βιβλιογραφία : στην μικροοικονομική θεωρία,[51] στην κλασική θεωρία της γενικής ισορροπίας,[52][53] στα δημόσια οικονομικά [54] (συμπεριλαμβανομένων των ανεπαρκειών της αγοράς),[55] καθώς και στην θεωρία των παιγνίων,[56] στη μαθηματική οικονομία,[57] και στα εφαρμοσμένα μαθηματικά (για τους οικονομολόγους).[58][59] . Τα αποτελέσματα των Shapley-Folkman-Starr έχουν επίσης επηρεάσει την οικονομία της έρευνας με τη χρήση του μέτρου και της θεωρίας ολοκλήρωσης.[60]

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

A graph of a convex function, which is drawn in black. Its epigraph, the area above its graph, is solid green.
Μια συνάρτηση είναι κυρτή, εάν η περιοχή πάνω στο γράφημα του είναι ένα κυρτό σύνολο.

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

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

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

Graph(f) = { (x, f(x) ) }
A graph of the sine function, which periodically oscillates up and down between −1 and +1, with the period 2π.
Η συνάρτηση ημχ είναι μη- κυρτή.
Epi(f) = { (x, u) : f(x) ≤ u }.
  • Μια πραγματική συνάρτηση ορίζεται να είναι μια κυρτή συνάρτηση αν η επιγραφή του είναι ένα κυρτό σύνολο.[62]

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

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

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

f(x) = f( (x1, ..., xN) ) = ∑ fn(xn).

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

xmin = (x1, ..., xN)min

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

(xj, f(xj) ) ∈  ∑ Conv (Graph( fn ) ).[5]

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

Η ανάλυση αυτή δημοσιεύθηκε από τον Ivar Ekeland το 1974 για να εξηγήσει την φαινομενική κυρτότητα των διαχωρίσιμων προβλημάτων με πολλά summands, παρά τη μη κυρτότητα των προβλημάτων summand. Το 1973, ο νεαρός μαθηματικός Claude Lemaráchall εξεπλάγη από την επιτυχία του με τη μέθοδο κυρτής ελαχιστοποίησης σχετικά με τα προβλήματα που ήταν γνωστά ως μη-κυρτά, για την ελαχιστοποίηση των μη γραμμικών προβλημάτων, η λύση του διπλού προβλήματος δεν χρειάζεται να παρέχουν χρήσιμες πληροφορίες για την επίλυση του προβλήματος, εκτός εάν το πρωταρχικό πρόβλημα είναι κυρτό και ικανοποιήσει έναν περιορισμό. Το πρόβλημα του LEMARECHAL ήταν ο διαχωρισμός προσθετέων, όταν κάθε λειτουργία summand ήταν μη-κυρτή. Παρ 'όλα αυτά, μια λύση στο πρόβλημα παρείχε μια στενή προσέγγιση στη βέλτιστη τιμή του αρχέγονου προβλήματος.[63][5][64]

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

[6][58][61]

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

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

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

(p1 p2)(ω)=(p1(ω), p2(ω)).

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

Παραπομπές

  1. ↑ 1,0 1,1 1,2 1,3 1,4 Starr (1969)
  2. ↑ 2,0 2,1 Howe (1979, p. 1): Howe, Roger (1979-11-03), 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, ανακτήθηκε στις 2011-01-01 
  3. ↑ 3,0 3,1 3,2 3,3 3,4 3,5 Starr (2008)
  4. ↑ 4,0 4,1 Guesnerie (1989, p. 138)
  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.
  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. Ανακτήθηκε στις 2011-02-02. 
  7. ↑ 7,0 7,1 Artstein & Vitale (1975, pp. 881–882)
  8. ↑ 8,0 8,1 8,2 8,3 8,4 Carter (2001, p. 94)
  9. ↑ Arrow & Hahn (1980, p. 375)
  10. ↑ 10,0 10,1 Rockafellar (1997, p. 10)
  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)
  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, Jonathan 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)
  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. (2005-03-14), «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, ανακτήθηκε στις 2011-01-01 
  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
    . Αρχειοθετήθηκε από το πρωτότυπο στις 2013-02-02. https://archive.today/20130202094407/http://www.sciencedirect.com/science/article/pii/0022053181900107. Ανακτήθηκε στις 2014-06-25.     
  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 (Ιανουάριος 1935). «Demand functions with limited budgets». Econometrica 3 (1): 66–78. 
  35. ↑ Wold (1943b, pp. 231 and 239–240): Wold, Herman (1943b). «A synthesis of pure demand analysis II». Skandinavisk Aktuarietidskrift [Scandinavian Actuarial Journal] 26: 220–263.
    MR 11939
    .     

    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. 
  36. ↑ 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. (Νοέμβριος 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).
  37. ↑ Diewert (1982, pp. 552–553)
  38. ↑ Farrell, M. J. (Αύγουστος 1959). «The Convexity assumption in the theory of competitive markets». The Journal of Political Economy 67 (4): 371–391. doi:10.1086/258197. https://archive.org/details/sim_journal-of-political-economy_1959-08_67_4/page/371.  Farrell, M. J. (Οκτώβριος 1961a). On Convexity, efficiency, and markets: A Reply. 69, σελ. 484–489.  Farrell, M. J. (Οκτώβριος 1961b). The Convexity assumption in the theory of competitive markets: Rejoinder. 69, σελ. 493. 
  39. ↑ Bator, Francis M. (Οκτώβριος 1961a). «On convexity, efficiency, and markets». The Journal of Political Economy 69 (5): 480–483. doi:10.1086/258540.  Bator, Francis M. (Οκτώβριος 1961b). On convexity, efficiency, and markets: Rejoinder. 69, σελ. 489. 
  40. ↑ Koopmans, Tjalling C. (Οκτώβριος 1961). «Convexity assumptions, allocative efficiency, and competitive equilibrium». The Journal of Political Economy 69 (5): 478–479. doi:10.1086/258539. https://archive.org/details/sim_journal-of-political-economy_1961-10_69_5/page/478. 

    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. 
  41. ↑ Rothenberg (1960, p. 447): Rothenberg, Jerome (Οκτώβριος 1960). «Non-convexity, aggregation, and Pareto optimality». The Journal of Political Economy 68 (5): 435–468. doi:10.1086/258363. https://archive.org/details/sim_journal-of-political-economy_1960-10_68_5/page/435.  (Rothenberg, Jerome (Οκτώβριος 1961). Comments on non-convexity. 69, σελ. 490–492. )
  42. ↑ Arrow & Hahn (1980, p. 182)
  43. ↑ Shapley & Shubik (1966, p. 806): Shapley, L. S.; Shubik, M. (Οκτώβριος 1966). «Quasi-cores in a monetary economy with nonconvex preferences». Econometrica 34 (4): 805–827. doi:10.2307/1910101.
    Zbl 154.45303
    . https://archive.org/details/sim_econometrica_1966-10_34_4/page/805.     
  44. ↑ 44,0 44,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
    . https://archive.org/details/sim_econometrica_1966-01_34_1/page/1.      Aumann (1966) uses results from

    Aumann (1964, 1965):

    Aumann, Robert J. (Ιανουάριος–Απρίλιος 1964). «Markets with a continuum of traders». Econometrica 32 (1–2): 39–50.
    MR 172689
    .      Aumann, Robert J. (Αύγουστος 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
    . Αρχειοθετήθηκε από το πρωτότυπο στις 2013-02-02. https://archive.today/20130202032422/http://www.sciencedirect.com/science/article/pii/0022247X65900491. Ανακτήθηκε στις 2014-06-25.     
  45. ↑ 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).
  46. ↑ 46,0 46,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. 
  47. ↑ Arrow & Hahn (1980, pp. 169–182). Starr (1969, pp. 27–33)
  48. ↑ Green & Heller (1981, p. 44)
  49. ↑ Guesnerie (1989, pp. 99)
  50. ↑ Mas-Colell (1987)
  51. ↑ Varian (1992, pp. 393–394): Varian, Hal R. (1992). «21.2 Convexity and size». Microeconomic AnalysisΑπαιτείται δωρεάν εγγραφή (3η έκδοση). 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. 

  52. ↑ 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. 
  53. ↑ Starr (1997, p. 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 (1η έκδοση). 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. 
  54. ↑ Laffont (1988, pp. 63–65): Laffont, Jean-Jacques (1988). «3 Nonconvexities». Fundamentals of public economics. MIT. ISBN 0-262-12127-1. 
  55. ↑ 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. 
  56. ↑ 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. 
  57. ↑ 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. 
  58. ↑ 58,0 58,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. 
  59. ↑ Carter (2001, pp. 93–94, 143, 318–319, 375–377, and 416)
  60. ↑ 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. 
  61. ↑ 61,0 61,1 Bertsekas (1999, p. 496): Bertsekas, Dimitri P. (1999). «5.1.6 Separable problems and their geometry». Nonlinear Programming (2η έκδοση). Cambridge, MA.: Athena Scientific. σελίδες 494–498. ISBN 1-886529-00-0. 
  62. ↑ Rockafellar (1997, p. 23)
  63. ↑ Lemaréchal (1973, p. 38): Lemaréchal, Claude (Απρίλιος 1973), Utilisation de la dualité dans les problémes non convexes [Use of duality for non–convex problems], Domaine de Voluceau, Rocquencourt, 78150 Le Chesnay, France: National Institute for Research in Computer Science and Control (IRIA), Laboratoire de recherche en informatique et automatique, σελ. 41 . Lemaréchal's experiments were discussed in later publications:

    Aardal (1995, pp. 2–3): Aardal, Karen (Μάρτιος 1995). «Optima interview Claude Lemaréchal». Optima: Mathematical Programming Society newsletter 45: 2–4. http://www.mathprog.org/Old-Optima-Issues/optima45.pdf. Ανακτήθηκε στις 2011-02-02. 

    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. Berlin: Springer-Verlag. σελίδες 136–193 (and bibliographical comments on pp.334–335). ISBN 3-540-56852-2. MR 1295240. 
  64. ↑ 64,0 64,1 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 279: 149–151. ISSN 0151-0509.
    MR 395844
    .     
  65. ↑ 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
    .     

  66. ↑ 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. Αρχειοθετήθηκε από το πρωτότυπο στις 9 Οκτωβρίου 2012. Ανακτήθηκε στις 25 Ιουνίου 2014. 
  67. ↑ 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.     
  68. ↑ 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. [νεκρός σύνδεσμος]
  69. ↑ 69,0 69,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.     
  70. ↑ 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
    .     
  71. ↑ 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).
  72. ↑ 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
    .     
  73. ↑ 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
    .     
  74. ↑ Vind (1964, pp. 168 and 175): Vind, Karl (Μάιος 1964). «Edgeworth-allocations in an exchange economy with many traders». International Economic Review 5 (2): 165–77. https://archive.org/details/sim_international-economic-review_1964-05_5_2/page/165.  Vind's article was noted by the winner of the 1983 Nobel Prize in Economics, Gérard DebreuDebreu (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 (Μάρτιος 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. 

  75. ↑ 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. Αρχειοθετήθηκε από το πρωτότυπο στις 24 Μαΐου 2011. Ανακτήθηκε στις 25 Ιουνίου 2014. 
  76. ↑ 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
    . Αρχειοθετήθηκε από το πρωτότυπο στις 2013-02-02. https://archive.today/20130202023110/http://www.sciencedirect.com/science/article/pii/0304406878900101. Ανακτήθηκε στις 2014-06-25.     

Πηγές

Εξωτερικοί σύνδεσμοι