Primal-dual methods for dynamic programming equations arising in non-linear option pricing

Abstract

When discretizing non-linear pricing problems, one ends up with stochastic dynamic programs which often possess a concave-convex structure. The key challenge in solving these dynamic programs numerically is the high-order nesting of conditional expectations. In practice, these conditional expectations have to be replaced by some approximation operator, which can be nested several times without leading to exploding computational costs. In the first part of this thesis, we provide a posteriori criteria for validating approximate solutions to such dynamic programs. To this end, we rely on a primal-dual approach, which takes an approximate solution of the dynamic program as an input and allows the computation of upper and lower bounds to the true solution. The approach proposed here unifies and extends existing results and applies regardless of whether a comparison principle holds or not. The second part of this thesis establishes an iterative improvement approach for upper and lower bounds in the special case of convex dynamic programs. This approach allows the computation of tight confidence intervals for the true solution, even if the input upper and lower bounds stem from a possibly crude approximate solution to the dynamic program. The applicability of the presented approaches is demonstrated in various numerical examples.

Die Diskretisierung nicht linearer Preisprobleme führt typischerweise zu stochastischen dynamischen Programmen, die eine konkav-konvexe Struktur aufweisen. Möchte man solche dynamischen Programme numerisch lösen, stellen die hochgradig verschachtelten bedingten Erwartungen die größte Herausforderung dar. In Anwendungen müssen diese bedingten Erwartungen mit Hilfe eines geeigneten Operators approximiert werden, der mehrfach angewendet werden kann, ohne zu explodierenden Rechenkosten zu führen. Im ersten Teil dieser Arbeit stellen wir Kriterien zur nachträglichen Validierung approximativer Lösungen solcher dynamischer Programme bereit. Dazu stützen wir uns auf einen primal-dualen Ansatz, der ausgehend von einer approximativen Lösung des dynamischen Programms die Konstruktion oberer und unterer Schranken an die wahre Lösung ermöglicht. Der hier vorgeschlagene Ansatz vereinheitlicht und verallgemeinert bisher bekannte Resultate und kann ungeachtet der Existenz eines Vergleichsprinzips genutzt werden. Der zweite Teil der Arbeit befasst sich mit einem iterativen Ansatz zur Verbesserung oberer und unterer Schranken im Spezialfall konvexer dynamischer Programme. Dieser Ansatz erlaubt die Konstruktion enger Konfidenzintervalle an die wahre Lösung, selbst wenn die gegebenen Schranken auf einer möglicherweise groben approximativen Lösung des dynamischen Programms beruhen. In verschiedenen numerischen Beispielen demonstrieren wir die Anwendbarkeit der vorgeschlagenen Ansätze.