平行美国蒙特卡罗

计算回归系数所需的信息包含在这些对象中，可以在路径和连续迭代中累积，而无需将所有路径保留在内存中。每次迭代开始时，只需进行线性系统反演。对于给定的迭代，练习决策取决于之前迭代中获得的对象UK和VKOB。在这个迭代中，不同路径上的计算是相互独立的。这意味着它们可以并行运行。一旦给定迭代中所有路径的数量累积起来，就可以为每个日期独立求解线性系统。因此，这条运河也应该平行化。此外，由于运动决策是使用之前迭代中的信息做出的，因此不需要使用反向计算：所有支付计算和运动决策都可以按照自然顺序进行。（请注意，在简单的情况下，在给定的路径上进行反向操作可能需要较少的计算。）有人可能会认为，在第一次迭代中，仅使用有限数量的路径来做出练习决策会增加最终价格的误差。然而，经过几次迭代后，这种影响似乎很小。为了减少最终结果中的误差，我们根据公式（4）和（5）中的迭代引入了权重：第一次迭代的路径的权重小于后续迭代的路径，后者更精确。事实上，我们算法的迭代性质甚至允许在机器学习中使用类似于所谓的提升的东西，正如Picazo（2002）在《美国期权定价》一书中介绍的那样。与经典的Longstaff-Schwartz算法相比，这最终会产生更小的误差。3.2符号N条路径被划分为N个不同的集合。

让我们假设分区的每一部分都由连续的路径组成，并用ni表示，1≤ 我≤ 在每套的最后一页。这意味着第i次迭代将使用来自ni的路径-1+1对ni.oM：锻炼日期的数量N：路径总数。on：迭代次数。oni：第i次迭代的最后一条路径。迭代i使用路径ni-1+1到ni，n=0，nn=n.oewi：价格总和中第i次迭代路径的权重。ow（i）kX（j）k: 矩阵U和向量V sumsin方程（4）中迭代i内路径j的权重。一种特殊情况是因式分解w（i）k（Xk）=wiyk（Xk）U（i）和V（i）k：包含路径1到nian信息的矩阵和向量，用于计算α（i）k.oU（i）和V（i）k：迭代i对U（i）和V（i）k的贡献，包含路径ni的信息-1+1 o镍α（i）k：在路径1到ni上回归的系数向量bC（i）k（Xk）：系数α（i）k给出的近似连续值。它用于迭代i+1κ（j）k：最佳运动时间指数κ，如果在tk之前没有运动，那么最佳运动时间是路径j上的tκP（j）k：如果之前未行使期权，则在tk时路径j上的贴现支付P（i）：第i次迭代路径的期权贴现支付之和“-PN：路径1到N的贴现期权支付的总加权和。oqN：路径1到N.3.3算法1的价格加权和。使用行使边界或系数α（0）k的粗略估计启动算法：例如，考虑期权仅在最终到期时行使，或者使用前一天计算的最终系数。2.从1到n对i进行迭代：（a）从ni对j进行迭代-1+1到ni:i.模拟路径j并获得状态变量X（j）kat所有日期。二、

对于所有日期tk，比较支付值FkX（j）k以及上一次迭代的continuationvalue估计值bc（i-1） kX（j）k= α（i）-1） >kfkX（j）k.由此可知，对于所有k，得到κ（j）k=minK≥ Kk=N或FkX（j）k≥bC（i）-1） kX（j）k最后P（j）k=e-Rκ（j）ktkrsdsFκ（j）kX（j）κ（j）kandeP（j）k+1=e-Rtk+1tkrsdsP（j）k+1。iii.累积对价格的贡献p（i）=niXj=ni-1+1P（j）。iv.对于每个日期，路径j tou（i）k=niXj=ni的贡献-1+1w（i）kX（j）kfkX（j）kf> kX（j）kv（i）k=niXj=ni-1+1w（i）kX（j）kfkX（j）keP（j）k+1。这种计算可以向前进行，但是在数值上，进行这种计算的最快方法是向后进行。从最后一个练习日期开始tMwe setP（j）M=FMX（j）M. 然后在k上递归，如果FkX（j）k≥bC（i）-1） kX（j）k, 设定P（j）k=FkX（j）k;否则设置P（j）k=eP（j）k+1=e-Rtk+1tkrsdsP（j）k+1。（b） 对于每个日期tk，在迭代i toU（i）k=iXl=1u（l）kV（i）k=iXl=1v（l）k中添加贡献u（i）和v（i）kof，求解线性系统u（i）kα（i）k=v（i），并得到第一条路径上的最小二乘回归系数：α（i）k=U（i）k-1V（i）k.（c）使用价格权重wi，将迭代i的贡献累积到yenPN=nXi=1ewiP（i）qN=nXi=1ewi（ni- 镍-1) .3. 最后得到期权价格的蒙特卡罗估计值，即加权平均p=`PNqN。3.4并行计算对于每次迭代，步骤（a）和（b）本质上可以并行化。在步骤（a）中，给定迭代中的所有路径相互独立，与不同路径相关的计算可以并行运行。

类似地，（b）中不同日期的线性系统可以并行求解。必须在计算单元之间共享或传输的数据包括所有日期的UK和VK、系数α和对最终价格的贡献P（i）。当权重w（i）k（Xk）因式分解为w（i）k（Xk）=wiyk（Xk）时，可以在这一步对wiyk的乘法进行因式分解：u（i）k=Pnij=ni-1+1ykX（j）kfkX（j）kf> kX（j）kU（i）k=U（i）-1） k+wiu（i）对于V.3.5收敛，我们假设权重为ewi~ 1当我→ ∞. 我们还假设w（i）k（Xk）因式分解为w（i）k（Xk）=wiyk（Xk）和wi~ 1当我→ ∞.让我们定义一个初始回归系数α的向量。在运动决策中使用这些系数，让我们定义u（α）=Ef（X）f（X）>v（α）=Ef（X）eP.这给出了一个函数α7→ \'\'α（α）=\'u（α）-1伏（α）。这对应于在有限条路径的限制下进行一次迭代后获得的系数矢量。让我们假设这个函数α7→ “‘α（α）’是合同方，即Lipschitzyα、 αk′α（α）- \'-α（α）k≤ qkα- αkwithq<1。然后，Banach不动点定理确保该函数有一个不动点。让我们用A表示（矩阵）算子的范数 α(α)α在这个固定点。我们有一个≤ q<1。假设m条路径有n次迭代，路径总数sn=nm。然后，我们提出的算法收敛到价格asn的近似值→ ∞.由于延拓值是在有限维的基础上预测的，因此练习边界是近似值，因此练习稍微次优。因此，算法收敛到一个低于真实价格的值。当基函数的数量增加时，价格估计值与实际价格接近。在Lonstaff-Schwartz算法中也观察到了同样的行为。该极限值周围的误差项具有O中的预期值n1-A.以及O中的标准错误√nmax（1,2-2A）.

如果≤, 这是通常的蒙特卡罗错误√纳米= O√N.当yk（Xk）中路径的权重与Longstaff和Schwartz选择的相同时，货币中的权重为1，货币中的权重为0，则该算法收敛到与Longstaff-Schwartz算法相同的价格。附录B.3.6路径权重给出了证明。为了提高算法的收敛性，一方面在矩阵U和向量V的计算中，另一方面在价格计算中，路径可以被赋予不同的权重。对于美式期权，当后续日期的估计延续值精确时，给定日期的延续值达到最大值。因此， αα为最优α。在这一点上，假设函数是Contractant并不是一个很强的约束。3.6.1练习边界Longsta off和Schwartz在回归中使用路径的简单权重：在日期tk，仅当选项在日期tk的货币中时，才会考虑路径j。当期权在货币中时，权重wk（X（j）k）等于1，否则等于0。这用于计算方程式（4）中的矩阵UK和向量VK。这个权重提高了算法的收敛性：Money中的路径是唯一可以执行的路径。更进一步，我们想把注意力集中在靠近运动边界的路径上。此外，我们要求权重是连续的，这将提供更平滑的结果。对于一个基础上的产品，我们建议使用一个简单的权重函数：yk（Xk）=e-（Xk）-Bk）2βkw其中Xkis为交易日的现货价格，Bk为同一交易日的行权边界值。在每个日期tk，行使边界是方程Fk（x）=bCk（x）的解，其中Fk是支付价值，bckis是持续价值估计。使用之前迭代的系数α计算边界。

这个方程可以用简单的数值方法近似求解。参数βkare的选择是为了在统计误差和系统误差之间提供良好的折衷。当考虑多条路径时，大βk的统计误差减小。对于较小的βk，当我们只查看到运动边界的路径时，系统误差会减小。我们可以使用我们算法的迭代性质来减少βk，因为迭代次数会增加。这将减少统计和系统误差。这类似于机器学习的提升：随着迭代次数的增加，我们会更加关注练习边界。3.6.2迭代次数和U、VAs上的权重算法是迭代的，回归系数的值在第一次迭代中不精确。因此，算法的一个简单优化就是对第一次迭代赋予较低的权重。在每次迭代中，矩阵U（i）和向量V（i）被填充并添加到U（i）中-1） kand V（i）-1） kof前面的迭代。我们引入一个随着迭代次数i增加的权重：wi=Qnj=i+1w（i）UVwithw（i）UV=1- λe-我知道。（6） 前一次迭代的每个U（i）和V（i）kF乘以w（i）UV。这降低了回归系数中第一次迭代的权重。3.6.3迭代和价格权重同样，在第一次迭代期间，估计的连续值不准确，因为系数αkare不准确，因此价格也不准确。提高收敛性的一个简单方法是从最终价格的计算中消除第一条路径。因此，最终价格是加权平均值，其中第一部分没有重要权重。我们引入了一个依赖于迭代的权重。权重随着迭代次数的增加而增加。我们使用以下函数：ewi=1-(1 - tanh[ν（i）- 1)]) .

（7） 在每次迭代i中，我们将迭代i的当前值之和乘以该权重，然后再将其与之前迭代的当前值之和相加。3.7时间作为回归函数的变量最终可以利用我们算法的迭代性质来减少回归中基函数的总数，并减少最小平方估计的统计误差。在最简单的算法中，对每个日期独立进行回归：对于每个日期tk，我们计算矩阵Uk和向量Vk，我们求解方程Ukαk=Vk，以获得系数αk的向量。通过在回归中包含时间，可以避免在每个日期进行回归。贴现现金流k+1根据状态变量向量xk和时间tk进行回归。这意味着基函数包括时间tkA变量。将fk，l（Xk）推广到fl（X，t）：C（j）k\'bCkX（j）k=pXl=1αlfl（X（j）k，tk）在这种一般情况下，我们最小化误差函数ψ（α）=MXk=1E“wk（Xk）Ck-pXl=1αlfl（Xk，tk）#.与第2.2节的解释类似，我们构建了一个p×p矩阵和一个维度p向量u=NXj=1MXk=1wkX（j）kFX（j）kf>X（j）kV=NXj=1MXk=1wkX（j）kFX（j）keP（j）k+1。（8） 然后我们求解线性方程Uα=V，得到最小二乘系数α=U-1V。当基函数的个数较大时，如果矩阵U是稠密的，则求解线性系统会非常耗时。然而，我们可以选择基函数，使U是块对角的。如果将基函数划分为具有不相交支撑的子集，则可获得此结果。更准确地说，假设我们有B块，用B标记。我们用PBB表示B块中基函数的数量，BXB=1pb=p。在B块中，我们用fb表示基函数，LW表示1≤ L≤ PB属于两个不同块的函数在（X，t）上有不相交的支撑。

因此，如果b6=bf对于所有的X和t，我们有fb，l（X，t）fb，l（X，t）=0。根据矩阵Uin方程（8）的定义，这意味着U是块对角的。我们用b块中基函数的向量FB表示，Ub是矩阵U的对角块，在Vb中向量V的拆分类似：Ub=NXj=1MXk=1wkX（j）kfbX（j）kf> bX（j）kVb=NXj=1MXk=1wkX（j）kfbX（j）keP（j）k+1。经典的逐日期回归是一种特殊情况，其中一个区块对应于给定的运动日期，且基函数为fb，l（X，t）=fb，l（X）t=tb。另一种需要较少基函数的可能性是，将整个锻炼日期集划分为B组连续日期，给定区块的基函数集中在相应日期上，其他日期的基函数为空。如果b区对应于练习日期tkwith kb-1<k≤ 基函数的形式为fb，l（X，t）=fb，l（X，t）tkb-1<t<tkb。例如，如果我们在X变量中有一组!-1（X，t）=fl（X）tkb-1<t<tkbfb，2l（X，t）=tfl（X）tkb-1<t<tkb正因为如此，不能在所有日期计算系数αkwon。对于一组训练时间[tkb]，我们只有一个矩阵ub和向量vb-1+1, . . . , tkb]。此外，这可以减少行权边界上的统计误差：对于给定数量的路径，U和V中有更多的贡献。4数值结果我们考虑了一个美国看跌期权的例子。假设股票价格遵循Black-Scholes动态，并且没有套利机会。股票价格的风险中性过程如下：dSt=rStdt+σStdWt。假设无风险利率r和波动率σ为常数。没有红利。

我们用K表示履约价格，用T表示期权的到期日。我们使用了与Longstaff和Schwartz（2001）相同的例子。我们以40美元的执行价为一股美国看跌期权定价。年利率为6%，标的股票价格为36美元，波动率σ为20%，到期日为1年。我们认为期权每年可行使50天，直至到期。我们生成了100000条路径。在并行算法中，我们使用100次迭代，与路径总数无关。我们选择5组10次约会。为回归选择的基函数是：1、S、S、t、tS和tS。我们在U和V上有权重，wuvλ=2和u=2。我们在价格上使用权重wi=0.99。我们也有重量，这取决于路径yk。我们将结果与有限差分法给出的参考值4.486美元进行比较。对于股票价格，我们使用了一个包含40000个时间步和1000个步骤的隐式方案。4.1算法的收敛性我们实现了并行算法，并将其与有限差分法进行了比较。我们已经测试了迭代次数和每个块的日期数的影响。这种差异是Black-Scholes方程离散化的结果：tP+σSSP+rS服务提供商- rP=0，终端条件P（T，S）=最大值（0，S- K） .4.1.1迭代次数我们的示例是在四核CPU上测试的。我们在四个线程上并行该算法。在每个线程中，生成路径，并计算每个日期k的矩阵Ub和向量sbare。对于每个线程，我们只需要为所有b保留Ub、vb和当前值之和。当计算在所有线程中完成时，结果被聚合。当我们有全局Ub和Vb，即每个线程的所有矩阵Ub和向量Vb之和时，通过求解Ubαb=Vb来计算回归系数αb。

这一步也可以通过为每个线程中的日期块b求解这个方程来并行完成。当计算系数时，我们在下面的迭代中使用它们来计算UK和VK以及期权价格。在第一次迭代中，我们没有α膝盖。我们决定保留期权直到到期。我们还可以使用前一天计算得出的系数。图1显示了迭代次数对最终价格的影响。在这个图中，生成的路径总数保持不变，只是每次迭代的路径数发生了变化。4.1 4.2 4.3 4.4 4.5 0 50 100 150 200价格迭代次数置信区间价格图1：给定数量路径（100000）的迭代次数对价格的影响。在蒙特卡罗定价过程中，我们计算价格SV=qNPni=1ewiPnij=ni的（加权）方差-1+1P（j）- p其qN=Pni=1ewi（ni- 镍-1). 使用alsoq（2）N=Pni=1ewi（ni-镍-1） 我们得到了标准误差估计ε=rVq（2）NqN。我们绘制了统计95%置信区间，对应于±1.96ε。请注意，它只考虑统计误差，不考虑系统误差。当迭代次数增加时，价格会更接近实际价格4.486美元。我们注意到，对于100000条路径，100次迭代足以收敛。进一步说，图2展示了不同迭代次数的价格趋同[10,20,100,200]。类似地，图3显示了在中期到期日早期锻炼边界的收敛。迭代次数越多，收敛速度越快。然而，100次和200次迭代之间的差异并不显著。在这两种情况下，在10000条路径之后获得了一个良好的价格估计。