基于加权随机变量的最优停车问题的半可跟踪性

我们感兴趣的是解决形式为：U？t=esssupτ∈Tt，TE[e-r（τ-t） f（Xτ）| Ft]，（24），其中f是Rd，r上的给定实值函数≥ 0和Tt，t代表停车时间τ的集合，取[t，t]中的值。问题（24）与相应偏微分方程的所谓自由边界问题有关。让我们介绍微分算子Lt:Ltu（t，x）=dXi，j=1aij（x）uxixj（t，x）+dXi=1bi（x）uxi（t，x），其中ij（x）=dXk=1σik（x）σjk（x）。我们用Xt，xs（或Xt，x（s）），s表示≥ T、 （23）从x:Xt，Xt=x的动量T开始的解。用u（T，x）表示以下偏微分不等式组的正则解：ut+Ltu- 俄罗斯≤ 0，u≥ f、 （t，x）∈ [0，T）×Rd，（25）ut+Ltu- 俄罗斯（f）- u） =0，（t，x）∈ [0，T）×Rd，u（T，x）=f（x），x∈ Rd，然后在一些温和的条件下（参见，例如[10]）u（t，x）=supτ∈Tt，TE[e-r（τ-t） f（Xt，xτ）]，（t，x）∈ [0，T]×Rd，（26）也就是说，u（T，x）=u？t（x）。有了这个符号，我们就有必要讨论一下本节将要讨论的主要问题。我们的目标是通过一个复杂度为C？的算法，在给定的点（t，x）上以小于ε的精度估计u（t，x）？（ε，d），它是1/ε中的多项式。正如引言中已经提到的，一些众所周知的算法，如回归算法，无法实现这一目标（至少根据文献中现有的复杂性界限）。让我们介绍一下斯内尔包络过程：U？tdef=esssupτ∈Tt，TEFt[g（τ，Xτ）]，（27），其中（比（24）中更一般）g是R上的给定非负函数≥0×Rd。在第一步中，我们通过引入一组有限的停止日期tl=lh，l=1，…，来执行时间离散化。

，L，其中h=T/L，L是一个自然数，接下来考虑离散化的Snell包络过程：Uotl（Xtl）def=ESSUPτ∈Tl，LEFtl[g（τ，Xτ）]，其中Tl，l表示停止时间集，其值在{Tl，…，Tl}集中。注意，可测量函数Uotl（·）的存在是由于过程X的马尔可夫性。时间离散化引起的误差在文献中得到了很好的研究。我们将依赖Thm隐含的以下结果。例如，在[3]中为2.1。命题7让g:[0，T]×Rd→ R为Lipschitz连续且p≥ 1、那么一个最大值为0，。。。，LUtl（Xtl）- Uotl（Xtl）p≤co欧共体oT（1+| x |）L，其中常数co, Co> 0分别取决于b、σ和G的Lipschitz常数。为了获得可接受的离散化误差，我们选择了一个有效的大L，然后重点计算Uo.在下一步中，我们在时间网格ti=iT/L，i=0，…，上使用一些强离散化方案来近似基本过程X，五十、 产生近似X。假设该方案的一步跃迁密度是明确已知的。最简单和最流行的方案是Theuler方案，Xitl+1=Xitl+bi（Xtl）h+mXj=1σij（Xtl）Wjtl+1- Wjtl公司, Xi=Xi，（28）i=1，d、 一般具有强收敛阶1/2，链的一步跃迁密度（Xtl+1）l≥0由“ph（y | x）def=q（2πh）d |∑exp”给出-h类-1（y- x个- b（x）h）>σ-1（y- x个- b（x）h）（29）带∑=σ>∈ Rd×dand h=T/L。现在我们将转向离散时间最优停车问题，可能的停车时间{tl=lh，L=0。

，L}。为此，我们将离散时间马尔可夫链Zldef=xtladapted引入过滤（Fl）def=（Ftl）和gl（x）def=g（tl，x）（略微滥用符号），并考虑离散化的斯内尔包络处理（Xtl）def=esssupτ∈Tl，左Lg（τ，Xτ）= esssupι∈Il，LEFl[gι（Zι）]def=Ul（Zl），（30），其中，由于进程x（或Z）的马尔可夫性，Il，l表示具有{l，…，l}值的停止指数集，以及可测量函数Utl（·）（或Ul（·））存在。U和U之间的距离o由下一个命题控制。命题8存在一个常数CEuler>0，取决于b、σ和g的Lipschitz常数，因此Maxl=0，。。。，LE公司Uotl（Xtl）- Utl（Xtl）≤ 塞勒√h、 因此，将命题7和命题8结合起来产生。推论9如果X由时间步长h=T/L的Euler格式构造，其中L是离散化步数，那么在命题7和命题8的条件下，我们得到了e[| U？（X）- U（x）|]。塞勒√h代表h→ 0，（31）其中。表示根据c达到常数的不等式o, Co还有CEuler。由于Euler格式的转移密度是明确已知的（见（29）），WSM算法可以直接用于构建基于马尔可夫链（Zl）路径的近似U（x）。为了推导得出的估算结果的复杂度界限，我们将做出以下假设。（AG）假设cg>0等于g（t，x）≤ 所有0的重心（1+| x |）≤ t型≤ T、 x个∈ Rd.（32）（AX）假设存在一个常数c'X>0，使得对于所有0≤ l≤ 五十、 EFtlhsupl≤l≤LXlh公司Xlh=xi≤ c'X（1+| X |），X∈ Rd，（33）在L中均匀分布（因此为h）。在Lipschitz条件下，该假设在SDE（23）的系数上得到满足，并且可以使用Burkholder-Davis-Gundy不等式和Gronwall引理加以证明。（AP）进一步假设Xlh，l=0。

L时间与满足Aronson型不等式的跃迁密度plh（y | x）齐次：存在正常数κ和α，因此对于任何x，y∈ Rd和任何l>0时，它保持PLH（y | x）≤κ（2παlh）d/2e-|x个-y | 2αlh。如果（23）中的系数有界且σ一致椭圆，则该假设成立。下一个命题为连续时间最优停止问题的WSM算法提供了复杂性边界。命题10假设假设假设（AG）、（AX）和（AP）成立，那么o通过WSM算法计算精度ε>0的固定L>0的U（x）in（30）的成本在c（ε，d）=cαcgκc（d）fcdTd+7hd+5×ε以上-4日志D+2Th（1+c'X+c'X'X'）ec'X√αT1+c'X+c'X'3/4（cgκ∨ 1)ε. （34）LS WSM QTA∞ 2表2：连续时间最优停车问题不同算法的半可处理性指数计算U的成本？（x） 在精度ε>0的情况下，通过WSM算法以C为界？（ε，d）=cαcgκc（d）fcdTd+7ε2d+14×logd+2T（1+c'X+c'X'X'）ec'X√αT1+c'X+c'X'3/4（cgκ∨ 1)ε. （35）第一个陈述直接来自命题5，采用（19），α=αh，cZ=c'X，L=T/h。然后设置h ε我们得到（35）（可能修改了自然常数c，c）。讨论见（35），ΓWSM=limd%∞直线度ε和0对数C？（ε，d）d对数ε-1=2（36），这表明所提出的算法与连续时间最优停车问题的现有算法相比，至少在半可跟踪性指数方面是有效的。事实上，文献中唯一具有可证明的有限类型限制（36）的算法是Bally、Pag\'es和Printems的量化树算法（QTA）[3]。事实上，通过使停止次数和量化次数趋于一致，使得Thm中相应的误差。

[3]中的2.4-b是平衡的，我们推导出以下复杂度上界c？QTA（ε，d）=Oε6d+6（37）因此ΓQTA=6.4数值实验在以下实验中，我们在连续时间最优停止问题的情况下说明了WSM算法。WSM算法的下界可以使用在独立轨迹集上计算的次优策略来获得。该策略可以直接通过（10）或使用似然权重sp（Z（j）l+1 |·）PNm=1p（Z（j）l+1 | Z（m）l）的插值来构造。做到这一点的最快和最简单的方法是使用基于轨迹训练集的最近邻插值，在所有实验中，将“邻居数”设置为500。4.1一个美国人在一个资产上放置，以说明WSM算法在连续时间内的性能，我们考虑了一个单对数布朗资产上美式看跌期权定价的财务问题，该资产TXT=Xexp（σWt+（r- σ/2）t），其中r表示无风险利率，假设为常数，σ表示恒定波动率。Payoff函数由g（x）=（K）给出-x） +且期权的公平价格为u=supτ∈T[0，T]Ee-rτg（Xτ）.该期权价格的闭合形式解未知，但有各种数值方法可以精确近似V。使用的参数值为r=0.08，σ=0.20，δ=0，K=100，T=3。通过二叉树型算法获得的真实价格的准确估计值为6.9320（见【11】）。在图1中，我们显示了由于WSM、Longstaff和Schwartz[13]（LS）的最小二乘法以及Tsitsiklis和Van Roy[16]（VF）的值函数回归算法，作为在[0，T]上形成均匀网格的停止次数L的函数。

由于在一组新的独立轨迹上估计了估计的连续值，这些下界是使用次优停止规则构造的。在LS和VF中用作基函数的多项式的最大阶数由图例中的数字（2和4）表示。可以看出，当NL增加时，WSM下界更稳定。VF下限似乎随着L的变化而变化→ ∞.5证明5.1命题1的证明l=l陈述已读UL（x）-eUL（x）pL（x | x）dx=Z | x-x |>Rg（x）pL（x | x）dx=εL，R，20 40 60 80 100L5.25.45.65.86.06.26.46.66.8期权价格，N=1000WSMLowVF2LowLS2VF4LowLS420 40 60 80 100L5.25.45.65.86.06.26.46.66.8期权价格，N=2000WSMLowVF2LowLS2VF4LowLS4（a）（b）图1：使用不同方法和统一方法近似的一维美式看跌期权价格的下限网格tk=kT/L，k=0，五十、 行使日期。训练路径的数量为Ntrain=1000（a）和Ntrain=2000（b），在这两种情况下，用于构造下界的新轨迹的数量为Ntest=20000。在LS和VF回归方法中，使用2次和4次多项式基。所以这是真的。假设（12）对于0<l+1为真≤ L

然后，使用| max（a，b）- 最大值（a，c）|≤ |b- c |和eul（x）为| x消失的事实- x |>R，Ul（x）-eUl（x）≤ 1 | x-x个|≤R | max[克（x），E[升+1（Xl+1）| Xl=x]]-最大Hg（x），EheUl+1（Xl+1）Xl=xii+ 1 | x-x |>RUl（x）≤ 1 | x-x个|≤REh公司Ul+1（Xl+1）-eUl+1（Xl+1）Xl=xi+1 | x-x |>RUl（x）。因此我们有归纳法，ZUl（x）-eUl（x）pl（x | x）dx≤Z | x-x |>REhUl+1（Xl+1）-eUl+1（Xl+1）Xl=xipl（x | x）dx+εl，R≤ZUl+1（y）-eUl+1（y）pl+1（y | x）dy+εl，R=LXj=l+1εj，R+εl，R=LXj=lεj，R.5.2命题2的证明，结合假设（32）和（33）收益率，Ul（x）=esssupτ∈Tl，LE[gτ（Zτ）| Zl=x]≤ cgE1+最大值≤l≤L | Zl|Zl=x≤ cg（1+cZ）+cgcZ | x |。使用Z | x-x |>Re-|x个-x | 2αldx≤ e-R8αl（4/3）d/2（2παl）d/2，和z | x-x |>R | x- x | e-|x个-x | 2αldx≤sZ | x-x |>Re-|x个-x | 2αldxsZ | x- x | e-|x个-x | 2αldx≤ e-R8αld/4（2παl）d/2√dαlwe get（注意（4/3）1/2<21/4），εl，R≤κ（2παl）d/2Z | x-x |>R（cg（1+cZ）+cgcZ | x |）e-|x个-x | 2αldx≤κcg（1+cZ+cZ | x |）（2παl）d/2Z | x-x |>Re-|x个-x | 2αldx+κcgcZ（2παl）d/2Z | x-x |>R | x- x | e-|x个-x | 2αldx≤ κcg1+cZ+cZ | x |+cZ√dα√ld/4e-R8αl≡A+B√lcgκe-R8αl，用于l≥ 1（ε0，R>0时R=0）。现在到（12），即命题1，我们得到Ul（x）-eUl（x）pl（x | x）dx≤ LA+B√Lcgκe-R8αL，由此估算（16）。5.3命题3的证明让我们为步骤l编写基于样本的反向动态程序（11）<Lin形式，UlZ（i）l=Z（i）l-x个≤Rmaxgl（Z（i）l），NXj=1Ul+1（Z（j）l+1）wij（38）通过定义权重wij：=p（Z（j）l+1 | Z（i）l）PNm=1p（Z（j）l+1 | Z（m）l），（39），其中l是固定和抑制的。对于一般的Borel函数f，让我们进一步缩写为[f]（x）=E[f（Zl+1）| Zl=x]=Zf（y）p（y | x）dy≥ 0

使用，eUlZ（i）l=Z（i）l-x个≤Rmaxhgl（Z（i）l），E[eUl+1]（Z（i）l）i，（38）和| max（a，b）- 最大值（a，c）|≤ |b- c |，我们因此得到联邦制药-eUl公司N： =NNXi=1Ul（Z（i）l）-eUl（Z（i）l）≤NNXi=1Z（i）l-x个≤RNXj=1升+1（Z（j）升+1）wij- E[eUl+1]（Z（i）l）≤NNXi=1Z（i）l-x个≤RNXj=1wijUl+1（Z（j）l+1）-eUl+1（Z（j）l+1）+NNXi=1Z（i）l-x个≤RNXj=1eUl+1（Z（j）l+1）wij- E[eUl+1]（Z（i）l）≤:Ul+1-eUl+1N+Rl+1，（40），使用（39）中的权重总和为1。因此，可以通过迭代（40）获得，英国-欧盟N≤L-1Xl=kRl+1（41）sinceUL-eUL=0。现在让我们介绍一下oij：=Np（Z（j）l+1 | Z（i）l）pl+1（Z（j）l+1 | x），（42），并考虑通用术语RL+1=NNXi=1Z（i）l-x个≤RNXj=1eUl+1（Z（j）l+1）wij- E[eUl+1]（Z（i）l）≤NNXi=1Z（i）l-x个≤RNXj=1eUl+1（Z（j）l+1）wij公司- woij公司+NNXi=1Z（i）l-x个≤RNXj=1woijeUl+1（Z（j）l+1）-NE[eUl+1]（Z（i）l）=: 期限+期限。由于（9）一个有，期限≤GRNNXi=1NXj=1Z（i）l-x个≤RZ（j）l+1-x个≤Rwij公司- woij公司,根据（39）和（42），我们可以写，wij公司- woij公司=p（Z（j）l+1 | Z（i）l）PNm=1p（Z（j）l+1 | Z（m）l）-Np（Z（j）l+1 | Z（i）l）pl+1（Z（j）l+1 | x）=p（Z（j）l+1 | Z（i）l）PNm=1p（Z（j）l+1 | Z（m）l）1.-NPNm=1p（Z（j）l+1 | Z（m）l）pl+1（Z（j）l+1 | x）.因此获得，期限≤GRNNXj=1Z（j）l+1-x个≤R1.-NPNm=1p（Z（j）l+1 | Z（m）l）pl+1（Z（j）l+1 | x）.我们现在要估计[Rl+1]。E[期限]+E[期限]。它认为≤GRNE“Z（1）l+1-x个≤RNXm=11-p（Z（1）l+1 | Z（m）l）pl+1（Z（1）l+1 | x）！#≤GRNDR+GRNE“NXm=2Z（1）l+1-x个≤R1级-p（Z（1）l+1 | Z（m）l）pl+1（Z（1）l+1 | x）！#withDR：=E“Z（1）l+1-x个≤R1.-p（Z（1）l+1 | Z（1）l）pl+1（Z（1）l+1 | x）#.现在考虑i.i.d.随机变量η（l+1）m：=Z（1）l+1-x个≤R1级-p（Z（1）l+1 | Z（m）l）pl+1（Z（1）l+1 | x）！，m=2。。。，N、 平均值为零。

然后，由Cauchy Schwartz所作NXm=2η（l+1）m≤VutenXm=2η（l+1）m！=急诊室√N威瑟尔：=Varη（l+1）= EZ（1）l+1-x个≤R1.-p（Z（1）l+1 | Z（2）l）pl+1（Z（1）l+1 | x）,关于术语，让我们写出[eUl+1]（Z（i）l）=ZeUl+1（y）p（y | Z（i）l）pl+1（y | x）pl+1（y | x）dy=E“eUl+1（Z0，xl+1）p（Z0，xl+1 | Z（i）l）pl+1（Z0，xl+1 | x）#，其中Z0，xis是一条独立的虚拟轨迹。因此我们有[Term]=EZ（1）l-x个≤RwoeUl+1（Z（1）l+1）-NE[eUl+1]（Z（1）l）+ ENXj=2ζ（l+1）j,其中，对于j=2。。。，N、 随机变量ζ（l+1）j：=Z（1）l-x个≤Rwo1 Jeul+1（Z（j）l+1）-NE[eUl+1]（Z（1）l）=Z（1）l-x个≤RNp（Z（j）l+1 | Z（1）l）pl+1（Z（j）l+1 | x）eUl+1（Z（j）l+1）- E“eUl+1（Z0，xl+1）p（Z0，xl+1 | Z（1）l）pl+1（Z0，xl+1 | x）#！是i.i.d.且具有零均值。我们同样拥有Cauchy Schwartz，ENXj=2ζ（l+1）j≤武特NXj=2ζ（l+1）j=rNVar公司ζ（l+1）≤ FRGR公司/√N、 其中fr=EZ（1）l-x个≤Rp（Z（2）l+1 | Z（1）l）pl+1（Z（2）l+1 | x）=Z Z | y-x个|≤Rp（y | x）pl+1（y | x）pl（x | x）dxdy。第二，一相Z（1）l-x个≤RwoeUl+1（Z（1）l+1）-NE[eUl+1]（Z（1）l）≤NE“Z（1）l-x个≤Rp（Z（1）l+1 | Z（1）l）pl+1（Z（1）l+1 | x）eUl+1（Z（1）l+1）#+NE“Z（1）l-x个≤RE“eUl+1（Z0，xl+1）p（Z0，xl+1 | Z（1）l）pl+1（Z0，xl+1 | x）##≤GRNE“Z（1）l+1-x个≤Rp（Z（1）l+1 | Z（1）l）pl+1（Z（1）l+1 | x）#+GRNE“| Z0，xl+1-x个|≤Rp（Z0，xl+1 | Z（1）l）pl+1（Z0，xl+1 | x）#=：GRNHR。接下来是Dr≤ 1+E“Z（1）l+1-x个≤Rp（Z（1）l+1 | Z（1）l）pl+1（Z（1）l+1 | x）#=1+Zpl（x | x）dxZ | y-x个|≤Rp（y | x）pl+1（y | x）dy≤ 1+FR。此外，显然有ER≤ 2+2FR和HR≤ 1+FRsinceE“| Z0，xl+1-x个|≤Rp（Z0，xl+1 | Z（1）l）pl+1（Z0，xl+1 | x）#≤ 现在把（41）中的期望值收集起来，我们得到了，呃英国-欧盟镍≤ （L）-k） GRp2+2FR+FR√N+2+2FRN！(43)≤3 +√（L）- k） GR1+FR√N、 假设N的取值为（1+FR）/√N<1.5.4命题5的证明为了达到所需的精度ε>0，让我们取R和N大值，使（18）中的两个误差项都等于ε/2。

因此，我们首先取ε，d=（8αL）1/2log1/2Lcgκ1+cZ+cZ | x |+cZ√dαL1+d/4ε，即R%∞ 当d+ε-1% ∞. 然后带上 表示R%∞ 直到某个自然常数，Nε Lcgκ（e/α）d/2d-d/2Rd+2εε-2. αcgκ（8e/d）d/2Ld/2+3×ε-2日志/2+1升1+cZ+cZ | x |+cZ√dαL1+d/4cgκε。因此，计算工作量（复杂性）由c（d）fNεL给出≤ cαcgκc（d）f（8e/d）dLd+7×ε-4logd+2L1+cZ+cZ | x |+cZ√dαL1+d/4cgκε（44），其中cis为自然常数。现在让我们写下-dlogd+2升1+cZ+cZ | x |+cZ√dαL1+d/4cgκε=dlogd+2L1/d1+cZ+cZ | x |+cZ√dαL1/d1/d+1/4（cgκ）1/dε1/d.然后，使用基本估计a+b√d1/天≤ aeb/a，对于a，b>0，d≥ 假设ε<1，（44）表示（19）。5.5命题8的证明一方面，一个hasUotl（Xtl）- Utl（Xtl）=esssupτ∈Tl，LEFtl[g（τ，Xτ）]- esssupτ∈Tl，左Lg（τ，Xτ）≤ esssupτ∈Tl，左Lg（τ，Xτ）- g（τ，Xτ）≤ esssupτ∈Tl，左Lg（τ，Xτ）- g（τ，Xτ）,另一个有相似的UTL（Xtl）- Uotl（Xtl）=esssupτ∈Tl，左Lg（τ，Xτ）- esssupτ∈Tl，LEFtl[g（τ，Xτ）]≤ esssupτ∈Tl，左Lg（τ，Xτ）- g（τ，Xτ）≤ esssupτ∈Tl，左Lg（τ，Xτ）- g（τ，Xτ）.因此我们得到Uotl（Xtl）- Utl（Xtl）≤ Esup0≤s≤Tg（s，Xs）- g（s，Xs）≤ LgE公司sup0≤s≤TXs型- Xs型≤ 塞勒√h、 由于Euler格式的强阶性，对于g.References【1】Ankush Agarwal和Sandeep Juneja，Lg是一些Lipschitz常数。比较了百慕大期权定价的随机网格法和最小二乘法的最优收敛速度。《2013年冬季模拟会议论文集：模拟：在复杂世界中做出决策》，第701-712页。IEEE出版社，2013年。[2] 罗伯特·阿森科特。小规模临时就业：发展机会研讨会。一、 在《数学讲师》第1059卷第十八期《概率研讨会》中。，第402–498页。柏林斯普林格，1984年。[3] 弗拉德·巴里、吉勒·帕格斯和雅克·普林特姆斯。