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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Computational Methods for Martingale Optimal Transport problems》
---
作者：
Gaoyue Guo and Jan Obloj
---
最新提交年份：
2019
---
英文摘要：
  We establish numerical methods for solving the martingale optimal transport problem (MOT) - a version of the classical optimal transport with an additional martingale constraint on transport\'s dynamics. We prove that the MOT value can be approximated using linear programming (LP) problems which result from a discretisation of the marginal distributions combined with a suitable relaxation of the martingale constraint. Specialising to dimension one, we provide bounds on the convergence rate of the above scheme. We also show a stability result under only partial specification of the marginal distributions. Finally, we specialise to a particular discretisation scheme which preserves the convex ordering and does not require the martingale relaxation. We introduce an entropic regularisation for the corresponding LP problem and detail the corresponding iterative Bregman projection. We also rewrite its dual problem as a minimisation problem without constraint and solve it by computing the concave envelope of scattered data.
---
中文摘要：
我们建立了求解鞅最优运输问题（MOT）的数值方法，该问题是经典最优运输问题的一个版本，对运输动力学具有附加鞅约束。我们证明了MOT值可以用线性规划（LP）问题来近似，该问题是由边缘分布的离散化和鞅约束的适当放松所导致的。针对一维问题，我们给出了上述方案收敛速度的界。我们还证明了仅在部分边际分布规范下的稳定性结果。最后，我们专门研究了一种特殊的离散格式，它保持了凸序，不需要鞅松弛。我们为相应的LP问题引入了熵正则化，并详细介绍了相应的迭代Bregman投影。我们还将其对偶问题改写为一个无约束的最小化问题，并通过计算散乱数据的凹包络来解决它。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--
一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--

---
PDF下载：
-->

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：计算方法 运输问题 distribution Applications Differential

提交给鞅最优输运问题的应用概率计算方法年鉴*郭高跃和Jan Ob l'oj+牛津大学，联合王国我们开发了求解鞅最优运输（MOT）问题的计算方法，这是经典最优运输的一个版本，对运输动力学具有附加鞅约束。我们证明了一个一般的多步骤多维MOT问题可以通过一系列线性规划（linearprogramming，LP）问题来近似，这些问题是由边缘分布的离散化以及鞅条件的适当放松所导致的。我们进一步提供了两种离散概率分布的通用方法，分别适用于我们可以根据这些分布计算积分或从中采样的情况。这些使得我们的主要结果适用，并为解决vingmot问题提供了一个可实现的数值格式。最后，专门针对realline上的一步模型，我们提供了一个收敛速度估计值，据我们所知，这是文献中此类模型的首次。1、简介。最优运输（OT）问题涉及以优化给定标准的方式将质量从一个位置转移到另一个位置。从数学上重新表述，为了简单起见，考虑到一维情况，我们给出了R上的两个概率分布u和ν，并寻求最小化所有概率测度P（dx，dy），（1）中的zrc（x，y）P（dx，dy），（1），也被称为运输计划，例如E×R= u[E]和PR×E= ν[E]，对于所有E∈ B（R），（2），其中c:R→ R是一个可测量的成本函数。过去五年的理论进展描述了优化器在各种不同设置下的存在性、唯一性、表示性和平滑性，参见。

[39，43]，在包括生物医学、地理和数据科学在内的大多数应用科学中，应用非常广泛。因此，OT的数值技术非常重要，并已迅速发展成为应用数学的一个重要独立领域：1。在绝对连续的情况下，即u（dx）=ρ（x）dx和ν（dy）=σ（y）dy，Benamouand Brenier在[7]中提出了二次距离函数c（x，y）=（x）的数值格式- y） 使用流体力学中的等效公式。*这项研究由欧洲研究理事会根据欧盟第七框架计划（FP7/2007-2013）/ERC第335421号赠款协议支持。作者感谢纪尧姆·卡利尔、布鲁诺·列维、唐塞克·林、特里·莱昂斯和彼得罗·西尔帕斯的富有洞察力的讨论和评论。+第二作者还感谢牛津圣约翰学院的支持。MSC 2010学科分类：初级49M25，60H99；辅助90C08。关键词和短语：鞅最优运输，鞅松弛，鲁棒套期保值，对偶，测度离散化，线性规划imsart-aap-ver。2014年10月16日文件：数字MOT\\U修订版。tex日期：1992年4月8日MOT问题计算方法2。在纯粹离散的情况下，即u（dx）=Pmi=1αiδxi（dx）和ν（dy）=Pnj=1βjδyj（dy），OT问题简化为线性规划（LP）问题，可以使用迭代Bregman投影进行计算，见Benamou等人【8】。3、在半离散情况下，即u（dx）=ρ（x）dx和ν（dy）=Pnj=1βjδyj（dy），L'evy【34】采用计算几何方法计算成本c（x，y）=（x- y） 并通过拉盖尔的细分来解决OT问题。最近，又考虑了一个额外的约束，这导致了所谓的马尔丁格尔最优传输（MOT）问题。

这种优化问题是由所谓的数学金融中奇异期权的模型独立或稳健定价所推动和促成的，这一观点在金融危机后获得了显著的势头。更准确地说，两个给定的度量u和ν描述了股票价格的初始和最终分布，并且可以从交易买入/卖出期权的市场价格中恢复。因此，校准后的市场模型通过鞅与这些规定的边际进行识别，即运输计划P进一步满足u-a.e.x的RyPx（dy）=x∈ R、 （3）式中（Px）x∈RDE注意到P相对于u的分解。MOT问题旨在最大化积分（1）总体P，仍然命名为运输计划，满足约束条件（2）和（3），并且它对应于选项c的模型独立价格。Beiglb¨ock等人提出了该方法。我们参考该方法进行更详细的讨论。同样值得一提的是，在霍布森（Hobson）[29]的一系列论文中，通过随机控制或Skorokhod嵌入技术，对特定支付的一些具体MOT问题进行了研究，参见[9、14、23、12、15、16、30、31、27]。鉴于对MOT问题的积极理论兴趣及其在数学金融中应用的重要性，开发这些问题的数值技术和计算方法变得越来越重要。一个简单但重要的观察结果给出了一个自然的起点，即对于上述纯离散情况，MOT问题等效于以下LP问题：max（pi，j）1≤我≤m、 1个≤j≤n∈Rmn+mXi=1nXj=1pi，jc（xi，yj）s.t.nXj=1pi，j=αi，对于i=1，m、 mXi=1pi，j=βj，对于j=1，n、 nXj=1pi，jyj=αixi，对于i=1，m、 Davis等人率先提出了这种LP配方。

[18] ，其中仅给出了有限数量的期望约束，而不是边际约束ν。对于凸奖励函数，这将导致优化器具有有限的支持。一般来说，为了适应这种方法，我们可以希望将（u，ν）的MOT问题与上述有限支持（un，νn）的LP问题近似，这些LP问题“接近”（u，ν）。不幸的是，这个天真的想法遇到了两个重要障碍。最大化公式更适合金融应用。我们将c称为奖励函数或Payoff，这在金融行话中被普遍接受。imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：2019年4月8日MOT问题的计算方法3首先，MOT问题没有作为其输入（u，ν）函数的一般连续性结果。据我们所知，唯一的例外是Juillet[33]，他证明了ifc（x，y）=Д（x）ψ（y）或c（x，y）=h（x- y） ，式中ψ，ψ，h:R→ 假设R满足[33]中备注2.10的条件，则存在优化器P*（u，ν）在Wasserstein型拓扑下是关于（u，ν）的Lipschitz。我们将他的结果扩展到命题4.7中更一般的Payoff c，但它仍然是一维结果。其次，即使（u，ν）允许鞅运输计划，在维度d>1时，可能很难构造离散近似值（un，νn），这也是如此，请参见下面的备注3.3。实际上，鞅条件似乎是无害的，它使得任何通常的OT技术都不可用，例如稳定性结果、PDE工具和计算几何。据我们所知，与OT相比，迄今为止，MOT问题的数值方法在理论和应用方面几乎不存在。本文填补了这一重要空白。

我们提供了一种系统求解N的近似方法-Rd上的周期MOT问题，N≥ 2和d≥ 我们对原始问题的近似依赖于边缘分布的离散化，再加上鞅约束的适当松弛，从而导致一系列LP问题。该序列收敛，并且专门化为N=2和d=1，我们得到了收敛速度。我们的调查涉及到许多新颖的结果和技术，我们相信这些结果和技术是独立的。特别是，我们明确计算了[22]中的常数，以使经验测度的收敛速度达到Glivenko-Cantelli定理中的极限。本文的组织结构如下。在本简介的其余部分中，我们将澄清我们工作所依据的框架和符号。第2节包含了所有主要的理论结果：我们引入了松弛鞅最优运输（松弛MOT），证明了近似LP问题对MOT问题的收敛性，并给出了一维收敛状态的一个界。在第3节中，我们考虑我们的方法的可能实现。这需要通过离散度量值unand来近似概率度量值u，并且能够计算或限制unandu之间的Wasserstein距离。我们开发了两种通用的方法来实现这一点，然后给出了几个数值例子来说明我们的方法，并提供了对优化器结构的启发性见解，包括一个猜想[37]。第4节包含所有相关的证明。第5节总结了本文，并指出了未来可能的工作。1.1. 预备工作。对于给定的集合E，我们用Ekits k表示-折叠产品。如果E是抛光的，则B（E）表示其Borelσ-字段和P（E）是E、 B（E）允许有一个有限的第一刻。

在研究OT时，我们通常将我们的问题表述在正则空间上，这在分析中起着重要作用。允许Ohm := Rd及其元素由x=（x，…，xd）和P表示：=P(Ohm). 自始至终，我们赋予RDS“范数|·|，即| x |：=Pdi=1 | xi |”。定义∧为Rdand上Lipschitz函数的空间，给定f∈ ∧，用Lip（f）表示其在Rd上的Lipschitz常数。对于每个L>0，设∧L 带Lip（f）的函数f的∧bethe子空间≤ 五十、 我们考虑坐标过程（Sk）1≤k≤N、 即Sk（x，…，xN）：=所有（x，…，xN）的xk∈ OhmN、 及其自然过滤（Fk）1≤k≤N、 即Fk：=σ（S，…，Sk）。从财务角度来看，OhmNModel收集d股价格演变的所有可能的主要因素，其中N是交易日期数。给定概率度量向量u=（uk）1≤k≤N∈ 请注意，请定义transportimsart aap版本集。2014年10月16日文件：数字MOT\\U修订版。tex日期：1994年4月8日边际分布为u，…，的MOT问题的计算方法，uNbyP（u）：=nP∈ POhmN: PoS-1k=uk，对于k=1，否，其中Po S-1K表示P通过map Sk向前推：OhmN→ Ohm. 特别是u和ν之间的塞尔斯坦距离（1阶）∈ P由w（u，ν）给出：=infP∈P（u，ν）EPS- S= supf公司∈ΛZRdf（x）u（dx）-ZRdf（x）ν（dx）,（4） 其中第二个等式紧随着坎托洛维奇的二重性。我们记得，配备了度量值W的P是一个波兰空格。此外，对于任何（un）n≥1. P和u∈ P、 W（un，u）→ 0当且仅当unL时有效-→ u和ZrD | x |un（dx）-→ZRd | x |u（dx），其中L表示概率测度的弱收敛性，有关详细信息，请参阅拉契夫和R¨uschendorf的专著【39】。为了便于我们在续集中进行分析，我们将PNW与产品指标W⊕由W定义⊕（u，ν）：=PNk=1W（uk，νk），对于所有u，ν∈ 请注意。因此，PNis对W进行抛光⊕.

我们通过列出下面使用的一些符号来结束本文的介绍。标记。o0 := (0, . . . , 0), 1 := (1, . . . , 1) ∈ 为了强调一维情况，我们写下≡ x和Sk≡ 对于d=1，请参见第3.3节L(OhmkRd）是来自Ohmkto路用L表示∞(OhmkRd）L(OhmkRd）（一致）有界函数的子集，以及Cb(OhmkRd） L∞(OhmkRd）连续有界函数的子集。o为了简单起见，只要上下文清楚，我们就采用以下缩写：Zfdu≡ZRdf（x）u（dx），（pi，…，iN）≡ （pi，…，iN）i∈我在里面∈年，Xi，。。。，在里面≡xi∈我在里面∈在中。2、主要结果。我们的计算方法依赖于OREM 2.2中所述的收敛结果。为了引入结果，我们需要ε的概念-近似鞅测度。定义2.1。对于任何ε≥ 0，概率测度P∈ POhmN被称为ε-近似鞅测度，如果每个k=1，N- 1英里/小时EP公司Sk+1Fk公司- Sk公司我≤ ε、 （5）或等效地，根据单调类定理，EPh（S，…，Sk）·（Sk+1- Sk）≤ εkhk∞, 对于所有h∈ Cb公司(OhmkRd），（6）其中khk∞:= 最大值kh（1）k∞, . . . , kh（d）k∞和kh（i）k∞:= sup（x，…，xk）∈Ohmkh（i）（x，…，xk）对于i=1，d、 imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：2019年4月8日MOT问题的计算方法5Givenε≥ 0，设Mε（u） P（u）是包含所有ε的子集-近似鞅测度。那么Mε（u）是凸的，并且相对于弱拓扑闭合（6），并且是紧致的。对于可测量函数c：OhmN→ R、 松弛的MOT问题由pε（u）：=supP定义∈Mε（u）EPc（S，…，SN）,（7） 其中，我们根据约定Pε（u）：=-∞ 每当Mε（u）=. 用P进一步表示ε Pn测量值u的集合，使得Mε（u）6=. 我们注意到∈ M（u）是阿马丁格尔度量，即。

（Sk）1≤k≤Nis是P下的鞅，P（u）是MOT问题。在本文的其余部分，为了简单起见，我们在ε=0时删除下标ε，例如P≡ P,M（u）≡ M（u），P（u）≡ P（u）等。如前所述，一旦边缘uk单位支持k=1，…，P（u）将减少为LP问题，N、 现在，我们将这一观察结果与适当放松马丁格尔约束相结合，以获得计算P（u）的统一框架。定理2.2。固定u∈ P. Let（un）n≥1. PNbe在W下收敛到u的序列⊕.那么，对于所有n≥ 1，un∈ Prn带rn：=W⊕（un，u）。假设进一步的c是Lipschitz。（i） 对于任意序列（εn）n≥1接近于零，使得εn≥ RN适用于所有n≥ 1，一个haslimn→∞Pεn（un）=P（u）。（ii）对于每个n≥ 1，Pεn（un）允许优化器Pn∈ Mεn（un），即Pεn（un）=EPn【c】。序列（Pn）n≥1很紧，每个极限点都必须是P（u）的优化器。特别是，（Pn）n≥只要P（u）有唯一的优化器，1就会弱收敛。备注2.3。（i） 根据Strassen定理【42】，u∈ P当且仅当uk uk+1工作=1，N- 1，即Rfduk≤Rfduk+1适用于所有凸函数f∈ ∧和k=1，N- 1、此外，定义如下：ε PNis凸闭Dunder W⊕, 和M（u） Mε（u）表示所有ε≥ 0.（ii）如前所述，一个自然的想法是尝试用P（u）乘以P（un），并使用完全支持的度量值un，unn因为后者相当于LP问题。对于classicalOT，优化问题对u的连续依赖性可以从原始问题或其对偶公式中推导出来。然而，附加的鞅约束意味着通常的OT参数不再有效。u7的连续性→ P（u）通常是一个悬而未决的问题。对于d=1，部分结果如【33】所示，我们将其扩展到下面的位置4.7。

此外，必须考虑合适的近似值，见第4.2节，以确保M（un）非空。这将涉及到d>1。定理2.2表明，进一步放松鞅约束可以避免这两个问题，并建立所需的收敛结果。我们还注意到，距离Rn不接受闭式表达式，其数值估计可能代价高昂。由于Theorem2.2，我们可以在实践中使用任何上界εn≥ RN收敛到零。（iii）最后，我们指出Lipschitz假设可以稍微削弱。让E Rdbea闭合子集，以便supp（unk） E代表所有n≥ 1和k=1，N、 然后在定理2.2中假设c，限制为EN，是Lipschitz。imsart aap版本。2014年10月16日文件：数字MOT\\U修订版。tex日期：20196年4月8日MOT问题的计算方法现在表明Pεn（un）等价于LP问题。因此，由于语言的轻微滥用，我们总是将Pεn（un）称为P（u）的近似LP问题。推论2.4。设un=（unk）1≤k≤Nbe的选择应确保每个unk都有有限的支持，即unk（dx）=Xik∈Ikαkikδxkik（dx），其中Ik=1.n（k）标记支撑支撑unk. 用p表示=圆周率，。。。，在里面我∈我在里面∈在D：=πNk=1n（k）的RD+元素中，则Pεn（un）可以重写为LP问题。证据假设每个元素P∈ Mεn（un）可以通过一些p∈ RD+。因此，Pεn（un）变成了maxp下面的优化问题∈RD+Xi，。。。，iNpi，。。。，股份有限公司xixNiN公司s、 t.Xi，。。。，ik-1，ik+1，。。。，iNpi，。。。，iN=αkik，用于ik∈ Ikand k=1，N、 （8）Xi，。。。，ikXik+1，。。。，iNpi，。。。，在里面xk+1ik+1- xkik公司≤ εn，对于k=1，N- 1.（8）不是LP公式，但是，通过添加松弛变量δki，。。。，ik，j我∈我ik∈Ik，j∈J∈RDk+带J：=1.