英文标题：
《Semi-tractability of optimal stopping problems via a weighted stochastic
mesh algorithm》
---
作者：
D. Belomestny, M. Kaledin and J. Schoenmakers
---
最新提交年份：
2019
---
英文摘要：
In this article we propose a Weighted Stochastic Mesh (WSM) Algorithm for approximating the value of a discrete and continuous time optimal stopping problem. We prove that in the discrete case the WSM algorithm leads to semi-tractability of the corresponding optimal problems in the sense that its complexity is bounded in order by $\\varepsilon^{-4}\\log^{d+2}(1/\\varepsilon)$ with $d$ being the dimension of the underlying Markov chain. Furthermore we study the WSM approach in the context of continuous time optimal stopping problems and derive the corresponding complexity bounds. Although we can not prove semi-tractability in this case, our bounds turn out to be the tightest ones among the bounds known for the existing algorithms in the literature. We illustrate our theoretical findings by a numerical example.
---
中文摘要：
在本文中，我们提出了一种加权随机网格（WSM）算法来逼近离散和连续时间最优停止问题的值。我们证明了在离散情况下，WSM算法导致相应优化问题的半可处理性，即其复杂性按$\\ varepsilon ^{-4}\\ log ^{d+2}（1/\\ varepsilon）$的顺序有界，其中$\\ d$是底层马尔可夫链的维数。此外，我们在连续时间最优停止问题的背景下研究了WSM方法，并推导了相应的复杂性界。虽然我们无法证明这种情况下的半可跟踪性，但我们的边界是文献中已知的现有算法的边界中最紧的边界。我们通过一个数值例子来说明我们的理论发现。
---
分类信息：

一级分类：Quantitative Finance 数量金融学
二级分类：Computational Finance 计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Computer Science 计算机科学
二级分类：Numerical Analysis 数值分析
分类描述：cs.NA is an alias for math.NA. Roughly includes material in ACM Subject Class G.1.
cs.na是Math.na的别名。大致包括ACM学科类G.1的材料。
--
一级分类：Mathematics 数学
二级分类：Numerical Analysis 数值分析
分类描述：Numerical algorithms for problems in analysis and algebra, scientific computation
分析和代数问题的数值算法，科学计算
--

---
PDF下载：
-->