8 results
Search Results
Now showing 1 - 8 of 8
- ItemMultilevel dual approach for pricing American style derivatives(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2011) Belomestny, Denis; Schoenmakers, John G.M.In this article we propose a novel approach to reduce the computational complexity of the dual method for pricing American options. We consider a sequence of martingales that converges to a given target martingale and decompose the original dual representation into a sum of representations that correspond to different levels of approximation to the target martingale. By next replacing in each representation true conditional expectations with their Monte Carlo estimates, we arrive at what one may call a multilevel dual Monte Carlo algorithm. The analysis of this algorithm reveals that the computational complexity of getting the corresponding target upper bound, due to the target martingale, can be significantly reduced. In particular, it turns out that using our new approach, we may construct a multilevel version of the well-known nested Monte Carlo algorithm of Andersen and Broadie (2004) that is, regarding complexity, virtually equivalent to a non-nested algorithm. The performance of this multilevel algorithm is illustrated by a numerical example.
- ItemOptimal stopping via deeply boosted backward regression(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2018) Belomestny, Denis; Schoenmakers, John G.M.; Spokoiny, Vladimir; Tavyrikov, YuriIn this note we propose a new approach towards solving numerically optimal stopping problems via boosted regression based Monte Carlo algorithms. The main idea of the method is to boost standard linear regression algorithms in each backward induction step by adding new basis functions based on previously estimated continuation values. The proposed methodology is illustrated by several numerical examples from finance.
- ItemSemi-tractability of optimal stopping problems via a weighted stochastic mesh algorithm(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2019) Belomestny, Denis; Kaledin, Maxim; Schoenmakers, John G.M.In this article we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete and continuous time optimal stopping problems. It is shown that in the discrete time case the WSM algorithm leads to semi-tractability of the corresponding optimal stopping problem in the sense that its complexity is bounded in order by $varepsilon^-4log^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 complexity bounds known in the literature. We illustrate our theoretical findings by a numerical example.
- ItemSolving optimal stopping problems via randomization and empirical dual optimization(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2021) Belomestny, Denis; Bender, Christian; Schoenmakers, John G. M.In this paper we consider optimal stopping problems in their dual form. In this way we reformulate the optimal stopping problem as a problem of stochastic average approximation (SAA) which can be solved via linear programming. By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties such as faster convergence rates and reduced complexity as compared to the non randomized procedure. We illustrate the performance of our algorithm on several benchmark examples.
- ItemRobust multiple stopping -- A path-wise duality approach(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2020) Laeven, Roger J. A.; Schoenmakers, John G. M.; Schweizer, Nikolaus F. F.; Stadje, MitjaIn this paper we develop a solution method for general optimal stopping problems. Our general setting allows for multiple exercise rights, i.e., optimal multiple stopping, for a robust evaluation that accounts for model uncertainty, and for general reward processes driven by multi-dimensional jump-diffusions. Our approach relies on first establishing robust martingale dual representation results for the multiple stopping problem which satisfy appealing path-wise optimality (almost sure) properties. Next, we exploit these theoretical results to develop upper and lower bounds which, as we formally show, not only converge to the true solution asymptotically, but also constitute genuine upper and lower bounds. We illustrate the applicability of our general approach in a few examples and analyze the impact of model uncertainty on optimal multiple stopping strategies.
- ItemThe real multiple dual(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2009) Schoenmakers, John G.M.In this paper we present a dual representation for the multiple stopping problem, hence multiple exercise options. As such it is a natural generalization of the method in Rogers (2002) and Haugh and Kogan (2004) for the standard stopping problem for American options. We consider this representation as the real dual as it is solely expressed in terms of an infimum over martingales rather than an infimum over martingales and stopping times as in Meinshausen and Hambly (2004). For the multiple dual representation we present three Monte Carlo simulation algorithms which require only one degree of nesting.
- ItemSimulation based policy iteration for American style derivatives : a multilevel approach(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2012) Belomestny, Denis; Ladkau, Marcel; Schoenmakers, John G.M.This paper presents a novel approach to reduce the complexity of simulation based policy iteration methods for pricing American options. Typically, Monte Carlo construction of an improved policy gives rise to a nested simulation algorithm for the price of the American product. In this respect our new approach uses the multilevel idea in the context of the inner simulations required, where each level corresponds to a specific number of inner simulations. A thorough analysis of the crucial convergence rates in the respective multilevel policy improvement algorithm is presented. A detailed complexity analysis shows that a significant reduction in computational effort can be achieved in comparison to standard Monte Carlo based policy iteration.
- ItemRobust optimal stopping(Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Krätschmer, Volker; Ladkau, Marcel; Laeven, Roger J.A.; Schoenmakers, John G.M.; Stadje, MitjaThis paper studies the optimal stopping problem in the presence of model uncertainty (ambiguity). We develop a method to practically solve this problem in a general setting, allowing for general time-consistent ambiguity averse preferences and general payoff processes driven by jump-diffusions. Our method consists of three steps. First, we construct a suitable Doob martingale associated with the solution to the optimal stopping problem using backward stochastic calculus. Second, we employ this martingale to construct an approximated upper bound to the solution using duality. Third, we introduce backward-forward simulation to obtain a genuine upper bound to the solution, which converges to the true solution asymptotically. We analyze the asymptotic behavior and convergence properties of our method. We illustrate the generality and applicability of our method and the potentially significant impact of ambiguity to optimal stopping in a few examples.