鞅最优运输问题的计算方法

2014年10月16日文件：数字MOT\\U修订版。tex日期：201914年4月8日MOT问题的计算方法严格正权重p*i、 jare集中在满足上述ξ±条件的两条曲线周围。为了进行比较，我们现在采用第3.2节中开发的随机离散化。Wesample，使用接受-拒绝算法，两个i.i.d.随机变量序列（Xi）1≤我≤nand（Yj）1≤j≤nfromu和ν。设X和Y是两个集合，分别包含xind Yj取的所有值，我们用X重新标记X和Y：=十、 X，···，X#X安迪：=Y、 Y，···，Y#Y, 其中#X，#Y≤ n表示X和Y的基数。进一步定义un（dx）：=P#Xi=1^αniδXi（dx）和νn（dy）：=P#Yj=1^βniδYj（dy），其中^αni：=#xin对于i=1#X和^βnj：=#yjn对于j=1#Y、 Xi：=Xk公司∈ X:Xk=Xi和Yj：=Xk公司∈ Y：Xk=Yj. LP问题Pεm（μun，μνn）由max（pi，j）给出∈R#X#Y+#XXi=1#YXj=1pi，jh（Xi- Yj）s.t.#YXj=1pi，j=αni，对于i=1#十、 #XXi=1pi，j=βnj，对于j=1#Y、 #XXi=1#YXj=1pi，jYj- α-尼克西≤ εm。注意，ν允许一个有限θth-力矩θ>1。θ=3时，χ（n）=2C（3，1）n-其中C（3，1）在命题3.6中定义。我们设置^nm：=bmrc，以便PM≥1χ（^nm）/εm<∞ 当r>4时，因此limm→∞Pεm（^u^nm，^ν^nm）=P（u，ν）最稳定。取r=4.1，计算Pεm（^u^nm，^ν^nm），结果如图2所示。左窗格中的蓝线显示Pεm（^u^nm，^ν^nm）在m中的收敛，而红色图2。计算，例如3.7。第一个窗格显示10的值Pεm（^u^nm，^ν^nm）（虚线）≤m级≤ 第二个窗格绘制m=100时优化器的热图。线条再现了图1第一个窗格中Pεm（|u（m），|ν（m））的收敛性。而随机离散化对于小m显示出一些不稳定性，对于m≥ 50我们发现这两条线非常接近。

我们注意到，对于相同的εm，Pεm（|u（m），|ν（m））的变量数为。2014年10月16日文件：数字MOT\\U修订版。tex日期：2019年4月8日MOT问题的计算方法15与Mw成正比，而其顺序为m2r m对于Pεm（^u^nm，^ν^nm）。在右侧窗格中，绘制了m=100的优化器的热图，并与图1的热图非常匹配。示例3.8。受模型独立定价的激励，我们考虑了一个有三个交易日期的股票，即N=3和d=1。我们采用Black-Scholes模型，即uk（dx）=ρk（x）dx，ρk（x）：=1（0，∞)（x） 经验值- （对数（x）+2k-4)k-2.x个√k-2π，对于k=1，2，3，考虑回溯和亚式选项，即c（x，y，z）：=max（x，y，z）- z和c（x，y，z）：=（x+y+z）/3-λz+带λ≥ 注意，所有ρkare L-L=12的R上的Lipschitz，且具有有限θ-Zr | x |θρk（x）dx时所有θ>1的力矩≤ZR | x |θρ（x）dx=eθ（θ-1） =：Mθ。由于所有ukhave无界支持，我们采用第3.1节中的完整近似程序。设￠u（n）k，上支持mbe识别号：0≤ i<mn, 定义为u（n）k，m识别号（i/n）:=(1 -Pmn公司-1j=1ρk（xk，j）/n如果i=0，ρk（xk，i）/n如果1≤ i<mn，其中xk，i：=argminx∈[i/n，（i+1）/n]ρk（x），对于i=1，明尼苏达州- 1、命题3.4意味着W⊕（▄u（n）1，m，▄u（n）2，m，▄u（n）3，m），（u，u，u）≤ 3.1/n+Mθ/Mθ-1+inf1≤j≤mn2jL/n+4Mθ/jθ-1个.取j=m=mn：=bn（θ- 1） Mθ/升1/（θ+1）c，设定unk：=°u（n）k，mn，一个hasW⊕（un，un，un），（u，u，u）≤ 3.1/n+Mθ/Mθ-1n+2mnL/n+4Mθ/mθ-1n:= εn，其中limn→∞εn=0。图3给出了与上述离散化相对应的回望和亚式期权（λ=2）LP问题的数值解。在图4中，我们展示了n=100时分别在（S，S）和（S，S）上投影的优化器的热图。上面的两个窗格用于Lookback选项，其中S上的条件涉及两个值，而S上的条件涉及最多四个值。

以下两个窗格用于亚洲选项。似乎（S，S）集中在水侧多边形的边界上，而（S，S）集中在两个不相交的四边形的边界上。示例3.9。最近，研究了一般维度上MOT问题的几何结构，参见[37，38，19]。我们在这里提供了二维数值证据，这使我们对[37]中的猜想2产生了怀疑。取N=d=2和c（x，y）：=-p（x- y） +（x- y） 对于所有x=（x，x），y=（y，y）∈ R、 给定（u，ν）∈ P, 假设如下：如果u在R上允许密度，那么P的支持度*对于u-a.e.x，x最多包含三个点∈ R、 其中P*∈ M（u，ν）是P（u，ν）和（P）的优化器*x） x个∈Ris为常规条件。2014年10月16日文件：数字MOT\\U修订版。tex日期：201916年4月8日MOT问题的计算方法图3。计算，例如3.8。这两个窗格显示10的值Pεn（un，un，un）≤ n≤ 左窗格代表回溯选项，右窗格代表亚洲选项。P的分解*关于u。设u（dx）=ρ（x）dx和ν（dy）=σ（y）dy由ρ（x）：=1确定[-1,1]（x）/4和σ（y）：=2-y[1,2]×[-1,1]（y）+2+y[-2.-1]×[-1,1]（y）+2-y型[-1,1]×[1,2]（y）+2+y[-1,1]×[-2.-1] （y）。注意，u，ν具有有界支撑，可以显式计算第3.1节的确定性离散化u（n）和ν（n）。我们得到，u（n）（识别号，j/n）= 1/4Nsi，j=-nn-1，对于i，j=-2n，2n个-1，ν（n）（识别号，j/n）=（4n+2i+1）/8nif- 2n个≤ 我≤ -n- 1.- n≤ j≤ n- 1，（4n+2j+1）/8nif- n≤ 我≤ n- 1.- 2n个≤ j≤ -n- 1，（4n-2j- 1） /8nif- n≤ 我≤ n- 1，n≤ j≤ 2n个- 1，（4n-2i- 1） /8nif n≤ 我≤ 2n个- 1.- n≤ j≤ n- 否则为1,0。εn：=4/n≥ W⊕（u（n），ν（n）），（u，ν）, 我们得到了LP问题Pεn（u（n），ν（n））。为了进行比较，我们还考虑了基于随机离散化的近似。

在例3.7中，我们表示相应的经验测度和lp问题的Pεm（μn，μνn）。因为ν有一个有界支撑，其中C（3，2）在命题3.6中定义，单相W⊕（un，νn），（u，ν）≤ 2C（3，2）（1+对数n）n-1/2=：χ（n）。设置^nm：=bmrc，r=4.1，一个hasPm≥1χ（^nm）/εm<∞ 和limm→∞Pεm（u，νnm）=P（u，ν）。通过求解Pεn（u（n），ν（n））和Pεm（^^nm，^νnm），将这些值绘制在图5中，其中说明了收敛性。注意，Pεm（uunm，νnm）的复杂度为m2r阶，与实施例3.7中相同，然而Pεn（u（n），ν（n））的复杂度为nw阶，其为一维情况下的平方。在图6中，我们绘制了在S（1）、S（2）、S（1）, 我们回忆起S=S（1），S（2）和S=S（1），S（2）. Asu和ν由映射R3（x，y）7保持不变→ （y，x）∈ R、 imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：2019年4月8日MOT问题的计算方法17图4。计算，例如3.8。这四个窗格显示了n=100时优化器在（S，S）和（S，S）上投影的热图。前两个对应于回溯选项，下两个对应于亚式选项。S（1）、S（2）、S（1）和S（2）、S（1）、S（2）在优化器下在法律上无法区分。红色突出显示的区域对应于转换为三个以上点的值。这些显然具有正质量，与[37]中的猜想2i不一致。示例3.10。为了证明我们方法的普遍性，我们在最后一个例子中考虑了R中的一个MOT问题，即N=2，d=3。设c（x，y）：=Pi=1λi | xi- 彝族|- K+对于所有x=（x，x，x），y=（y，y，y）∈ R、 其中K>0，λi≥ 0和pi=1λi=1。这里，Cre给出了一个篮子期权的支付，该篮子期权写在三个具有K点的远期启动期权上。我们构造了（u，ν）∈ P按以下方式。

设ρ：R→ [0, ∞) 成为L-具有有限θ的Lipschitz密度函数-一些θ>1的力矩，表示u（dx）=ρ（x）dx。我们将下一个ν定义为u与标准正态分布的卷积，即ν（dy）=σ（y）dy，其中σ（y）：=ZRρ（y- x） （2π）3/2exp-x+x+x！dx。那么σ是L-Lipschitz和νincludes finiteθ-片刻我们现在处于与示例3.8相同的条件下。取λ=1/2，λ=1/3，λ=1/6，K=1，ρ（x）：=1[-1,1]（x）| x |+| xx | C（1+x+2x+3x），其中C：=Z[-1,1]| x |+| xx | 1+x+2x+3xdx，imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：201918年4月8日MOT问题的计算方法图5。计算，例如3.9。左窗格显示10的Pεn（u（n），ν（n））值≤ n≤ 200，右窗格显示10的值Pεm（^u^nm，^ν^nm）（虚线）≤ m级≤ 200图6。计算，例如3.9。左侧窗格显示优化器的热图S（1）、S（2）、S（1）对于n=100，右窗格显示预测的优化器的热图S（1）、S（2）、S（1）对于m=100。其中一个具有L=7/C和进一步的Zr | y |σ（y）dy≤C+√2π:= Mandχ（n）：=2C（2，3）n-其中C（2，3）在命题3.6中给出。我们执行与示例3.8相同的离散化程序，确定性的离散化程序和随机的离散化程序与示例3.7和3.9相同，并解决相应的LP问题。结果值函数如图7.4所示。校样。第4节致力于定理2.2和2.5的证明。与通常的MOT类似，松弛问题Pε（u）允许byDε（u）给出的对偶公式：=inf（H，ψ）∈Dε“NXk=1Zψkduk#），（17），其中H是F的集合-适应过程H=（Hk）1≤k≤N-1以Rd计算价值，即Hk∈L∞(OhmkRd）对于k=1，N- 1和Dε H×λndentes成对的集合H=imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：2019年4月8日MOT问题的计算方法19图7。计算，例如3.10。

左窗格显示10的值Pεn（un，νn）≤ n≤ 220，右窗格显示10的值Pεm（^u^nm，^ν^nm）（虚线）≤ m级≤ 220.（香港）1≤k≤N-1，ψ=（ψk）1≤k≤N对于（x，…，xN）∈ OhmNN型-1Xk=1Xk（x，…，xk）·（xk+1- xk）-εN-1Xk=1HKK∞+NXk=1ψk（xk）≥ c（x，…，xN）。（18） 回想一下，Mε（u） P（u）是凸面且紧凑的。最小-最大理论的应用允许在下面的定理4.1中建立（7）和（17）之间的Kantorovich对偶。该公式在很大程度上重复了[4]中的推理，其中结果显示为ε=0，但它仍包含在附录A中。定理4.1。Letu∈ Pε. 如果c是线性增长的上半连续的，则存在一个优化因子P*对于Pε（u），即P*∈ Mε（u）和Pε（u）=EP*[c] 。此外，存在节点间隙，即Pε（u）=Dε（u）。对于ε=0，（18）的左侧表示通过在基础资产中动态交易和在一系列普通期权中静态交易来实现支付的超级复制。更准确地说，Hk（S，…，Sk）表示交易员在k时持有的股份数量。Vanilla期权允许持有人在k时收到等于ψk（Sk）的现金流，k=1，N、 其市场价格为ψk相对于uk的积分，其中u，un呈现S、…、的市场隐含分布，序号：。当d=1时，正如Breedenand Litzenberger[10]所观察到的那样，ukare是根据观察到的所有可能罢工的认购/卖出期权价格唯一确定的。因此，（17）右侧括号中的表达式表示采用超边缘策略的成本（H，ψ），D（u）等于c.4.1中的最小超边缘价格。松弛MOT问题的收敛性。定理2.2表明，P（u）可以通过考虑一系列放松的MOT问题来近似，这为我们提出的解决MOT问题的方案提供了主要见解。

定理2.2的证明分为推论4.3、命题4.4和引理4.5的证明。提案4.2。Letu∈ Pε. 那么对于任何ν∈ PN，一个有ν∈ Pε+r，r=W⊕(u, ν). 如果我们另外假设c是Lipschitz，Lipschitz常数为Lip（c），那么pε（u）≤ Pε+r（ν）+Lip（c）r.imsart-aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：201920年4月8日MOT问题的计算方法Proof。设置rk：=W（uk，νk），对于k=1，N其中一个定义为r=PNk=1rk。取任意P∈ Mε（u）。从斯科罗霍德（Skorokhod）[41]的定理1可以看出，存在一个放大的概率空间（E，E，Q），它支持随机变量xk和k=1，…，在rdk中的zktakingvalue，N这样Qo（X，…，XN）-1=P，Z，ZNand（X，…，XN）相互独立，QoZ-1k是Rd上的标准正态分布，对于k=1，N、 对于k=1，N、 设Pk为实现ukandνk之间的Wasserstein距离的最优运输计划，即Pk∈ P（uk，νk）和rk=EPkS-S. 引理A.1中存在可测量函数fk：Ohm→ Rd使Qo （Xk，Yk）-1=pk，Yk：=fk（Xk，Zk），对于k=1，N、 尤其是Qo Y-1k=νk。此外，一个人拥有所有∈ Cb公司Ohmk研发部均衡器h（Y，…，Yk）·（Yk+1- Yk）= 均衡器h（Y，…，Yk）·（Yk+1- Xk+1）+ 均衡器h（Y，…，Yk）·（Xk+1- Xk）+均衡器h（Y，…，Yk）·（Xk）- Yk）≤ （rk+rk+1）khk∞+ EQhhf（X，Z），fk（Xk，Zk）·Xk+1- Xk公司i=（rk+rk+1）khk∞+ZOhmkEP公司h类f（S，x），fk（Sk，xk）· （Sk+1- Sk）Nk（dx，…，dxk）≤ （ε+r）khk∞,式中，Nk表示Z的联合分布，Zk。因此，EPh（S，…，Sk）·（Sk+1-Sk）≤ （ε+r）khk∞保持所有h∈ Cb公司Ohmk研发部, 其中P：=Qo （Y，…，YN）-根据单调类定理，这等价于phEP公司Sk+1Fk公司- Sk公司我≤ ε+r。因此，P∈ Mε+r（ν）和ν∈ Pε+r。要总结证明，请注意EPc（S，…）。

，序号）- Pε+r（ν）≤ EP公司c（S，…，SN）- EP公司c（S，…，SN）= 均衡器c（X，…，XN）-c（Y，…，YN）≤ 唇（c）NXk=1EQXk公司- Yk公司= Lip（c）r，产生Pε（u）≤ Pε+r（ν）+Lip（c）r，因为P∈ Mε（u）是任意的。因此，下面的推论立即出现。推论4.3。Let（un）n≥1和（εn）n≥1be定理2.2中的序列。THNP（u）≤ Pεn（un）+Lip（c）εn≤ P2εn（u）+2Lip（c）εn，对于所有n≥ 1.证明。取ε=0，ν=u，r=rn，则有P（u）≤ Prn（un）+Lip（c）rn≤Pεn（un）+Lip（c）εn，其中Prn（un）≤ Pεn（un）后接定义。第二个不等式具有相同的参数，但交换u和un.imsart-aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：2019年4月8日MOT问题21的计算方法为了完成定理2.2的证明，仍然需要显示P2εn（u）→ P（u）为n→ ∞.提案4.4。让c成为Lipschitz。（i） 对于每个固定ε≥ 0，地图Pε3 u 7→ Pε（u）∈ R在W下为上半连续⊕.（ii）对于每个固定u∈ P, 地图[0，∞) 3 ε 7→ Pε（u）∈ R是非递减的、连续的和凹的。在证明命题4.4之前，让我们注意到，它与推论4.3和引理4.5一起，立即证明了我们的主要结果：定理2.2的证明。（i） 我们有Mεn（un）6= 来自提案4.2。推论4.3产量-Lip（c）εn≤ Pεn（un）- P（u）≤P2εn（u）- P（u）+ 所有n的边缘（c）ε≥ 1，命题4.4给出了limn→∞Pεn（un）=P（u）。（ii）根据定理4.1，我们知道所有n的优化器pn的存在性≥ 1、作为Pn∈ Mεn（un）P（un），引理4.5得出，（Pn）n≥1很紧，每个极限点必须小于P（u）。取任意收敛子序列（Pnk）k≥1带极限P，然后是P∈ P（u）。重复命题4.4（i）的证明，可以推断P∈ 因此，M（u）和P是P（u）的最佳值。

如果P（u）有唯一的优化器，则（Pn）n的每个收敛子序列≥1具有相同的限值，表明（Pn）n≥1弱收敛为P(OhmN） 是波兰人。命题4.4的证明。（i） 我们建立了一个稍微强大的财产。取两个序列（εn）n≥1. [0, ∞) 和（un）n≥1. Pεn，限值为ε和u。让Pn∈ Mεn（un）满足lim supn→∞Pεn（un）=lim supn→∞EPn公司c（S，…，SN）. 在传递到子序列之前，我们可以假设lim supn→∞EPn【c】=limn→∞EPn[c]，并进一步通过引理4.5得出（Pn）n≥1在瓦瑟斯坦意义上收敛到某个极限P∈ P（u）。对于每k=1，N- 1和h∈ Cb公司(Ohmk一个有EPnh（S，…，Sk）·（Sk+1-Sk）≤ εnkhk∞适用于所有n≥ 1和此后的限制措施，这意味着P∈ Mε（u）。同样，c的Lipschitz连续性给出了Slim-supn→∞Pεn（un）=limn→∞EPn公司c（S，…，SN）= EP公司c（S，…，SN）≤ Pε（u）。（ii）我们首先证明凹度。给定ε，ε≥ 0和α∈ [0，1]，仍需显示（1-α） Pε（u）+αPε（u）≤ Pεα（u），其中εα：=（1- α)ε + αε. 这确实源于以下事实（1- α） P+αP∈ Mεα（u）表示所有P∈ Mε（u）和P∈ Mε（u）。特别是，映射限制为（0，∞) 是连续的。最后，根据上面（i）中的推理，un=u，εn→ 0，给出limn→∞Pεn（u）=P（u），这与明显的反向不等式相结合，在ε=0时产生正确的连续性。引理4.5。Let（un）n≥1. PNbe收敛到u的序列∈ PNW以下⊕, 和PN∈ 所有n的P（un）≥ 1、则存在子序列（Pnk）k≥1在P上的Wassersteinmetric中进行连接(OhmN） 其极限P为P（u）。证据使用compact ER：=（x，…，xN）∈ OhmN： | xk |≤ R、 对于k=1，N. OnehasPn[电子病历]≤NXk=1ZRd[R，∞)（| x |）unk（dx）≤Rsupn≥1（NXk=1ZRd | x |unk（dx））。imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：1922年4月8日MOT问题的计算方法Further，W下的收敛性⊕暗示Limn→∞ZRd | x |unk（dx）=ZRd | x |uk（dx），对于k=1。

，N，产生（Pn）N的紧密性≥1自limR起→∞supn公司≥1Pn【EcR】= 这意味着存在一个弱收敛的子序列，我们仍然将其表示为（Pn）n≥设P为其极限。请注意，投影贴图是连续的，然后unk=PnoS-1K也收敛于弱toPo S-1K=1，N，表示P∈ P（u）。最后，Pnto P在瓦瑟斯坦意义上的收敛源自一阶矩的收敛。4.2. 收敛速度分析：N=2，d=1。本节涉及一维一步模型的收敛速度估计。定理4.1中的对偶性起着重要作用，并被反复使用。据我们所知，OREM 2.5中的误差界是文献中此类误差界的第一个。固定一对（u，ν）∈ P. 在整个第4.2节中，我们强调对c的依赖性，并写入Pcε（u，ν）≡ Pε（u，ν），Dcε≡ Dε和Dcε（u，ν）≡Dε（u，ν）。显然，对于任何c:R→ R、 它认为Pc+cε（u，ν）≤ Pcε（u，ν）+Pcε（u，ν）。根据推论4.3，我们有Pcεn（un，νn）-Pc（u，ν）≤Pc2εn（u，ν）- Pc（u，ν）+ Lip（c）εn，其中εn≥ W⊕（un，νn），（u，ν）适用于所有n≥ 1、为了估算差异Pcεn（un，νn）-Pc（u，ν）, 我们需要了解Pcε（u，ν）的渐近行为-Pc（u，ν），ε变为0，如定理2.5的证明所示。定理2.5的证明。设置L：=最大值唇板（c），sup（x，y）∈Ryyc（x，y）< ∞ 并引入cL（x，y）：=c（x，y）- 年月日/2。然后，对于每个x∈ R、 地图y 7→ cL（x，y）是凹的。此外，让我们用一个关于y的a ffine函数截断cLby。即，定义everyR≥ 0cRL（x，y）：=cL（x，-R） +（y+R）ycL（x，-R） 如果y≤ -R、 cL（x，y）如果- R<y≤ R、 cL（x，R）+（y- R）YL（x，R）另有规定。接下来是一个简单的计算，y 7→ cRL（x，y）为凹面，边缘（cRL）≤LR：=L（R+1）。鉴于Beiglb¨ock等人的备注2.6。