基于伪回归的最优停车动态规划

在实践中，人们很清楚，将支付函数本身添加到基函数集通常是有益的。这可能会导致伪回归出现问题，因为无法预期Payoff函数与其他（通常为多项式）基函数的内积以闭合形式给出，从而违反假设5.5。然而，我们可以通过求积、准蒙特卡罗甚至标准蒙特卡罗来计算这些标度积，而额外成本可以忽略不计，特别是在假设5.7的设置中。通过一些额外的工作，我们仍然可以通过Gram Schmidt实现正交性。让我们通过查看最典型的案例来总结本节的结论。可以说，当M K、 J.我们可以选择基函数为正交函数，因此我们考虑命题5.6中的第二种情况。因此，对于标准回归，计算成本与JMK成渐近比例，而伪回归仅产生与JMK成比例的成本。这将带来计算上的优势，尤其是当K很大时。5.2. Longsta off–Schwartz算法。渐进地，基于标准回归的Longstaff–Schwartz算法通常与基于标准回归的Tsitsiklis–van Roy算法产生相同的成本（命题5.4）。提案5.9。Longsta off–Schwartz算法的计算成本（2.6）–（2.8），使用标准回归，isCreg=0JM K+JK.证据首先，我们以成本O（JM）模拟所有轨迹，并以成本O（JM K）评估沿所有模拟值的基本函数。对于反向迭代中的每个步骤j，我们需要以（单个）成本O（MK）设置矩阵N>N。然后我们需要计算代价为O（JM）的右手边Y（j），它假设在时间j+1。

，J已在反向迭代的早期阶段进行了预计算。最后，以成本O（MK+K）计算系数。如果我们将Longstaff–Schwartz算法与伪回归相结合，我们注意到与Tsitiklis–van Roy相比的一个重要差异：在算法的标准情况下（见第3.2节），我们可能需要评估基本函数ψ，ψk每个样品Xj-1，Umr，r=j，J、 在最坏的情况下，这将产生与JKM成比例的成本。因此，我们得到了命题5.10。基于伪回归的Longsta off–Schwartz算法的计算成本Iscpeudo=OJK+K+JMK.DYN公司。OPT编程。通过伪回归17停止如果基函数为正交w.r.t.u，则成本降低到伪=OJMK公司.假设我们实际上处于假设5.7的设置中。那么我们可以再次复制样品。在这种情况下，我们仍然需要从j=0的采样初始点开始模拟完整的轨迹，但我们可以及时“移动”这些样本。在这种情况下，我们只需要计算X0，Umr，r=j，J、 这将产生额外的成本O（JMK）。另一方面，我们只需将每个j的Y（j）组合起来，就可以得到成本组成部分O（JM）。在总体上，我们得到命题5.11。如果假设5.7成立，我们复制样本，那么基于伪回归的Longsta off–Schwartz算法的计算成本CPseudo=OJK+K+JMK+JM.如果基函数为正交w.r.t.u，则成本降低到伪=OJM K+JM.让我们通过查看一个典型案例，再次总结关于计算成本的讨论。

对于真正的百慕大期权，J当然是固定的，而K需要增加，以提高估计值的准确性。因此，渐近考虑的典型情况可能是M K J、 再一次，我们可以很好地假设已经选择了正交基函数，与假设5.7一致。因此，关于伪回归，我们处于命题5.11的第二种情况。在这些条件下，带有标准回归的Longsta off–Schwartz算法的计算成本与JMK近似成比例，而伪回归的成本与JMK近似成比例。同样，从长远来看，标准回归的成本占主导地位。6、数值实验下面的数值实验是在带有IntelR的笔记本电脑上进行的CoreTMi7-6500U处理器和8GB RAM。所有算法都在openSUSE Leap 42.3上运行的GNU Octave版本4.0.3中实现和执行。此外，所有代码都是单线程的。我们考虑n资产上的百慕大最大看涨期权，例如，在[1]中已经考虑过。资产以δ的比率进行相同的分配和收益分配。它们的解为todXit=（r- δ） Xitdt+σXitdWit，Xi=x，t∈ [0，T]，i=1，n、 （6.1）其中wi是独立的标量布朗运动。利率r和σ都是常数。我们假设有J+1练习日期0≤ t<t，…<tJ公司≤ 期权持有人可行使的Tin以获得支付（Xt）=最大值（Xt，…，Xnt）- κ+,（6.2）其中κ>0。此外，我们通过ft（Xt）=e引入了贴现支付函数-rth（Xt）。在本节剩余部分中，假设T=3，r=0.05，δ=0.1，σ=0.2，κ=100。对于j=0，…，我们进一步选择tj=jtj，J、 18克里斯蒂安·拜耳、马丁·雷德曼、约翰·舍恩马克斯6.1。使用Tsitiklis–van Roy进行期权定价。

我们的目标是确定上述百慕大最大看涨期权价值的近似值。为此，我们使用了Tsitiklis–van Roy【10】的算法，其中连续函数的计算'cj（j=0，…，j- 1） 基于标准回归（SR）。另一方面，我们使用第3.1节中解释的算法（参见算法1），其中SR被伪回归（PR）方法代替。在本节中，我们设置J=9。基于PR的算法的总体思想是选择随机初始值Utj~ utjat（6.1）中给出的每个组件xit的每个练习日期tjj。事实上，通过设置utj=emtj+^σtjZ，我们对该方案获得了很好的结果，其中Z~ N（0，1），即Utjis对数正态分布，常数方差参数^σtj≡ ^σ ∈hσpT/2，σ√平均参数mtj=（r- δ） tj公司- 0.5^σ+ln（x）确保E【Utj】=E【Xitj】。然而，事实证明，PR算法对平均参数不是很敏感，因此我们可以选择一个常数，即mtj≡ m=（r- δ） t型- 0.5σt+ln（x），对于固定t∈ [T/2，T]。这意味着我们选择Utj≡ U（或utj≡ u）独立于行使日期，这有利于将基函数评估的数量减少到两个。因此，该方案在计算上比以前更便宜。平均参数m和方差参数^σ的具体选择取决于n，因为我们观察到，如果这些参数随资产数量n略微修改，我们会获得更好的结果。我们选择正交多项式（ψk）k=1，。。。，K关于u。更精确地说，我们在R上引入了用Hi表示的i次Hermite多项式。然后我们定义ψ，ψKvia函数的适当顺序snyj=1Hijln（yj）- m^σ使用i+i+…+在里面≤ p、 其中p∈ N是最大多项式次数，ij∈ 因此，基函数的总数是K=（p+n）！pn

事实上，我们只需选取总阶数达到p的埃尔米特多项式的所有乘积，并使用一些双射将它们赋给指数k=1，K、 在下文中，上述正交函数不仅用于PR，也用于SR ansatz。现在，我们确定“vof the Bermudan option”的初始值x=90、100、110。此外，我们还对n=2，3，4，5资产进行了数值实验。对于n=5，我们将p=4，否则我们将p=5。使用n=5的不同多项式阶数的原因是，我们的目标是实现PRA和基于SR的算法的相同精度，以便能够比较两种方案。通过选择p，在推导连续函数时，使用两种方法的M=2e+06个样本可大致获得相同的输出。当然，也可以为PR选择不同数量的样本，而不是为SR选择不同数量的样本，以便为这两种情况找到完全相同的输出。然而，很难找到这些数量的样本，以使两种算法产生完全相同的输出v。请注意，对于vcan，数量略低的算法总是可以通过使用更多的样本来改进。DYN公司。OPT编程。通过伪回归停止19我们从n=2的情况开始，对于该情况，我们确定m=（r- δ - 0.5σ）T+ln（x）和^σ=0.26。我们发现，在n=2的情况下，PR和SR的表现几乎相同，见表1的第一部分。似乎PR甚至可以产生稍微好一点的‘v’结果。图1a中可以找到相应的计算时间。结果表明，PR算法的速度快了三倍多。对于n>2，也可以采用相同的均值和方差参数。然而，对于n=3，将方差稍微增大到^σ=0.29，会导致结果稍微好一点。

平均参数与n=2时相同。从表1中的第二个部分可以看出，两种算法得出的值大致相同。使用PR的优点是计算时间要少得多。从图1b中我们知道，与SR相比，我们节省了五个以上的因子。在n=4的情况下，与n=3资产的情况相比，方差参数再次扩大，即^σ=0.32。我们也修改了平均参数，在这种情况下，它是m=（r- δ - 0.5σ）2.56+ln（x）。同样，SR和Pryeld的结果质量相同，见表1的第三块，而PR basedalgorithm与SR相比速度非常快。图1c显示，可以节省大于9的系数。从n=4到n=5，只有平均参数更改为m=（r-δ - 0.5σ）3+ln（x）。SR和PR提供大致相同的输出，参见表1的第四部分。此外，图1d显示了基于PR（x）的“vusing PR.x”v（x）计算速度是基于SR参数usedn=290 8.046（0.006）8.030（0.006）K=21，σ=0.26100 13.884（0.008）13.868（0.008）和110 21.322（0.009）21.314（0.009）m=ln（x）的七倍以上- 0.105n=390 11.238（0.007）11.234（0.007）K=56，^σ=0.29100 18.640（0.009）18.640（0.009）和110 27.533（0.010）27.520（0.010）m=ln（x）- 0.105n=490 14.045（0.008）14.049（0.008）K=126，^σ=0.32100 22.638（0.009）22.638（0.010）和110 32.527（0.011）32.531（0.011）m=ln（x）- 0.179n=590 16.567（0.008）16.562（0.008）K=126，^σ=0.32100 26.054（0.010）26.055（0.010）和110 36.665（0.011）36.657（0.011）m=ln（x）- 0.21表1。使用Tsitiklis–van Roy，基于SR和PR的百慕大期权的近似值，J=9。

连续函数的计算基于M=2e+06个样本。20 CHRISTIAN BAYER，MARTIN REDMANN，JOHN SCHOENMAKERS0 2 4 6 8 10 12 14 16 20 PRSR18.425.18时间[秒]（a）n=2.0 10 20 30 40 50 60 70 PRSR68.4612.71时间[秒]（b）n=3.0 50 100 150 200 200 250 300 PRSR296.3232.33时间[秒]（c）n=4.0 50 100 150 200 200 300 350 PRSR349.5848.90时间[秒]（d）n=5的计算时间。图1：。使用Tsitiklis–van Roy和M=2e+06个样本计算延拓函数的时间；n=2、3、4、5和J=9.6.2的标准Versupseudo回归。使用Longstaff–Schwartz进行期权定价。在本节中，我们将研究与第6.1节中相同的问题。然而，我们现在根据Longsta ff–Schwartz确定百慕大最大看涨期权的近似值。再次，我们研究了该方法的基于PR的版本（见第3.2节）和基于SR的方法（见[8]），以推导连续函数cj。DYN公司。OPT编程。通过伪回归21停止，我们从模拟中观察到，对于n>2的Longstaff–Schwartz，使用与第6.1节相同的参数，PR明显快于SR。我们没有再次对Longstaff–Schwartz进行相同的实验，而是只指出了一个在计算时间上表现出巨大增益的典型案例：案例n=4和j=4，以及所有其他参数。表2向我们展示了这两种类型的回归为“vb”提供了相似的值，但与图2相比，使用SR的成本要高出两倍多。x'v（x）基于PR'v（x）基于SR参数usedn=490 13.719（0.008）13.708（0.008）K=126，σn=0.32100 22.170（0.010）22.163（0.010）和110 31.914（0.011）31.915（0.011）mn=ln（x）- 0.179表2。

使用Longstaff–Schwartz，基于SR和PR的百慕大期权的近似值，J=4。0 20 40 60 80 100 120 140 PRSR124.5661.95时间图2。使用Longsta off–Schwartz计算连续函数的时间；n=4和J=4的标准与伪回归。备注6.1。在Tsitiklis–van Roy的背景下，Longsta off–Schwartz算法的伪回归版本相对于标准算法的增益通常小于第6.1节中的增益。原因很清楚：标准算法中的后退步骤（2.6）–（2.8）不能直接修改为基于伪回归的设置。因此，为了在类似于标准方法的基于伪回归的设置中构建停止现金流的向量Y（j），从u下模拟的初始状态开始，为每个练习日期模拟新的轨迹。当然，这使得该过程的成本更高，然而，这种方法避免了在每个练习日期对随机矩阵进行通常昂贵的反演。结论我们将求解百慕大期权的经典回归方法与基于伪回归的新变量进行比较，即Linner22 CHRISTIAN BAYER、MARTIN REDMANN、，JOHN Schoenmakers基于人工基准度量u模拟样本的产品（与任何时间点的基础股价分布不直接相关）。作为一个关键问题，伪回归方法可以避免在每个练习日期设置和反转随机矩阵。因此，如第6节中的数字示例所示，在类似的精度水平下，计算成本可以大大降低。这也源于渐进成本分析，见第5节。

此外，基于伪回归的算法在理论上更容易分析，并导致更短更清晰的收敛性证明（见第4节）。同时，由于可以忽略经典回归误差分析中的对数误差项（由于arandom矩阵的反转），收敛速度略有提高。概率度量u的选择对伪回归算法的成功至关重要。另一方面，尽管w.r.t.u在许多情况下可以为每个时间步选择一个单独的测量值，但该程序是不敏感的。然而，必须以适当的方式选择u，因为错误的选择会导致最终计算的期权价格的错误大幅增加。通常，u的选择应确保U~ u涵盖了所有j的基础随机过程xj的重要领域。这些领域通常可以通过基础过程的动力学粗略估计。在某种意义上，u的特定选择可以与重要性采样进行比较，因为它允许在不引入偏差的情况下更改实际采样点的分布。因此，我们预计，选择u的灵活性可能是有利的，尤其是在资金匮乏的情况下，当回报只有在罕见的情况下才为正时。我们将在今后的工作中更详细地研究这些方面。附录A.证明A。定理4.1的证明。设Uk为u在ψ的线性跨度上的投影。。。，ψK，即（A.1）uK=arg infw∈ span{ψ，…，ψK}ZD | w（z）-u（z）|u（dz）。然后，用γ：=（γ，…，γK）>∈ Rk由（A.2）uK=KXk=1γkψk和α定义∈ Rk由αk定义：=hψk，uiL（u），直接由（A.3）γ=G的标度积得出-1α.根据毕达哥拉斯的规则，EZD | u（z）-u（z）|u（dz）=（A.4）EZDu（z））-英国（z）u（dz）+ZD英国（z）-u（z）u（dz）。DYN公司。OPT编程。

通过伪回归23停止，因此，（4.3）中的第二项由于（A.1）和（A.4）而清晰可见。ψ（z）：=（ψ（z）。。。，ψK（z））>对于（A.4）中的第一项，我们得到u（z）-英国（z）u（dz）=ZDEβ> ψ（z）-γ> ψ（z）u（dz）=ZDE我的>M- α>G-1ψ（z）u（dz）=ZDE我的>M- α>G-1ψ（z）ψ>（z）G-1.毫米>Y- αu（dz）=E我的>M- α>G-1.毫米>Y- α,使用（4.1）、（4.2）、（A.2）、（A.3）和ZDψ（z）ψ>（z）klu（dz）=hψk，ψli=Gkl。因此，我们有0≤ EZD公司u（z）-英国（z）u（dz）≤λ矿山MN>Y- α=λminKXk=1Var毫米>Yk、 从那时起嗯，是的k=MEMXm=1ψk（U（m））Y（m）（A.5）=Eψk（U（1））Y（1）= Eψk（U（1））EhY（1）| U（1）i= hψk，ui=αk。现在，通过观察thatVar毫米>Yk=VarMMXm=1ψk（U（m））Y（m）！（A.6）=MVarψk（U（1））Y（1）=ME Varhψk（U（1））Y（1）| U（1）i+MVar Ehψk（U（1））Y（1）| U（1）i=MEψk（U（1））VarhY（1）| U（1）i+MVarψk（U（1））UU（1）≤σ+Dmgkk，其中λminKXk=1Var毫米>Yk≤σ+DMλmintrGK公司≤σ+DMλminKλmax，然后是（4.3）。24克里斯蒂安·拜耳、马丁·雷德曼、约翰·舍恩马克斯评论A.1。从（A.5）中，我们可以看到，我们基本上是通过简单的蒙特卡罗模拟来近似内积hψk，uiL（u）。乍一看，可以估计（a.6）的平方误差与K/M成正比（直至投影误差本身）。因此，定理4.1指出，即使基函数不是正交的，该误差实际上与K/M成比例。A、 2。引理4.3的证明。