Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization. Belomestny, D., Bender, C., & Schoenmakers, J. Mathematics of Operations Research, 0(0):null, 0. Paper doi abstract bibtex In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem can be reformulated as a problem of stochastic average approximation (SAA) that 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 compared with the nonrandomized procedure. We illustrate the performance of our algorithm on several benchmark examples.
@article{doi:10.1287/moor.2022.1306,
author = {Belomestny, Denis and Bender, Christian and Schoenmakers, John},
title = {Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization},
journal = {Mathematics of Operations Research},
volume = {0},
number = {0},
pages = {null},
year = {0},
doi = {10.1287/moor.2022.1306},
URL = {https://doi.org/10.1287/moor.2022.1306},
eprint = {https://doi.org/10.1287/moor.2022.1306},
abstract = { In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem
can be reformulated as a problem of stochastic average approximation (SAA) that 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 compared with the nonrandomized procedure. We illustrate the performance
of our algorithm on several benchmark examples. }
}
Downloads: 0
{"_id":"3xdjK9DKCMmWNqADd","bibbaseid":"belomestny-bender-schoenmakers-solvingoptimalstoppingproblemsviarandomizationandempiricaldualoptimization-0","author_short":["Belomestny, D.","Bender, C.","Schoenmakers, J."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Belomestny"],"firstnames":["Denis"],"suffixes":[]},{"propositions":[],"lastnames":["Bender"],"firstnames":["Christian"],"suffixes":[]},{"propositions":[],"lastnames":["Schoenmakers"],"firstnames":["John"],"suffixes":[]}],"title":"Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization","journal":"Mathematics of Operations Research","volume":"0","number":"0","pages":"null","year":"0","doi":"10.1287/moor.2022.1306","url":"https://doi.org/10.1287/moor.2022.1306","eprint":"https://doi.org/10.1287/moor.2022.1306","abstract":"In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem can be reformulated as a problem of stochastic average approximation (SAA) that 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 compared with the nonrandomized procedure. We illustrate the performance of our algorithm on several benchmark examples. ","bibtex":"@article{doi:10.1287/moor.2022.1306,\nauthor = {Belomestny, Denis and Bender, Christian and Schoenmakers, John},\ntitle = {Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization},\njournal = {Mathematics of Operations Research},\nvolume = {0},\nnumber = {0},\npages = {null},\nyear = {0},\ndoi = {10.1287/moor.2022.1306},\nURL = {https://doi.org/10.1287/moor.2022.1306},\neprint = {https://doi.org/10.1287/moor.2022.1306},\nabstract = { In this paper, we consider optimal stopping problems in their dual form. In this way, the optimal stopping problem \ncan be reformulated as a problem of stochastic average approximation (SAA) that can be solved via linear programming. \nBy randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear \nprogramming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties \nsuch as faster convergence rates and reduced complexity compared with the nonrandomized procedure. We illustrate the performance \nof our algorithm on several benchmark examples. }\n}\n\n\n\n","author_short":["Belomestny, D.","Bender, C.","Schoenmakers, J."],"key":"doi:10.1287/moor.2022.1306","id":"doi:10.1287/moor.2022.1306","bibbaseid":"belomestny-bender-schoenmakers-solvingoptimalstoppingproblemsviarandomizationandempiricaldualoptimization-0","role":"author","urls":{"Paper":"https://doi.org/10.1287/moor.2022.1306"},"metadata":{"authorlinks":{}},"html":""},"bibtype":"article","biburl":"https://denbel.github.io/pubdata.bib","dataSources":["cbSQWShtd2dER8vAa"],"keywords":[],"search_terms":["solving","optimal","stopping","problems","via","randomization","empirical","dual","optimization","belomestny","bender","schoenmakers"],"title":"Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization","year":0}