期权定价中的维度诅咒与最优解

尽管Chen和Glasserman（2007）进行了密切相关的观察，但似乎最佳停止和最大流量/最小切割之间的明确联系是新颖的。我们将进一步探索这一联系，例如，应用其他算法，从成熟的最大流量理论到最佳停车和期权定价，作为未来研究的一个有趣方向。此外，我们注意到，最优停止和期权定价因此为网络流量作为建模工具和优化框架的强大功能提供了另一个简单而优雅的证明。N的特殊结构赋予了潜在的最大流量问题一些特殊的特征，这可能有助于设计其他流量检测算法以实现最佳停止。我们注意到，有大量关于网络相关家族的专门算法ms的文献（Br ucker（1984）、Ho Off man（1988）、Goldberg and Tarjan（1988）、Ho Off man（1992）、Vishkin（1992）、Cohen（1995））。例如，让我们回顾一下，在s-t流问题中，阻塞流是一种可行的流，因此每个s-t路径至少有一条饱和边，即其流量等于该边的capa城市的边。众所周知，在一般的最大s-t流量问题中，阻塞流量不一定是最优的，尽管任何最优流量都必须是阻塞流量。然而，在树状网络（如N）中，每个阻塞流都是最优的，这是事实。一位直截了当的Chen和Goldberg的主张如下：击败期权定价和最优停止矛盾论证中的维度诅咒，这是众所周知的，我们省略了细节（Hooffman（19851992））。

这一事实提供了一种不同的方法来解释0-sure-optimal对偶鞅的几个性质，这些性质在以前的工作中出现过，这些性质都归结为这样一个事实：如果某个过程沿每个样本路径都有一个零，那么某个鞅必须是对偶最优的。由于最大流量已经是一个多项式时间的可解问题，而Nis上的最大流量问题由于其树结构更容易解决（事实上可以通过一个简单的动态程序来解决，该程序在概念上相当于反向归纳法以达到最佳停止），人们当然可以问，为什么路径相关的最佳停止ping应该被视为一个难题。答案是，eve n非常快的最大流量算法通常集中在节点和边数的运行时多项式上，对于路径相关的最优停止，它将在T中呈指数增长。我们的纯对偶表示和定理1可以解释为这类流量问题的算法，它在一系列回合中同时沿所有路径增加流量（我们展开的每一项对应于给定回合中推动的总流量）。例如，在第一轮中，a流沿着对应于γ的s-t路径推动∈特奎尔斯造币厂∈[1，T]Zt（γ[T]）×P（Y【T】=γ），并且第一轮的总流量pu（通过将所有部分相加）等于E【mint∈[1，T]Zt]。类似地，对于t∈ [1，T- 1], γ ∈t、 一个d v∈ S、 第一轮沿边缘（nγ，nγ| v）推动的流量等于E迷你∈[1，T]Zi英尺+1（γ| v）×PYt+1=γ| v, 我们注意到，可行性（水资源保护能力）来自以下事实：迷你∈[1，T]Zi英尺+1（γ| v）≤Zt+1（γ| v）。在给定的轮数后，Theorem 2限制了与最优性的距离，而我们的算法结果可以解释为提供了一种非常快速的随机算法，可以预先预测每轮中推动的流量（因此是最佳值本身）。3.4.

当然最优对偶和算法加速在这一节中，我们对某些对偶鞅可能是最优的这一更严格的意义进行了评论，注意到我们的方法不具备这一性质，并推测这可能在允许我们的方法如此快速地产生近似解方面起着重要作用。对于1≤ t型≤ t型≤ T，let Tt，tdenote所有整数值停止时间τ的集合，适用于F，s.T.w.p.1 T≤ τ ≤ t、 让我们说M∈ Mhas确定的最优性质（w.r.t.Z）如果：1。P造币厂∈[1，T]Zt公司- Mt公司= 选择=1.和2。就我而言∈ [1，T]，P造币厂∈【i，T】Zt公司- Mt+Mi= infτ∈Ti，TE【Zτ| Fi】= 1.我们注意到这里我们只提到了0-均值鞅，因为它简化了相关的讨论（并且是w.l.o.gby适当的翻译和已知的结果）。如Schoenmakers等人（2013）所述，每个最优停止问题都有这样一个确定的最优对偶解，这一性质可能有助于算法设计，因为它产生了具有零方差的某些超上界的最优性特征。Schoenmakers et al.（2013）还指出，有一些对偶方法是0-sure-optimal martingales，但不一定是最优鞅，尽管大多数方法是Schen和Goldberg：在期权定价和最优止损中击败维数诅咒在最优对偶解上的实际收益率。有趣的是，正如我们现在通过一个简单的例子展示的那样，我们的方法不一定会产生一个最优鞅，在这个例子中，我们将所有相关的证明都推迟到技术附录中。考虑尺寸D=1，地平线T=3的设置；Y=0 w.p.1；Y=1w。p、 1；没错。p、 ，等于1 w.p。；停止问题就是infτ∈TE[Yτ]，即gt（Y[t]）=所有t的Y∈ [1, 3].引理7。在此设置中，唯一（0-mea n）肯定最优对偶鞅M satifiesm（0）=M（0，1）=0，M（0，1，1）=，M（0，1，）=-.

因此，P（M=0）=P（M=0）=1，而P（M=）=P（M=-) =. 然而，我们的方法得出的最优对偶鞅MAR对所有t都满足P（MARt=0）=1。我们怀疑，缺乏确定的最优性可能是我们的方法实现快速近似的根本原因。直觉上，任何产生确定最优对偶鞅的方法（在某种意义上）都必须解决N的所有子树上定义的所有子问题。我们的近似方法是快速的，因为它不必这样做。我们将把这种推理形式化，并理解相关的下界以及我们的方法与对偶公式的联系作为未来研究的一个有趣方向。收敛速度和定理2-5的证明在这一节中，我们证明了定理2-5，这是我们关于收敛速度的主要结果。在这一过程中，我们证明了一个更强的路径收敛结果，这将使我们能够在ApproxiateValue函数的标准框架之外构造出可证明良好的近似策略。我们还证明，对我们的方法稍加修改，即使在E[（ZT）]要比OPT大得多，并将这些结果应用于最佳停止ping文献中感兴趣的几个问题-i.i.d.设置和Robbins问题。最后，我们提供了几个额外的示例，说明我们的方法在某些情况下可以更快地收敛。4.1. 定理2的证明在这一节中，我们证明了c收敛结果的主要速率定理2。首先，我们证明了一个更强大的路径收敛结果，本质上，在扩展的r k次迭代之后，每个样本路径的最小值为mostk+1。这是一个比OREM 2中给出的更有力的陈述，OREM 2中只考虑预期。

我们首先介绍以下stro ng convergenceresult，它的pro of出人意料地简单。引理8。假设w.p.1 Zt∈ [0，U]对于所有t∈ [1，T]。那么对于所有k≥ 1，w.p。1薄荷∈[1，T]Zkt≤英国。Chen和Goldberg：战胜期权定价和最优止损中的维度诅咒证明：请注意，通过定义、可测量性和引理1，对于所有k≥ 1，Zk+1T=ZT-Pki=1mint∈[1，T]青春痘≥ 0 w.p.1。根据引理1保证的单调性，可以得出w.p.1，k×mint∈[1，T]Zkt≤ ZT公司≤ U、 接下来是期望的结果。Q、 定理2的E.D.证明：用引理1，OPT=Pki=1E[mint∈[1，T]Zit]+infτ∈TE【Zk+1τ】。让tingτk+1停止第一次Zk+1t的停止时间≤k+1（如果不存在这样的时间，则在时间T处停止），引理8意味着E[Zk+1τk+1]≤k+1。因此infτ∈TE[Zk+1τ]≤k+1，并结合上述内容完成证明。Q、 E.D.4.2。prophet不等式的交替边界和定理3的证明在最优停止中，一些最著名的结果涉及所谓的p-rophet不等式，与infτ相关∈TE[Zτ]至E[铸币厂∈[1，T]Zt]在Z上的各种假设下，包括有界性、独立性等，我们不打算在这里调查关于此类不平等的大量文献，而是让读者参考Hill和Kertz（1992）的经典调查，以及Lucier（2017）的更近的调查（更具经济学导向的视角）。

我们注意到，文献中的许多结果仅在独立性假设下成立，这将不适合我们的目的，就像{Zt，t∈ [1，T]}是i.i.d.，{Zt，T∈ [1，T]}一般不会这样。然而，也有一些显著的例外，包括Hill和Ke rtz（1983）的以下结果。虽然最初是以最大化的形式陈述的，但我们在此陈述了相应的版本形式化，这很容易从Hill和Kertz（19 83）的原始结果中得到，我们省略了细节。回想一下，对于x∈ [0，1]，h（x）=（1- x） 日志（1-x） ；对于k≥ 2和x∈ [0，1]，hk（x）=h香港-1（x）.引理9（有界序列的Prophet不等式（Hill and Kertz（1983）））。假设PZt公司∈ [0, 1]= 1 f或所有t∈ [1，T]。然后选择- E[铸币厂∈[1，T]Zt]≤ h（可选）。4.2.1. 定理3的证明。定理3的证明：我们首先说明了H的一些基本性质，这些性质很容易通过简单的微积分参数验证，我们省略了细节。第一，h（x）∈ [0，1]对于所有x∈ [0, 1].第二，h（x）≤ x代表所有x∈ [0，1]，然后是一个直接的归纳论证，对于每个固定的x∈ [0，1]，{hk（x），k≥ 1} 是单调递减的。第三，他严格递增[0，1- 经验值(- 1)]. 第四，h（x）≤ 经验值(-1） 对于所有x∈ [0, 1].接下来，我们证明，对于所有k≥ 1，可选- 埃克≤ 香港（OPT），并通过入职培训进行。因为引理1意味着OPT=Ek+infτ∈对于所有k，TE【Zk+1τ】≥ 1，对于所有k，所需结果等效于提供≥ 1，infτ∈TE[Zk+1τ]≤ 香港选择. 基本情况k=1紧跟引理1和引理9。现在，让我们从归纳法开始。假设理想的陈述是trueChen和Goldberg：击败期权定价中的维度诅咒和s ome k的最优停止≥ 1.

然后从定义，可选停止，引理9，infτ∈TE[Zk+2τ]等式infτ∈TE公司Zk+1τ- E[铸币厂∈[1，T]Zk+1t | Fτ], 自身等于infτ∈TE[Zk+1τ]- E[铸币厂∈[1，T]Zk+1t]≤ h类infτ∈TE[Zk+1τ].根据我们的归纳假设，infτ∈TE[Zk+1τ]≤ 香港选择. 正如我们已经表明的那样，香港选择≤ h类选择≤ 经验值(-1) < 1 - 经验值(-1） ，his在[0，1]上增加- 经验值(- 1） ]之后infτ∈TE[Zk+1τ]≤ h类香港选择= 香港+1（可选）。结合以上完成归纳，再结合一些直代数完成定理的证明。Q、 E.D.我们注意到，不幸的是，它可以证明hk（x）不在一般情况下（即，如果一个人在所有x中采取最坏的情况∈ [0，1]）得到一个比T heorem 2更好的界作为k→ ∞. 然而，它可能会对OPT的特定值产生强边界。例如，如果OPT接近1，那么定理3意味着我们的方法即使在一个单一的ite比率之后也有很小的误差。更一般地，引理9也可以用来证明两个OPT- ek以及在我们展开的第k次迭代过程中取得了多少进展，例如，通过使用以下事实（源自astraightforward Taylor展开），h（x）~ x个-xas x↓ 0，尽管我们在这里不进行这种分析。4.3. 交替界限当Z是无界的并且证明定理4时，我们现在完成定理4的证明，它提供了一个关于收敛速度的界限，这是完全通用的，即不需要归一化，也不需要通过任何上界重新调整绝对误差，甚至不需要存在任何上界。定理4的证明：首先，我们声明对于所有k≥ 1，E[铸币厂∈[1，T]Zkt]≤k×选项。（6） 事实上，这完全遵循了单调性和引理1，这也意味着（通过一些简单的代数）为了证明整个定理，必须证明infτ∈TE[Zk+1τ]≤ 2 ×OPT×E[（ZT）]×k。

（7） 要继续，让我们考虑以下thr eshold策略的性能。让xk=E[（ZT）]×OPT×k-1.. 考虑第一次停止Zk+1t的政策≤ xk，如果[1，T]中不存在这样的T，则简单地停止时间T。通过τk计算该停车时间，注意w.p.1 Zk+1τk≤xk+I造币厂∈[1，T]Zk+1t>xkZk+1T，通过单调性（意味着Zk+1T≤ ZTw。p、 1）在mostChen和Goldberg：击败期权定价和最优止损中的维度诅咒XK+I造币厂∈[1，T]Zk+1t>xkZT。考虑到期望值和适用的Cauchy-Schwarz，我们发现[Zk+1τk]最多为xk+E[（ZT）]×P造币厂∈[1，T]Zk+1t>xk. 进一步应用Markov\'sinequality和（6），我们得出E[Zk+1τk]最多为xk的结论+OPT×k-1×E[（ZT）]xk= 2xk，完成验证。Q、 E.D.4.4。i.i.d.设置和Robbins问题的备用边界在某些情况下，可能需要不仅保证绝对误差，而且保证相对误差或。也就是说，一个人可能会在几个回合后出错，这个错误最多只是OPT本身的一个小错误。Theo rem 4产生这样的结果，只要E[（ZT）]比OPT大不了多少倍。然而，文献中深入研究的许多特定理论停止问题，例如Z是[0,1]上均匀分布的i.i.d.（即U[0,1]）的设置，或标定的Robbins问题（B russ（2005）），都具有以下特征：当T较大时，E[（ZT）]比OPT大很多倍。在这种情况下，定理2-4的边界可能需要k非常大（用t缩放），才能获得较小的相对误差。我们现在表明，对我们的方法稍加修改即可克服这一问题。我们不认为，尽管我们怀疑我们的方法，未经改进，也能在此类问题的相对误差（未被我们证明的界限捕获）下取得良好的性能，但这是一个有趣的开放问题。

让Y={Yi，i≥ 1} 表示T的U[0,1]r.v.s.的i.i.d.序列≥ 1和T∈ [1，T]，let gUt（Y[T]）= Yt；和gRt（Y[t]）=Pti=1I（Yi≤ Yt）+（T- t） 年初至今。然后简单地验证了r.v.s的i.i.d.U[0,1]序列的最优停止问题等价于问题OPTU（T）= infτ∈TE公司gUτ（Y[τ]）. 我们注意到，由于这一问题是经典的al问题，其解决方案已被充分理解（Gilbert和Mosteller（1966），Kennedy和Kertz（1991）），例如，它被称为atlimT→∞T×OPTU（T）=2，在这种情况下，我们的结果仅说明了我们框架的适应性。同样可以证实（Bruss（2005））著名的Robbins问题等同于OPTR（t）问题= infτ∈TE公司gRτ（Y[τ]）. 然而，对于这个问题，我们知之甚少，而且我们对OPTR（T）的价值和（近似）最优政策的性质的理解仍然是近期大量研究中的公开问题（Bruss（2005），Den dievel et al.（2016），G nedin and Iksanov（2011），Meier et al.（2017））。例如，虽然已知Limt→∞OPTR（T）存在，e xact极限值仍然是一个未决问题。让罗宾斯的公共关系问题如此棘手的一个方面是，它表现出了完全的历史依赖性，即使是在有限的时间内→ ∞ （Bruss（2005））。当然，对于我们的方法来说，这种依赖性不是问题。我们的程序如下。请注意，由于zt可能比OPT大得多，因此如果一个人运气不好，那么它并不意味着在时间T停止∈[1，T]Zktwas大于预期。相反，我们使用的事实是，对于i.i.d。

停止U[0,1]r.v.s和Robbins问题，f或任何固定η∈ （0，1），如果T很大（对于固定η），则很像存在T∈ [(1 - η） T，T]suchChen和Goldberg：击败期权定价和最优止损中的维度诅咒，即Zt不会比OPT大太多（这里“太多”将是η的一些函数），而且一些止损时间（在这个区间上）几乎可以达到预期的效果。因此，我们继续采用修正的扩展，其中我们只取第一个（1）的最小值- η） T时间段，如果我们运气不好，留给我们足够的时间自我纠正。然后，通过取一个双极限来证明结果，其中η被设置为所需精度的适当函数，并应用了几个附加边界。我们注意到，我们对i.i.d.sett Ingan和Robbins问题的结果来自于我们在技术附录引理20中证明的更一般的界，这可能对其他此类Stop-in-g问题有用。更正式地说，让我们定义一个修改后的扩展，如下所示。对于η∈ （0，1）和t∈ [1，T]，letZη，T= Zt。对于k≥ 1, η ∈ （0，1），t∈ [1，T]，设Zk+1η，T= Zkη，t- E迷你∈[1,(1-η） T型]Zkη，i | Ft. 然后，相应的收敛结果如下所示。Let Hk（η）= E[最小1≤t型≤(1-η） T型Zkη，t]和Ek（η）=Pki=1Hi（η）。定理8。存在一个绝对的严格正有限常数C，与任何其他常数无关，对于所有t≥ 1和k≥ 1.OPTU（T）- 埃克（k+1）-≤ C×（k+1）-×OPTU（T）；和OPTR（T）- 埃克（k+1）-≤ C×（k+1）-×OPTR（T）。我们将定理8的证明推迟到技术附录中。定理m 8的一个重要方面是，展开式中获得良好相对误差所需的项数与时间ho rizon T无关。