Birkhoff多胞形是指由所有n×n雙隨機矩陣構成的凸多胞形，其頂點由n×n置換矩陣構成。該多胞形位於R{n^2}空間中，維度為(n-1)^2，具有n^2個面和n!個頂點。
這一概念被推廣至高維張量，研究線隨機與面隨機張量的多胞體，並給出了其頂點數量的上界比較。
針對帶Birkhoff多面體約束的最佳化問題，如最優傳輸問題和二次指派問題，研究提出了非精確Bregman鄰近梯度法等求解方法。另有研究運用疊代洛朗級數方法對Birkhoff多胞形Ehrhart多項式的留數計算進行了探討。在深度學習領域，有研究通過Sinkhorn-Knopp算法將連線矩陣約束在Birkhoff多胞形上以提升模型訓練穩定性。
基本介紹
- 定義：n階雙隨機矩陣構成的凸多胞形
- 套用：最優傳輸問題、二次指派問題
- 維度：(n-1)^2
- 面數：n個
- 頂點：n階置換矩陣
- 頂點數：n!個
套用領域,定義與定理,高維推廣,性質與結構,數值方法,
套用領域
帶Birkhoff多面體約束的最佳化問題在機器學習和數據科學等領域有著重要的套用，例如最優傳輸問題、Gromov-Wasserstein距離的計算、二次指派問題和圖匹配問題等等。
在深度學習領域，Birkhoff多胞形被用於提升模型訓練穩定性。DeepSeek團隊提出的mHC（流形約束超連線）架構運用Sinkhorn-Knopp算法將殘差連線矩陣投影到Birkhoff多胞形上，使信號傳播變為特徵的“凸組合”，從而保證了前向信號與後向梯度的穩定流動，解決了訓練不穩定問題。
定義與定理
一個方陣是雙隨機的，如果其所有元素非負且每行及每列的和均為1。
經典的Birkhoff多胞形定理指出，n×n雙隨機矩陣構成的多胞形由n×n置換矩陣生成。等價地，一個n×n矩陣是雙隨機的，若且唯若它是某些n×n置換矩陣的凸組合。
n×n隨機矩陣在R^{n^2}中的Birkhoff多胞形維度為(n-1)^2，具有n^2個面和n!個頂點。
該定理可推廣至多維數組（即超矩陣或張量）。一個n×n×n隨機張量是一個非負數組，其中任一索引上的和均為1。研究這些張量構成的多胞形，焦點之一是其頂點數目的上下界估計。
高維推廣
Birkhoff多胞形定理已被推廣到多維數組，即張量或超矩陣。研究線隨機張量與面隨機張量對應的多面體，或研究所有n×n×n隨機張量構成的多面體。研究通過多種方法給出了這些多面體頂點數目的上界，並比較了這些上界，同時關注頂點數的上下界。
性質與結構
Birkhoff多胞形為n階雙隨機矩陣構成的凸多胞形。其概念可推廣至多維數組即張量，研究線隨機和面隨機張量多胞體的頂點數上界及其比較。有研究運用疊代洛朗級數方法對Birkhoff多胞形Ehrhart多項式的留數進行計算。
數值方法
求解帶Birkhoff多面體約束的非凸最佳化問題在機器學習和數據科學等領域有著重要的套用，例如最優傳輸問題、Gromov-Wasserstein距離的計算、二次指派問題和圖匹配問題等。求解該類問題的一類有效算法是Bregman鄰近梯度法，然而算法的每一步需要精確求解子問題，使得整體的計算量較高。Yang和Toh針對求解帶Birkhoff多面體約束乃至一般凸約束的凸最佳化問題提出了非精確Bregman鄰近梯度算法，其中非精確準則的選擇具有很高的靈活性和自適應性，使得算法整體具有很高的效率。該方法已被推廣用於求解帶Birkhoff多面體約束的非凸最佳化問題，並在Kurdyka-Lojasiewicz條件和合理假設下證明了算法產生點列的收斂性。通過對QAPLIB的二次指派問題的數值實驗表明了算法的有效性。
