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

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

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

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

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

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

Το λήμμα των Λόιντ Σάπλει και Τζον Φόλκμαν δημοσιεύθηκε για πρώτη φορά από τον οικονομολόγο Ρος Μ. Σταρ, ο οποίος ερευνούσε την ύπαρξη οικονομικής ισορροπίας ενώ σπούδαζε με τον Κένεθ Άροου.  Στο έγγραφό του, ο Σταρ μελέτησε την κυρτή μορφή της οικονομίας, όπου τα μη- κυρτά σύνολα αντικαταστάθηκαν από αντίστοιχα κυρτά˙ Ο Σταρ απέδειξε ότι η οικονομία έχει κυρτές ισορροπίες που προσεγγίζονται από τους "οιωνούς ισορροπίας" της αρχικής οικονομίας. Επιπλέον, αποδείχθηκε ότι κάθε οιωνός ισορροπίας έχει πολλές από τις καλύτερες δυνατές ιδιότητες της αληθινής ισορροπίας, τα οποία αποδείχθηκαν ότι υπάρχουν για κυρτές οικονομίες. Μετά την έκθεση του Σταρ το 1969, τα αποτελέσματα των Σάπλει- Φόλκμαν- Σταρ έχουν χρησιμοποιηθεί ευρέως για να δείξουν ότι τα βασικά αποτελέσματα των (κυρτών) οικονομικών θεωριών είναι καλής προσεγγίσεις σε μεγάλες οικονομίες μη κυρτές, για παράδειγμα, οιωνοί ισορροπίας σε στενή προσέγγιση ισορροπίας μίας κυρτής οικονομίας. «Η παραγωγή αυτών των αποτελεσμάτων σε γενική μορφή υπήρξε ένα από τα σημαντικότερα επιτεύγματα της μεταπολεμικής οικονομικής θεωρίας», έγραψε ο Roger Guesnerie. Το θέμα των μη κυρτών συνόλων στα οικονομικά έχει μελετηθεί από πολλούς νομπελίστες, εκτός από τον Λόιντ Σάπλει που κέρδισε το βραβείο το 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).

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

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

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

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

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

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

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

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

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

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

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

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

Κυρτά σύνολα 

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

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

 (1 − λ) v0 + λv1

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

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

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

 = 1.

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

Κυρτό κύτους 

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

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

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

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

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

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

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

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

 ∑ Qn = {∑ qn : qn ∈ Qn}.

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

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

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

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

 Conv(  ∑ Qn  ) = ∑ Conv( Qn ).

Δηλώσεις 

Η προηγούμενη ταυτότητα 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.

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  ∑ 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-σύνολα ομοιόμορφα οριοθετούνται μέγεθος). Στην πραγματικότητα, η δέσμευση του Σταρ στη μη κυρτότητα αυτής της μέσης συνόλων μειώνεται στο μηδέν καθώς ο αριθμός των summands Ν αυξάνεται έως το άπειρο (όταν οι εσωτερικές ακτίνες όλων των summands οριοθετούνται από τον ίδιο αριθμό).

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

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

Εφαρμογές 

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

Οικονομικά 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 (xj, f(xj) ) ∈  ∑ Conv (Graph( fn ) ).

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

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

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

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

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

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

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

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

Παραπομπές

Πηγές

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