深度學(xué)習(xí)+離散的M-K理論不足以支持深入研究，因?yàn)槠浣Y(jié)構(gòu)不具有豐富性。

推薦書(shū)籍《最有傳輸理論和計(jì)算》

## 離散的傳輸問(wèn)題

注1：純離散問(wèn)題，目標(biāo)函數(shù)+約束函數(shù)都是線性函數(shù)。目標(biāo)是總成本的代價(jià)越低越好

注2：$p_1,\cdots,p_m$是生產(chǎn)者，$q1,\cdots,q_n$是消費(fèi)者。從$p_i$傳遞到$q_j$需要消耗成本$c(p_i,q_j)$，$\gamma_{ij}$表示從i到j(luò)的傳輸量

注3：第$i$個(gè)生產(chǎn)者的生產(chǎn)總量為$\mu_i$,第$j$個(gè)消費(fèi)者的消費(fèi)總量為$v_j$.

注4：生產(chǎn)者生產(chǎn)的總量==消費(fèi)者消費(fèi)的總量

注1：線性問(wèn)題的解集是一個(gè)凸集，線性目標(biāo)與凸集相較于兩點(diǎn)，分別是最優(yōu)、最差傳輸方案存在。因此證明了解的存在性，此外解可能唯一或不唯一。

注2：最優(yōu)傳輸?shù)幕A(chǔ)解決方法就是采用線性規(guī)劃的方法解決。

## 線性規(guī)劃和對(duì)偶問(wèn)題

注1：影子價(jià)格。存在另一個(gè)工廠，租借本工廠的資源。每個(gè)小時(shí)的租賃報(bào)價(jià)。后來(lái)被稱(chēng)為勢(shì)能函數(shù)。

注2：假設(shè)出租。則租金收益要高于營(yíng)業(yè)收益。產(chǎn)生了對(duì)偶問(wèn)題。

注3：本身是非常典型的線性規(guī)劃問(wèn)題，因此有

兩個(gè)問(wèn)題互為對(duì)偶，探索其解法。

注1：$y_i^*$表示i資源的稀缺性。if $y_i^*>0$表示資源稀缺，則說(shuō)明本工廠對(duì)資源i使用耗盡了（n個(gè)產(chǎn)品對(duì)i資源的消耗用盡了），即$\sum_{j=1} a_{ij}x_j^*=b_i$.反之，本工廠對(duì)資源$i$的消耗有剩余，則i資源不稀缺，因?yàn)?y_i^*=0$.

注2：當(dāng)本工廠考慮是否生產(chǎn)$j$產(chǎn)品的時(shí)候，如果用資源的影子價(jià)格其產(chǎn)品j的收益等于我的自身的收益，則我應(yīng)該生產(chǎn)產(chǎn)品j,即$x_j^*>0$.反之，如果用影子價(jià)格生產(chǎn)產(chǎn)品獲得收益大于我生產(chǎn)產(chǎn)品的收益$c_j$,則我不應(yīng)該生產(chǎn)該產(chǎn)品$j$,即$x_j^*=0$.(此時(shí)，出租比自我生產(chǎn)收益高)。

注3：離散理論，容易理解。但是丟失了很多信息。

## Lagrange乘子法

可以將原問(wèn)題和對(duì)偶問(wèn)題統(tǒng)一起來(lái)。

注1：約束中，將原來(lái)的線性不等式添加一個(gè)正數(shù)$s_i^2$變?yōu)榈仁健?/p>

注2：當(dāng)變?yōu)榈仁胶?，可以使用Lagrange乘子法，首先獲得輔助函數(shù)。其次求輔助函數(shù)的最大值。再次，令輔助函數(shù)梯度為0，獲得最優(yōu)解和松弛變量。

$\lambda_i$即影子價(jià)格，那它代表了什么呢？在經(jīng)濟(jì)學(xué)中的解釋如下。

注1： $p_1 x_1 + p_2 x_2=$表示：第一個(gè)價(jià)格乘以消費(fèi)量+第二個(gè)價(jià)格乘以消費(fèi)量=預(yù)算m

注2：采用Lagrange方法構(gòu)造輔助函數(shù)，得到影子價(jià)格$\lambda^*$的關(guān)系。

## k-p及其對(duì)偶問(wèn)題的舉例

注1：原問(wèn)題中有2個(gè)生產(chǎn)者和3個(gè)消費(fèi)者。$c_ij$表示傳輸代價(jià)，與深度學(xué)習(xí)中的損失函數(shù)是不同的。

注2：大多數(shù)深度學(xué)習(xí)使用對(duì)偶問(wèn)題解決的原因在于，原問(wèn)題有$m\times n$個(gè)未知變量，而對(duì)偶問(wèn)題有$m+n$個(gè)未知變量。維數(shù)問(wèn)題。

注1：第$i$個(gè)生產(chǎn)者的影子價(jià)格為$\varphi_i$,第$j$個(gè)消費(fèi)者的影子價(jià)格為$\phi_j$.

## 連續(xù)的自由傳輸問(wèn)題

注1：連續(xù)問(wèn)題變?yōu)殡x散的方式：離散采樣，使用Dirac和代替原來(lái)的測(cè)度。

注2：當(dāng)采樣精度足夠高的時(shí)候，離散測(cè)度會(huì)弱收斂到連續(xù)測(cè)度。

注3：最優(yōu)傳輸穩(wěn)定性定理，當(dāng)弱收斂時(shí)，影子價(jià)格會(huì)收斂到勢(shì)能函數(shù)。

## 數(shù)學(xué)原理的通用型與弊端

## Monge (蒙日)問(wèn)題

注1：度量空間是完備的(求極限的時(shí)候是封閉的)。降低難度，假設(shè)是緊集( 它們的任何開(kāi)覆蓋都有有限子覆蓋).

注2：使用勒貝格積分

注1:從x點(diǎn)(X空間)到y(tǒng)點(diǎn)(Y空間) 的傳輸代價(jià)為c. c是一個(gè)映射。映射c是具有保測(cè)度的，即$T_{\#\mu}=v$.

注2：在所有的保測(cè)度映射中，使得傳輸代價(jià)最小者，稱(chēng)為最優(yōu)傳輸映射。

注1：映射T: $(X,\mu) \to (Y,v)$。在Y(目標(biāo)區(qū)域)中隨便選擇一個(gè)可測(cè)集A(可假設(shè)為波萊爾集，即 在一個(gè) 拓?fù)淇臻g 中，從所有的 開(kāi)集 出發(fā)，通過(guò)取 補(bǔ)集 ，可數(shù)并，可數(shù)交等運(yùn)算，構(gòu)造出來(lái)的所有集合)，A的原象為$T^{-1}(A)$,采用勒貝格測(cè)度。

注2：保測(cè)度，即為，原象的在測(cè)度$\mu$下的值等于A在測(cè)度$v$下的值。其物理意義是，(在液體流動(dòng)的時(shí)候)保質(zhì)量。(因?yàn)橘|(zhì)量不會(huì)憑空產(chǎn)生也不會(huì)憑空消失)。

注3：公式中的錯(cuò)誤，應(yīng)為$v(T^{-1}(A))$

注4：該問(wèn)題無(wú)法解決，Kantorvich將其放松后才解決。

## Kantarovich問(wèn)題

注1： 映射-->傳輸方案，該方案用一個(gè)聯(lián)合分布表示。其物理意義是，在X中生產(chǎn)的一部分存到Y(jié)后并繼承$\gamma$。

注2：邊際概率：$\gamma$向X空間投影為$\mu$（對(duì)生產(chǎn)者固定，生產(chǎn)者發(fā)出的總質(zhì)量=生產(chǎn)總質(zhì)量）,$\gamma$向Y空間投影為$v$（對(duì)消費(fèi)者固定，收到的所有產(chǎn)量=消費(fèi)的總質(zhì)量）。

注1： 該問(wèn)題為，在所有的可能的傳輸方案$\gamma \in \Pi(\mu,v)$中，產(chǎn)生總代價(jià)的最小者。

注2：在Monge問(wèn)題中有$(X,\mu),(Y,v)$,而在Kantarovich問(wèn)題中有聯(lián)合概率$\Pi(\mu,v)$.其邊際概率分別為$\mu, v$.

注3：K-P松弛的點(diǎn)在于：從一點(diǎn)(生產(chǎn)者)出發(fā)的質(zhì)量可以分成很多份，而M-P中從一點(diǎn)(生產(chǎn)者)出發(fā)的質(zhì)量只能傳達(dá)到另外一點(diǎn)。這就是從多對(duì)一(或一對(duì)一）松弛為一對(duì)多。

## M-P和K-P的比較

注1：右側(cè)(K-P): 對(duì)應(yīng)于同一個(gè)x($\in X$),其y值(非0解)可以是一條線。者說(shuō)明是一對(duì)多。

注2：左側(cè)(M-P):從x出發(fā)只能映射為一個(gè)y.但同一個(gè)y，可能具有多個(gè)x.

注3：Supp表示支集，M-P為一條線，K-P為一個(gè)面。所以，M-P的解在K-P的支集中是一個(gè)零測(cè)度。

注4：如果最優(yōu)傳輸映射存在，則不要采用線性規(guī)劃問(wèn)題(K-P方法)去解。因?yàn)榻饪臻g(K-P)絕大多數(shù)為0，只在某條曲線上非0.所以，計(jì)算的時(shí)候會(huì)浪費(fèi)存儲(chǔ)空間。

注1：最優(yōu)傳輸映射為最優(yōu)傳輸方案的特例。

注2：一個(gè)傳輸映射不能分解生產(chǎn)質(zhì)量；如果只有一個(gè)生產(chǎn)者多個(gè)消費(fèi)者時(shí)，只存在最優(yōu)傳輸方案而不存在最優(yōu)傳輸映射。

注1：數(shù)學(xué)上，保測(cè)度映射的空間是非緊的。比如定義一個(gè)柯西數(shù)列，其極限不在空間內(nèi)。則其解(M-P)會(huì)非常困難。

注2：K-P的解是緊集的。

## 下半連續(xù)函數(shù)

自由傳輸理論應(yīng)用非常廣泛，將連續(xù)函數(shù)拓展到下半連續(xù)函數(shù)。

分片連續(xù)的，在間斷點(diǎn)處達(dá)到下極限（上極限忽略）。

## Weierstrass定理

注1：微積分定理---如果歐式空間中有一個(gè)緊集(任何開(kāi)覆蓋都有有限子覆蓋),有個(gè)連續(xù)函數(shù)，那么連續(xù)函數(shù)在緊集達(dá)到下界。

注2：推廣到復(fù)泛函空間上，X是個(gè)抽象空間(例如是個(gè)函數(shù)空間)，定義距離、范數(shù)，從而定義X是個(gè)緊集。如果在X上存在一個(gè)下半連續(xù)的函數(shù)f，則f具有下界。

## 緊空間上連續(xù)代價(jià)函數(shù)的Kantorovich問(wèn)題

## Daul問(wèn)題

## 對(duì)偶問(wèn)題

注1：目標(biāo)泛函是線性的(對(duì)于$\gamma$來(lái)說(shuō))

注2：約束條件當(dāng)下有3個(gè)，實(shí)際上可為無(wú)窮維的

注3：廣義的Lagrange乘子，可以解決無(wú)窮多個(gè)約束問(wèn)題(不是有限個(gè))

注1:新型的Lagrange乘子 ，或?yàn)橛白觾r(jià)格

注2：$\varphi \in \mathcal{C}_b(X)$是測(cè)度空間X的對(duì)偶空間(即測(cè)度空間上的線性泛函)，$\phi \in C_b(X)$同理。

注3：$\gamma \in \Pi(\mu,v)$(即是可容許的), $\forall \varphi,\phi$,積分(Lagrange乘子函數(shù))恒等于0，所以其極大值為0(sup表示上確界).

注4:Lagrange輔助函數(shù)(第二個(gè)公式)，要令其最小化，因此會(huì)強(qiáng)迫紅色公式部分為0，也就是說(shuō)會(huì)令$\gamma \in \Pi(\mu,v)$.

注1：交換，使與$\gamma$相關(guān)的項(xiàng)放在公式后面。一種公式解釋是：前面是泛函，后面是公式懲罰項(xiàng)

## 對(duì)偶問(wèn)題

利用先驗(yàn)工具

## 連續(xù)函數(shù)空間的緊致性

注1：c-變換，是最優(yōu)傳輸理論中最本質(zhì)的一個(gè)概念。

注2：想極大化$\varphi$的期望值和$\phi$的期望值。勢(shì)能函數(shù)滿足小于c的條件。首先固定$\phi$，使$\varphi$在約束下逐漸增大,這樣先增大$\int_X \varphi d\varphi$的期望和；再固定$\varphi$，使得在約束下$\phi$增大；從而可以構(gòu)造期望和的單調(diào)遞增系列

注3：$c(x,y)-\chi(x)$當(dāng)取遍所有的x，其極小(下確界)定義為$\chi^c (y)$.結(jié)果是保證$\chi(x)+\chi^c (y) \leq c(x,y)$,在任意點(diǎn)。

注1：在變換x的時(shí)候，即有$\chi^c (y)$的過(guò)程中，想當(dāng)于后圖中的紅色曲線。代價(jià)c函數(shù)決定了支撐。支撐包絡(luò)得到了勢(shì)能$\chi^c (y)$.舉例：采用Legendre變換來(lái)理解c變換

注2：在Legendre變換中，x映射為梯度，就是自由傳輸映射。

注1：$ \exists u(x)$,定義在$R^d$上。圖中(左圖)所有的直線的方程為$<p,x>-q$,其中p是斜率，q是截距。$<p,x>-q \to 點(diǎn)(p,q)$,則該點(diǎn)就為這條線的對(duì)偶點(diǎn)。

注2：$u^*(x)$是$u(x)$的Legendre的變換。$u(x)$是凸函數(shù)，其對(duì)偶函數(shù)$u^*(x)$也是凸函數(shù)。

注3：藍(lán)色的線(支撐直線)的對(duì)偶點(diǎn)(藍(lán)點(diǎn))位于$U^*(x)$的內(nèi)部。

注:4：如果$u(x)$的切線(紅色直線)，則其對(duì)偶點(diǎn)(紅點(diǎn))在$u^*(x)$上。

注5：上境圖。一條曲線分為上下兩部分。上部分就稱(chēng)為 上境圖對(duì)偶。

注6：$u^(x)$的對(duì)偶函數(shù)為$u(x)$，對(duì)偶的對(duì)偶為原函數(shù)。

注1：$u(x)$是非凸的。

注2：所有支撐直線(切線)的上半部分的交函數(shù)為凸函數(shù)。即u的對(duì)偶的對(duì)偶。

注3：函數(shù)的凸化：函數(shù)對(duì)偶兩次

最優(yōu)化理論的推廣：將直線換成曲線。

注1：一族紅色曲線，其包絡(luò)定義了一個(gè)勢(shì)能函數(shù)，稱(chēng)為 包絡(luò)勢(shì)能。

## 連續(xù)模

作先驗(yàn)工具的第一個(gè)武器為：連續(xù)模。

## Kantorovich和對(duì)偶Dual問(wèn)題的等價(jià)性

注1: 在最優(yōu)解(配對(duì))上，隨意破壞配對(duì)，其 傳輸代價(jià)肯定是增加的。

注1：一般下$\varphi(x)+\varphi^c(x) \leq c(x,y)$,當(dāng)最優(yōu)的情況下的時(shí)候，取到等號(hào)。等號(hào)下所定義的y稱(chēng)為x的c-次微分。這是梯度的推廣。

注2：c-次微分中的x和y對(duì)，會(huì)出現(xiàn)在最優(yōu)傳輸方案中。最優(yōu)傳輸方案是一個(gè)概率分布。其支集是由點(diǎn)對(duì)(x,y)組成。

注3：若點(diǎn)對(duì)(x,y)滿足c-次微分的條件等式，則(x,y)應(yīng)出現(xiàn)在最優(yōu)傳輸方案的支集中。

注4：固定一個(gè)生產(chǎn)者$x$,x生產(chǎn)的東西運(yùn)送到消費(fèi)者y,所有消費(fèi)者構(gòu)成的集合則稱(chēng)為x的c-次微分。如果函數(shù)光滑，則x的c-次微分只有一個(gè)（即單點(diǎn)集）。

注1：在c-次微分上定義c-次微分圖。滿足條件的點(diǎn)對(duì)(x,y)構(gòu)成c-次微分圖。

注1：$n$個(gè)生產(chǎn)者和與之配對(duì)的n個(gè)消費(fèi)者,排列后，查看是否單調(diào)的。？？？

注2：假設(shè)給了兩個(gè)概率分布，其支集的邊界非常的不規(guī)則。循環(huán)單調(diào)性可退出一個(gè)新的條件，即 ”傾斜性條件？？？“。

注3：“傾斜性條件”，對(duì)應(yīng)點(diǎn)處的法向量，其夾角一定是銳角(絕不可能是鈍角)。

注4：反之：如果兩個(gè)集合的邊界非常的不規(guī)則，兩個(gè)邊界之間無(wú)法找到一個(gè)同胚，(同胚）where滿足對(duì)應(yīng)的點(diǎn)之間的夾角都是銳角。這說(shuō)明 最優(yōu)傳輸映射一定是非連續(xù)的，即存在間斷點(diǎn)。此時(shí)，也就是表明，深度學(xué)習(xí)是無(wú)法學(xué)會(huì)的(深度學(xué)習(xí)只能學(xué)會(huì)連續(xù)變換)。

==Rockafellar定理==

注1：如果存在一個(gè)集合滿足c-單調(diào)循環(huán)，可以找到一個(gè)勢(shì)能$\varphi$包含在$\Gamma$中。

注1：證明了最優(yōu)傳輸問(wèn)題的對(duì)偶問(wèn)題和Kantorovich問(wèn)題是等價(jià)的。

這是最優(yōu)傳輸在運(yùn)籌學(xué)上的設(shè)定，最終得到一個(gè)線性規(guī)劃問(wèn)題。線性規(guī)劃問(wèn)題的傳統(tǒng)解決方法有：

注1：給定一個(gè)隨機(jī)變量，如果一個(gè)事件(event)發(fā)生具有不同的概率。

注2:信息熵的概念沒(méi)有最優(yōu)傳輸?shù)母拍罴?xì)膩？？？

注3：信息學(xué)的眾多經(jīng)典定理可以用最優(yōu)傳輸?shù)脑碇匦峦茖?dǎo)。