Solving stochastic dynamic programs by convex optimization and simulation

Denis Belomestny, Christian Bender, Fabian Dickmann, Nikolaus Schweizer

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

Abstract

In this chapter we review some recent progress on Monte Carlo methods for a class of stochastic dynamic programming equations, which accommodates optimal stopping problems and time discretization schemes for backward stochastic differential equations with convex generators. We first provide a primal maximization problem and a dual minimization problem, based on which confidence intervals for the value of the dynamic program can be constructed by Monte Carlo simulation. For the computation of the lower confidence bounds we apply martingale basis functions within a least-squares Monte Carlo implementation. For the upper confidence bounds we suggest a multilevel simulation within a nested Monte Carlo approach and, alternatively, a generic sieve optimization approach with a variance penalty term.
Original languageEnglish
Title of host publicationExtraction of Quantifiable Information from Complex Systems
EditorsT.J. Barth, M. Griebel, D.E. Keyes, R.M. Nieminen, D. Roose, T. Schlick
Place of PublicationCham
PublisherSpringer International Publishing AG
Pages1-23
ISBN (Print)9783319081588
DOIs
Publication statusPublished - 30 Sep 2014
Externally publishedYes

Publication series

NameLecture Notes in Computational Science and Engineering
Volume102

Fingerprint

Confidence Bounds
Stochastic Dynamics
Convex Optimization
Optimal Stopping Time
Stochastic Dynamic Programming
Optimal Stopping Problem
Backward Stochastic Differential Equation
Sieve
Discretization Scheme
Dual Problem
Time Discretization
Martingale
Minimization Problem
Monte Carlo method
Confidence interval
Basis Functions
Least Squares
Penalty
Simulation
Monte Carlo Simulation

Cite this

Belomestny, D., Bender, C., Dickmann, F., & Schweizer, N. (2014). Solving stochastic dynamic programs by convex optimization and simulation. In T. J. Barth, M. Griebel, D. E. Keyes, R. M. Nieminen, D. Roose, & T. Schlick (Eds.), Extraction of Quantifiable Information from Complex Systems (pp. 1-23). [Chapter 1] (Lecture Notes in Computational Science and Engineering; Vol. 102). Cham: Springer International Publishing AG. https://doi.org/10.1007/978-3-319-08159-5_1
Belomestny, Denis ; Bender, Christian ; Dickmann, Fabian ; Schweizer, Nikolaus. / Solving stochastic dynamic programs by convex optimization and simulation. Extraction of Quantifiable Information from Complex Systems. editor / T.J. Barth ; M. Griebel ; D.E. Keyes ; R.M. Nieminen ; D. Roose ; T. Schlick. Cham : Springer International Publishing AG, 2014. pp. 1-23 (Lecture Notes in Computational Science and Engineering).
@inbook{9885e0b48ab34e6a946c4d7587af4c52,
title = "Solving stochastic dynamic programs by convex optimization and simulation",
abstract = "In this chapter we review some recent progress on Monte Carlo methods for a class of stochastic dynamic programming equations, which accommodates optimal stopping problems and time discretization schemes for backward stochastic differential equations with convex generators. We first provide a primal maximization problem and a dual minimization problem, based on which confidence intervals for the value of the dynamic program can be constructed by Monte Carlo simulation. For the computation of the lower confidence bounds we apply martingale basis functions within a least-squares Monte Carlo implementation. For the upper confidence bounds we suggest a multilevel simulation within a nested Monte Carlo approach and, alternatively, a generic sieve optimization approach with a variance penalty term.",
author = "Denis Belomestny and Christian Bender and Fabian Dickmann and Nikolaus Schweizer",
year = "2014",
month = "9",
day = "30",
doi = "10.1007/978-3-319-08159-5_1",
language = "English",
isbn = "9783319081588",
series = "Lecture Notes in Computational Science and Engineering",
publisher = "Springer International Publishing AG",
pages = "1--23",
editor = "T.J. Barth and M. Griebel and D.E. Keyes and R.M. Nieminen and D. Roose and T. Schlick",
booktitle = "Extraction of Quantifiable Information from Complex Systems",
address = "Switzerland",

}

Belomestny, D, Bender, C, Dickmann, F & Schweizer, N 2014, Solving stochastic dynamic programs by convex optimization and simulation. in TJ Barth, M Griebel, DE Keyes, RM Nieminen, D Roose & T Schlick (eds), Extraction of Quantifiable Information from Complex Systems., Chapter 1, Lecture Notes in Computational Science and Engineering, vol. 102, Springer International Publishing AG, Cham, pp. 1-23. https://doi.org/10.1007/978-3-319-08159-5_1

Solving stochastic dynamic programs by convex optimization and simulation. / Belomestny, Denis; Bender, Christian; Dickmann, Fabian; Schweizer, Nikolaus.

Extraction of Quantifiable Information from Complex Systems. ed. / T.J. Barth; M. Griebel; D.E. Keyes; R.M. Nieminen; D. Roose; T. Schlick. Cham : Springer International Publishing AG, 2014. p. 1-23 Chapter 1 (Lecture Notes in Computational Science and Engineering; Vol. 102).

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

TY - CHAP

T1 - Solving stochastic dynamic programs by convex optimization and simulation

AU - Belomestny, Denis

AU - Bender, Christian

AU - Dickmann, Fabian

AU - Schweizer, Nikolaus

PY - 2014/9/30

Y1 - 2014/9/30

N2 - In this chapter we review some recent progress on Monte Carlo methods for a class of stochastic dynamic programming equations, which accommodates optimal stopping problems and time discretization schemes for backward stochastic differential equations with convex generators. We first provide a primal maximization problem and a dual minimization problem, based on which confidence intervals for the value of the dynamic program can be constructed by Monte Carlo simulation. For the computation of the lower confidence bounds we apply martingale basis functions within a least-squares Monte Carlo implementation. For the upper confidence bounds we suggest a multilevel simulation within a nested Monte Carlo approach and, alternatively, a generic sieve optimization approach with a variance penalty term.

AB - In this chapter we review some recent progress on Monte Carlo methods for a class of stochastic dynamic programming equations, which accommodates optimal stopping problems and time discretization schemes for backward stochastic differential equations with convex generators. We first provide a primal maximization problem and a dual minimization problem, based on which confidence intervals for the value of the dynamic program can be constructed by Monte Carlo simulation. For the computation of the lower confidence bounds we apply martingale basis functions within a least-squares Monte Carlo implementation. For the upper confidence bounds we suggest a multilevel simulation within a nested Monte Carlo approach and, alternatively, a generic sieve optimization approach with a variance penalty term.

U2 - 10.1007/978-3-319-08159-5_1

DO - 10.1007/978-3-319-08159-5_1

M3 - Chapter

SN - 9783319081588

T3 - Lecture Notes in Computational Science and Engineering

SP - 1

EP - 23

BT - Extraction of Quantifiable Information from Complex Systems

A2 - Barth, T.J.

A2 - Griebel, M.

A2 - Keyes, D.E.

A2 - Nieminen, R.M.

A2 - Roose, D.

A2 - Schlick, T.

PB - Springer International Publishing AG

CY - Cham

ER -

Belomestny D, Bender C, Dickmann F, Schweizer N. Solving stochastic dynamic programs by convex optimization and simulation. In Barth TJ, Griebel M, Keyes DE, Nieminen RM, Roose D, Schlick T, editors, Extraction of Quantifiable Information from Complex Systems. Cham: Springer International Publishing AG. 2014. p. 1-23. Chapter 1. (Lecture Notes in Computational Science and Engineering). https://doi.org/10.1007/978-3-319-08159-5_1