沙普利-福克曼引理

沙普利-福克曼引理是的一條引理，其於數理經濟學有應用。引理描述向量空間子集的閔可夫斯基和有何性質。若干個集合的閔可夫斯基和，即從各集合分別取一個元素相加，組成的集合：例如，將整數formula_1和formula_2組成的集合，與自身相加，得到由formula_3組成的集合，以符號可寫成：formula_4「許多個集合的閔氏和，是否必定近似凸集？」沙普利-福克曼引理和相關的結果表明，問題的答案為肯定。集合稱為凸，意思是連線其中任意兩點的線段，必為該集合的子集：舉例，實心圓盤 formula_5 為凸集，但圓 formula_6 則不然，因為連線相異兩點的線段 formula_7 並不是圓的子集。沙普利-福克曼引理大致斷言，若求和項的數目超出向量空間的維數，則其閔氏和將近凸。沙普利-福克曼引理引入時，是作為證明沙普利-福克曼定理的一步，該定理斷言閔氏和與其凸包的距離不超過某個上界。所謂集合formula_8的凸包，是包含formula_8的最小凸集。而當且僅當和為凸時，上述距離為零。定理中，距離的上界取決於維數formula_10及求和項的形狀，但不取決於求和的項數formula_11，而只需formula_12。只要其中formula_13個求和項的形狀，就足以確定formula_11個集合的閔可夫斯基平均集formula_15與其凸包的距離的上界。當formula_11趨向無窮時，該上界遞減至零的推論將沙普利-福克曼定理的上界壓得更低，故又稱為沙普利-福克曼-斯塔定理。勞埃德·沙普利和的引理，最先由經濟學家發表，其時斯塔正在肯尼斯·阿羅門下，研究經濟均衡的存在性。斯塔在論文中，研究凸化都著重。沙普利-福克曼引理在最佳化論和機率論皆有應用。最佳化論中，可以引理解釋，在求多個函式之和的最小值時，為何一些解法可以成功。機率論中，引理適用於證明的「大數定律」。此定理先前僅在凸集的情況得證。簡單例子.考慮凸的實數區間formula_17，其包含整數子集formula_18，且是其凸包。僅得兩個元素的集合formula_18，複製成三份，並按元素求和，得到formula_20和集的凸包則為區間formula_21。區間formula_21中，每個數formula_23都可以寫成區間formula_24中某三個實數，與formula_17中某一個實數之和。凸包formula_29中的點，到formula_30的距離，至多為formula_31：formula_32然而，考慮三個區間formula_24的閔氏平均formula_34與其凸包formula_29的距離，僅為formula_36，即未平均前formula_18與formula_17距離的三分之一。越多個集合相加，其閔氏平均就將凸包填得越滿：由閔氏平均至凸包的最遠距離，隨被加項數增加，而趨向於零。此為沙普利-福克曼定理的結論。前置概念.沙普利-福克曼引理需要用到的若干定義和定理，本節將作簡介。實向量空間.二維的實向量空間上，有笛卡兒坐標系，將每點視為一對實數，稱為「坐標」，按慣例記為formula_40。笛卡兒平面上的兩點，可以逐個坐標相加：formula_41此外，點也可以逐個坐標與實數formula_42相乘：formula_43更一般而言，任何formula_44維實向量空間，均可視為formula_44個實陣列成的"D"元組的集合formula_46，並配備兩種運算：向量加法和標量乘法。有限維實空間的此兩種運算，皆定義成逐個坐標運算，與笛卡兒平面上的運算類似。凸集.實向量空間中，非空子集formula_47稱為凸集，意思是，對於formula_47的任意兩個點，連線兩點成一線段，其上的所有點仍在formula_47中。例如，實心圓盤 formula_5 為凸，但圓 formula_6 則不然，因為連線相異兩點的線段 formula_7 並不是圓的子集。三個整數的集合formula_53非凸，但其為區間formula_54的子集，而該區間為凸。又例如，實心立方體為凸，然而任何空心或凹陷的圖形，如，則非凸。空集也是凸集，視乎作者偏好，這可能是專門的定義，也可能是因為要滿足的條件是。更嚴謹而言，集合formula_47稱為凸，意思是，對formula_47中任意兩點formula_57，和單位區間formula_58中的任意實數formula_59，點formula_60仍是formula_47的元素。由數學歸納法，集合formula_47為凸，當且僅當其任意多個元素的凸組合仍在formula_47中。所謂向量空間子集formula_64的凸組合，是其元素的任意加權平均formula_65，而各formula_66可以是總和為formula_67的任意非負實數，即只需formula_68。凸集的定義推出，兩個凸集的交集仍是凸集。更甚者，任意一族凸集的交也是凸集。作為特例，若取兩個不交的凸集，則其交集為空集，故應當稱空集為凸。凸包.對於實向量空間的每個子集formula_8，其凸包formula_70是包含formula_8的最小凸集。所以，formula_72是所有覆蓋formula_8的凸集的交。等價地，可以將formula_72定義成formula_75的點的所有凸組合的集合。作為例子，整數集合formula_27的凸包，是實數閉區間formula_58，其兩端為原有的整數formula_78。單位圓的凸包則是閉單位圓盤，其包含單位圓。閔可夫斯基和.在任何向量空間formula_79中，兩個非空子集formula_80的閔可夫斯基和，定義為其元素之和的集合，即 formula_81（。例如：formula_82此運算定義在非空子集族上，且滿足結合律和交換律。既然有結合律和交換律，就可以遞迴定義多個被加項的運算結果formula_83。由數學歸納法，可見formula_84閔可夫斯基和的凸包.閔可夫斯基和與凸包運算可以交換。具體而言，對實向量空間formula_85的任意子集formula_86，其閔氏和的凸包等於其凸包的閔氏和。換言之，formula_87故由數學歸納法得formula_88對任意formula_89和非空子集formula_90成立。各命題的敍述.由前一段的恆等式，對和的凸包中的每點formula_92，都存在各凸包的formula_93，使得formula_97。各點formula_98的位置取決於formula_23。引理.有了以上背景，沙普利-福克曼引理斷言，formula_100的表示法formula_101中"，"僅需要不多於formula_10個被加項formula_103取自凸包，而其他被加項，則只需取自原來的集合formula_104。以符號復述，即有以上方法表示formula_100，且滿足formula_106。不妨將下標重新排序，然後就有formula_107其中對formula_108，有formula_109，而對formula_110，則有formula_111。注意，倘若重排，則排序的方式也取決於點formula_100。再精簡，沙普利-福克曼引理可以寫成formula_113舉例，集合formula_114中的每個點，根據引理，必定可以寫成formula_115的某個元素，與formula_116的某個元素之和。實向量空間的維數.反之，沙普利-福克曼引理刻劃了有限維實向量空間的維數。具體而言，若某向量空間，對於某個自然數formula_10滿足引理的結論，但對小於formula_10的數不滿足，則其維數恰好為formula_10。引理僅對有限維向量空間成立。沙普利-福克曼定理及斯塔的推論.沙普利與福克曼運用其引理，證明沙普利-福克曼定理，給出集合的閔氏和與其凸包。上述定理給出閔氏和及其凸包之間距離的上界。當且僅當閔氏和為凸集時，此距離為零。該上界取決於維數formula_10及各被加項的形狀，但只要formula_12，就不取決於項數formula_11。通常，外接半徑會大於內半徑，而無論如何，外接半徑總不能小於內半徑。集合formula_104的內半徑定義為：最小的正實數formula_130，滿足：若formula_131在formula_132凸包中，則formula_131在formula_132若干點的凸包中，而該些點皆在同一個半徑為formula_130的球內。斯塔將沙普利-福克曼定理中的外接半徑換成內半徑，從而壓低沙普利-福克曼定理的上界：沙普利-福克曼定理的斯塔推論：凸化和formula_120的任一點，到和集formula_121的歐氏距離平方，不超過各集合formula_104的內半徑中，最大formula_10個的平方和。斯塔的推論確定，formula_11個集合的閔氏和與其凸包之間，歐氏距離的上界。此距離可以衡量閔氏和非凸的程度，故為簡單起見，下文稱為非凸度。於是，斯塔對非凸度的上界，僅取決於formula_10個最大內半徑之值，但不取決於求和的項數formula_11。例如，非凸集formula_144的非凸度為formula_39，因為與其凸包的距離為formula_147所以，既然formula_121的非凸度有不取決於項數formula_11的上界，就知平均集formula_150非凸度上界，會隨formula_11增加而遞減。例如，平均集formula_152和其凸包formula_24的距離僅為formula_154，等於被加項formula_27與其凸包formula_156的距離。若使用斯塔的上界，則前一句結論的條件可以放寬，只需各求和項的內半徑有同一個上界。證明和計算.沙普利-福克曼引理的原證明，僅確定存在該種表示法，而無說明如何構造。阿羅與哈恩、、斯奈德問題與零和賽局的對偶間隙。應用.有沙普利-福克曼引理，學者就得將有關凸集閔氏和的結果，套用到一般集合之和。此種和見於經濟學、最最佳化理論、機率論。此三領域的應用中，非凸性起到重要作用。經濟學.經濟學中，消費者對每一「籃子」商品有其偏好程度。每籃子可用一個非負向量表示，其坐標為籃中各商品的量。所有籃子組成的集合中，每個消費者有自己的一族無差異曲線，滿足：在同一條曲線上的各籃子，對該消費者是等價的，即消費者並不覺該曲線上有籃子勝於另一個籃子。每籃子恰好處於一條無差異曲線上。消費者相對於一條無差異曲線的偏好集，定義為該無差異曲線與其更偏好的區域的並集。稱消費者的偏好為凸，意思是其所有偏好集皆為凸。如圖所示，消費者認為的最優籃子，是在預算線某個偏好集時取到，因為此時，所選的籃子是整條預算線上，達到最高的無差異曲線的一點。所謂預算線，是由商品的價格向量與消費者的收入計算得出的限制，消費者無足夠收入購買高於此線的籃子。所以，最優籃子的集合是各價格的函式，稱為消費者的需求。若偏好集為凸，則不論價格為何，消費者認為的最優籃子總是組成凸集，例如可能是單元集，或是一條線段。非凸偏好.然而，若有偏好集非凸，則某些價格確定的預算線，可能在兩個分開的最優籃子支撐該偏好集。例如，可以設想，動物園購買獅子或鷹的價錢一樣，且其預算恰好夠買一隻獅子或一隻鷹。此外，假設園主亦認為兩隻動物價值相同，則動物園有可能買獅子，也可能買鷹，但當然不可能買半隻獅子加半隻鷹。所以，園主的偏好非凸：買兩隻動物中的任一隻，勝於兩者的嚴格凸組合。若消費者有非凸偏好集，則對於某些價格，需求不連通。不連通的需求，會導致消費者的行為出現不連續的間斷。引述哈羅德·霍特林的話：若考慮波浪形的無差異曲線，即在某些區域向原點凸，而在其他區域向原點凹，則我等被迫推論，僅有向原點凸的部分需要理會，因為幾乎不可能觀測到其他部分。要偵測該些部分，唯一方法是，觀察價格之比率變化時，需求的不連續變化。此變化的效果是，當直線旋轉時，切點會突然躍過某凹陷。雖然此種不連續的表現，揭示有凹陷，但卻不可能量度缺口的深度。倘若無差異曲線，或其高維推廣，有凹陷部分，則定必因永遠無法測量，而不為人知。書中，稱有強調研究非凸偏好的困難，也引述保羅·薩繆爾森稱凹陷處「被永恆的黑暗遮蔽」。儘管有上述困難，《》。斯塔1969年的論文與當代經濟學.肯尼斯·阿羅收集前人研究的列成表，並加入註解，交給。斯塔當時仍是本科生，但已在修讀阿羅開設的高等數理經濟學課程。斯塔在學期論文中，考慮將非凸偏好換成其凸包所得的假想經濟體，研究其一般均衡。凸化經濟體中，在每個價位，總需求皆是各消費者需求的凸包之和。斯塔的想法吸引數學家勞埃德·沙普利和參與，兩人「在私人通訊中」證明現以兩人命名的引理和定理，到1969年，斯塔才於論文報告此事。斯塔1969年的論文中，應用沙普利-福克曼-斯塔定理，證明「凸化」經濟體有一些一般均衡，只要參與者足夠多，能以原經濟體的「準均衡」近似。具體而言，斯塔證明，至少存在一個價格向量為formula_161的準均衡，滿足下列條件：斯塔確立以下結論：「總體中，［取各消費及生產集的凸包］所得的假想經濟體的分配，與真實經濟體的某個分配，兩者的差異，有不取決於參與者數目的上界。因此，當參與者數目趨向無窮時，平均參與者感受到，與擬作行動的偏差，近乎可以忽略不計。」斯塔1969年論文發表後，沙普利-福克曼-斯塔的結論，在經濟理論獲廣泛應用。如此總結該結論對經濟學的意義：「假設凸性，所得的若干重要結果，在不具凸性的情況下，仍都著重。沙普利-福克曼-斯塔的結論，在經濟學各分支的經常出現，包括微觀經濟學、一般均衡理論、公共經濟學、博弈論、數理經濟學、經濟學中的應用數學。沙普利-福克曼-斯塔的結論，也使經濟學更多使用測度論和積分理論。最最佳化理論.沙普利-福克曼引理可以解釋，為何大規模的最小化問題，即使非凸，仍可用迭代法近似求解函式之和。最最佳化理論的前置概念.非線性規劃依賴下列有關函式的若干定義：formula_168formula_170舉例，二次函式formula_171為凸，而絕對值函式formula_172亦然，但正弦函式formula_173。加性最佳化問題.許多最佳化問題中，目標函式formula_175可分離變數，即formula_175是多個函式之和，而各個函式的引數不同，如：formula_177又例如，線性規劃問題就可分離變數。考慮一個可分問題，及一個最優解formula_178在該點取到最小值formula_179。對此可分問題，同時考慮其「凸化問題」的最優解，即將每個求和項formula_180的影象換成其凸包。此種最優解，會是凸化問題的某點列formula_181的極限，其中formula_182當然，因為此點是formula_183個影象凸包的點之和，由沙普利-福克曼引理，就可以寫成原影象的點與少數影象凸包的點之和。以上分析，1974年由發表，以解釋為何可分問題有許多項時，即使各項非凸，總問題仍看似凸。對非線性最小值問題而言，對偶問題的解，不一定就是原問題的解，但是，1973年，青年數學家詫異，對已知非凸的問題使用凸問題的方法，竟然也成功。勒馬雷沙爾的問題，正是上段加性可分離變數的形式，而每個和項皆非凸函式，但對偶問題的解，仍近似原問題的最優解。埃科蘭德的分析說明，「大而可分」的最小值問題，即使各和項有凹陷，仍可運用凸最佳化的方法。埃科蘭德及其後的作者主張，因為變數可以加性分離，所得的總問題近似凸。該等著作以沙普利-福克曼引理為關鍵一步。沙普利-福克曼引理促使學者將凸最佳化方法，應用到目標函式為多個函式之和的情況。機率與測度論.凸集常與機率論一同研究。說明，formula_184維空間的子集formula_75凸包中的點，是取值於formula_75的簡單的期望值，而所謂簡單，意思是僅在不多於formula_187個點處有非零機率。所以，對非空集formula_75，取值自formula_75的簡單隨機向量組成的集合，等於formula_75的凸包。由此便可在機率論中，套用沙普利-福克曼-斯塔的結果。反之，藉期望值與凸包之間的聯絡，機率論亦能用作研究凸集，尤其可用作分析沙普利-福克曼-斯塔的結果。沙普利-福克曼-斯塔的結果，廣泛用於，例如證明隨機集的大數定律、中央極限定理、。要證明前列機率極限定理，可以使用沙普利-福克曼-斯塔的結果，來避免假設隨機集為凸。機率測度是有限的測度，而沙普利-福克曼引理還可以應用到非機率的測度論，如體積或向量測度的理論。沙普利-福克曼引理可以加強。該不等式斷言，閔氏和的體積，相較於各和項的體積不能太大，即閔氏和的體積有上界，以各和項的體積的表示。歐氏空間子集的體積，此處定義為其勒貝格測度。高等測度論中，沙普利-福克曼引理適用於證明李亞普諾夫定理，即向量測度的值域為凸。值域是函式所有可能取值的集合，而向量測度則將測度推廣到允許取向量值。例如，若某測度空間有兩種機率測度formula_191和formula_192，則可定義一個向量測度formula_193，是對每個事件formula_194，將其兩個機率結合為一個二元組，即formula_195李亞普諾夫定理在經濟學、(砰砰)控制論、皆有應用。李亞普諾夫定理是沙普利-福克曼引理的連續版，而沙普利-福克曼引理是李亞普諾夫定理的離散類比。