Monte-Carlo methods for backward stochastic differential equations : segment-wise dynamic programming and fast rates for lower bounds

Abstract

In this thesis, we study two different algorithms using Monte-Carlo methods for solving backward stochastic differential equations. In the first chapter, we present a new algorithm where the backward stochastic differential equation is discretized to a dynamic programming equation alternating between a multi-step forward approach on segments of the time grid and a one-step scheme between segments. Conditional expectations are computed via least squares regression on function spaces. We optimize the length of the segments in dependence on the dimension and smoothness of the backward stochastic differential equation and compute the complexity needed to achieve a desired accuracy in the limit as the number of time points in the discretization goes to infinity. In the second chapter, we consider a discretized backward stochastic differential equation in form of a dynamic programming equation and study an algorithm for constructing lower bounds for its value at time zero. The algorithm uses a pre-computed approximate solution of this equation to sample a control process which is used to derive the lower bound for the solution. We derive asymptotic error bounds and compute the complexity required to achieve a desired accuracy in dependence on the input approximation. The results of both algorithms are illustrated by numerical examples.

Diese Arbeit beschäftigt sich mit zwei Algorithmen zur Lösung von rückwärtsstochastischen Differentialgleichungen mit Hilfe von Monte-Carlo Methoden. Im ersten Kapitel wird ein neuer Algorithmus vorgestellt, der auf einem Diskretisierungsverfahren beruht, welches zwischen einer Mehr-Schritt Darstellung auf Zeitsegmenten und einem Ein-Schritt Verfahren zwischen den Segmenten alterniert. Auftretende bedingte Erwartungswerte werden dabei als Projektionen auf endlich dimensionale Funktionenräume berechnet. Die Wahl der Segmentlänge wird in Abhängigkeit der Glattheit und der Dimension der Differentialgleichung optimiert und es wird der asymptotische Rechenaufwand ermittelt, welcher notwendig ist um eine vorgegebene Genauigkeit zu erzielen. Im zweiten Kapitel wird ein Algorithmus zur Konstruktion von unteren Schranken der Lösung rückwärtsstochastischer Differentialgleichungen zum Startzeitpunkt untersucht. Hierfür wird mit Hilfe einer vorab berechneten Approximation der Lösung ein Kontrollprozess simuliert mit dessen Hilfe schließlich die Schranke berechnet wird. Es werden asymptotische Fehlerschranken sowie der erforderliche Rechenaufwand zur Erzielung einer vorgegebenen Genauigkeit hergeleitet. Die theoretischen Ergebnisse bezüglich der beiden Algorithmen werden mit numerischen Beispielen illustriert.