IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i3p1454-1480.html

Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization

Author

Listed:
  • Denis Belomestny

    (Department of Mathematics, University of Duisburg-Essen, 47057 Duisburg, Germany)

  • Christian Bender

    (Department of Mathematics, Saarland University, 66123 Saarbrücken, Germany)

  • John Schoenmakers

    (Weierstrass Institute for Applied Analysis and Stochastics, 10117 Berlin, Germany)

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.

Suggested Citation

  • Denis Belomestny & Christian Bender & John Schoenmakers, 2023. "Solving Optimal Stopping Problems via Randomization and Empirical Dual Optimization," Mathematics of Operations Research, INFORMS, vol. 48(3), pages 1454-1480, August.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:3:p:1454-1480
    DOI: 10.1287/moor.2022.1306
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1306
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1306?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Longstaff, Francis A & Schwartz, Eduardo S, 2001. "Valuing American Options by Simulation: A Simple Least-Squares Approach," The Review of Financial Studies, Society for Financial Studies, vol. 14(1), pages 113-147.
    2. Richard Nickl & Benedikt M. Pötscher, 2007. "Bracketing Metric Entropy Rates and Empirical Central Limit Theorems for Function Classes of Besov- and Sobolev-Type," Journal of Theoretical Probability, Springer, vol. 20(2), pages 177-199, June.
    3. Denis Belomestny & Christian Bender & John Schoenmakers, 2009. "True Upper Bounds For Bermudan Products Via Non‐Nested Monte Carlo," Mathematical Finance, Wiley Blackwell, vol. 19(1), pages 53-71, January.
    4. Denis Belomestny & John Schoenmakers, 2018. "Advanced Simulation-Based Methods for Optimal Stopping and Control," Palgrave Macmillan Books, Palgrave Macmillan, number 978-1-137-03351-2, June.
    5. Mark Broadie & Menghui Cao, 2008. "Improved lower and upper bound algorithms for pricing American options by simulation," Quantitative Finance, Taylor & Francis Journals, vol. 8(8), pages 845-861.
    6. David B. Brown & James E. Smith & Peng Sun, 2010. "Information Relaxations and Duality in Stochastic Dynamic Programs," Operations Research, INFORMS, vol. 58(4-part-1), pages 785-801, August.
    7. Martin B. Haugh & Leonid Kogan, 2004. "Pricing American Options: A Duality Approach," Operations Research, INFORMS, vol. 52(2), pages 258-270, April.
    8. Jérôme Lelong, 2018. "Dual pricing of American options by Wiener chaos expansion," Post-Print hal-01299819, HAL.
    9. Denis Belomestny & John Schoenmakers, 2021. "From optimal martingales to randomized dual optimal stopping," Papers 2102.01533, arXiv.org.
    10. Mark Joshi & Jochen Theis, 2002. "Bounding Bermudan swaptions in a swap-rate market model," Quantitative Finance, Taylor & Francis Journals, vol. 2(5), pages 370-377.
    11. L. C. G. Rogers, 2002. "Monte Carlo valuation of American options," Mathematical Finance, Wiley Blackwell, vol. 12(3), pages 271-286, July.
    12. Vijay V. Desai & Vivek F. Farias & Ciamac C. Moallemi, 2012. "Pathwise Optimization for Optimal Stopping Problems," Management Science, INFORMS, vol. 58(12), pages 2292-2308, December.
    13. Longstaff, Francis A & Schwartz, Eduardo S, 2001. "Valuing American Options by Simulation: A Simple Least-Squares Approach," University of California at Los Angeles, Anderson Graduate School of Management qt43n1k4jb, Anderson Graduate School of Management, UCLA.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Vijay V. Desai & Vivek F. Farias & Ciamac C. Moallemi, 2012. "Pathwise Optimization for Optimal Stopping Problems," Management Science, INFORMS, vol. 58(12), pages 2292-2308, December.
    2. Joshi, Mark & Tang, Robert, 2014. "Effective sub-simulation-free upper bounds for the Monte Carlo pricing of callable derivatives and various improvements to existing methodologies," Journal of Economic Dynamics and Control, Elsevier, vol. 40(C), pages 25-45.
    3. Sebastian Becker & Patrick Cheridito & Arnulf Jentzen & Timo Welti, 2019. "Solving high-dimensional optimal stopping problems using deep learning," Papers 1908.01602, arXiv.org, revised Aug 2021.
    4. Aur'elien Alfonsi & Ahmed Kebaier & J'er^ome Lelong, 2026. "How can the dual martingale help solving the primal optimal stopping problem?," Papers 2602.09950, arXiv.org.
    5. Helin Zhu & Fan Ye & Enlu Zhou, 2013. "Fast Estimation of True Bounds on Bermudan Option Prices under Jump-diffusion Processes," Papers 1305.4321, arXiv.org.
    6. Jérôme Lelong, 2019. "Pricing path-dependent Bermudan options using Wiener chaos expansion: an embarrassingly parallel approach," Working Papers hal-01983115, HAL.
    7. Helin Zhu & Fan Ye & Enlu Zhou, 2015. "Fast estimation of true bounds on Bermudan option prices under jump-diffusion processes," Quantitative Finance, Taylor & Francis Journals, vol. 15(11), pages 1885-1900, November.
    8. Denis Belomestny & John Schoenmakers, 2021. "From optimal martingales to randomized dual optimal stopping," Papers 2102.01533, arXiv.org.
    9. J'er^ome Lelong, 2019. "Pricing path-dependent Bermudan options using Wiener chaos expansion: an embarrassingly parallel approach," Papers 1901.05672, arXiv.org, revised Jul 2020.
    10. Roger J. A. Laeven & John G. M. Schoenmakers & Nikolaus Schweizer & Mitja Stadje, 2025. "Robust Multiple Stopping—A Duality Approach," Mathematics of Operations Research, INFORMS, vol. 50(2), pages 1250-1276, May.
    11. Christian Bender & Christian Gaertner & Nikolaus Schweizer, 2016. "Pathwise Iteration for Backward SDEs," Papers 1605.07500, arXiv.org, revised Jun 2016.
    12. Maximilian Mair & Jan Maruhn, 2013. "On the primal-dual algorithm for callable Bermudan options," Review of Derivatives Research, Springer, vol. 16(1), pages 79-110, April.
    13. Denis Belomestny & John Schoenmakers & Fabian Dickmann, 2013. "Multilevel dual approach for pricing American style derivatives," Finance and Stochastics, Springer, vol. 17(4), pages 717-742, October.
    14. Jiefei Yang & Guanglian Li, 2024. "A deep primal-dual BSDE method for optimal stopping problems," Papers 2409.06937, arXiv.org.
    15. Bradley Sturt, 2023. "A Nonparametric Algorithm for Optimal Stopping Based on Robust Optimization," Operations Research, INFORMS, vol. 71(5), pages 1530-1557, September.
    16. Jérôme Lelong, 2018. "Dual pricing of American options by Wiener chaos expansion," Post-Print hal-01299819, HAL.
    17. Secomandi, Nicola & Seppi, Duane J., 2014. "Real Options and Merchant Operations of Energy and Other Commodities," Foundations and Trends(R) in Technology, Information and Operations Management, now publishers, vol. 6(3-4), pages 161-331, July.
    18. David A. Goldberg & Yilun Chen, 2018. "Polynomial time algorithm for optimal stopping with fixed accuracy," Papers 1807.02227, arXiv.org, revised May 2024.
    19. Cosma, Antonio & Galluccio, Stefano & Scaillet, Olivier, 2012. "Valuing American options using fast recursive projections," Working Papers unige:41856, University of Geneva, Geneva School of Economics and Management.
    20. Sebastian Becker & Patrick Cheridito & Arnulf Jentzen, 2020. "Pricing and Hedging American-Style Options with Deep Learning," JRFM, MDPI, vol. 13(7), pages 1-12, July.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:48:y:2023:i:3:p:1454-1480. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.