IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1103.4483.html
   My bibliography  Save this paper

A method for pricing American options using semi-infinite linear programming

Author

Listed:
  • Soren Christensen

Abstract

We introduce a new approach for the numerical pricing of American options. The main idea is to choose a finite number of suitable excessive functions (randomly) and to find the smallest majorant of the gain function in the span of these functions. The resulting problem is a linear semi-infinite programming problem, that can be solved using standard algorithms. This leads to good upper bounds for the original problem. For our algorithms no discretization of space and time and no simulation is necessary. Furthermore it is applicable even for high-dimensional problems. The algorithm provides an approximation of the value not only for one starting point, but for the complete value function on the continuation set, so that the optimal exercise region and e.g. the Greeks can be calculated. We apply the algorithm to (one- and) multidimensional diffusions and to L\'evy processes, and show it to be fast and accurate.

Suggested Citation

  • Soren Christensen, 2011. "A method for pricing American options using semi-infinite linear programming," Papers 1103.4483, arXiv.org, revised Jun 2011.
    • Handle: RePEc:arx:papers:1103.4483
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1103.4483
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Alexander Novikov & Albert Shiryaev, 2006. "On a Solution of the Optimal Stopping Problem for Processes with Independent Increments," Research Paper Series 178, Quantitative Finance Research Centre, University of Technology, Sydney.
    2. Martin Lauko & Daniel Sevcovic, 2010. "Comparison of numerical and analytical approximations of the early exercise boundary of the American put option," Papers 1002.0979, arXiv.org, revised Aug 2010.
    3. S. Y. Wu & S. C. Fang & C. J. Lin, 1998. "Relaxed Cutting Plane Method for Solving Linear Semi-Infinite Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 99(3), pages 759-779, December.
    4. Ernesto Mordecki, 2002. "Optimal stopping and perpetual options for Lévy processes," Finance and Stochastics, Springer, vol. 6(4), pages 473-493.
    5. L. C. G. Rogers, 2002. "Monte Carlo valuation of American options," Mathematical Finance, Wiley Blackwell, vol. 12(3), pages 271-286, July.
    6. Christensen, Sören & Irle, Albrecht, 2009. "A note on pasting conditions for the American perpetual optimal stopping problem," Statistics & Probability Letters, Elsevier, vol. 79(3), pages 349-353, February.
    7. Dayanik, Savas & Karatzas, Ioannis, 2003. "On the optimal stopping problem for one-dimensional diffusions," Stochastic Processes and their Applications, Elsevier, vol. 107(2), pages 173-212, October.
    8. Mucci, A. G., 1978. "Existence and explicit determination of optimal stopping times," Stochastic Processes and their Applications, Elsevier, vol. 8(1), pages 33-58, November.
    9. Alexander Novikov & Albert Shiryaev, 2004. "On an Effective Solution of the Optimal Stopping Problem for Random Walks," Research Paper Series 131, Quantitative Finance Research Centre, University of Technology, Sydney.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Soren Christensen, 2011. "Optimal decision under ambiguity for diffusion processes," Papers 1110.3897, arXiv.org, revised Oct 2012.

    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. Christensen, Sören & Salminen, Paavo & Ta, Bao Quoc, 2013. "Optimal stopping of strong Markov processes," Stochastic Processes and their Applications, Elsevier, vol. 123(3), pages 1138-1159.
    2. Christensen, Sören, 2014. "On the solution of general impulse control problems using superharmonic functions," Stochastic Processes and their Applications, Elsevier, vol. 124(1), pages 709-729.
    3. Sören Christensen, 2014. "A Method For Pricing American Options Using Semi-Infinite Linear Programming," Mathematical Finance, Wiley Blackwell, vol. 24(1), pages 156-172, January.
    4. Boyarchenko, Svetlana & Levendorskii, Sergei, 2010. "Optimal stopping in Levy models, for non-monotone discontinuous payoffs," MPRA Paper 27999, University Library of Munich, Germany.
    5. Zbigniew Palmowski & Jos'e Luis P'erez & Kazutoshi Yamazaki, 2020. "Double continuation regions for American options under Poisson exercise opportunities," Papers 2004.03330, arXiv.org.
    6. Jukka Lempa, 2008. "On infinite horizon optimal stopping of general random walk," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 67(2), pages 257-268, April.
    7. Alexander Novikov & Albert Shiryaev, 2006. "On a Solution of the Optimal Stopping Problem for Processes with Independent Increments," Research Paper Series 178, Quantitative Finance Research Centre, University of Technology, Sydney.
    8. S. G. Kou & Hui Wang, 2004. "Option Pricing Under a Double Exponential Jump Diffusion Model," Management Science, INFORMS, vol. 50(9), pages 1178-1192, September.
    9. Ming-Chi Chang & Yuan-Chung Sheu, 2013. "Free boundary problems and perpetual American strangles," Quantitative Finance, Taylor & Francis Journals, vol. 13(8), pages 1149-1155, July.
    10. Jaap H. Abbring, 2012. "Mixed Hitting‐Time Models," Econometrica, Econometric Society, vol. 80(2), pages 783-819, March.
    11. Carolyn E. Phelan & Daniele Marazzina & Guido Germano, 2021. "Pricing methods for $\alpha$-quantile and perpetual early exercise options based on Spitzer identities," Papers 2106.06030, arXiv.org.
    12. Denis Belomestny & Pavel V. Gapeev, 2006. "An Iteration Procedure for Solving Integral Equations Related to Optimal Stopping Problems," SFB 649 Discussion Papers SFB649DP2006-043, Sonderforschungsbereich 649, Humboldt University, Berlin, Germany.
    13. Gapeev Pavel V. & Rodosthenous Neofytos, 2013. "Perpetual American options in a diffusion model with piecewise-linear coefficients," Statistics & Risk Modeling, De Gruyter, vol. 30(1), pages 1-21, March.
    14. Thomas J. Sargent & John Stachurski, 2024. "Dynamic Programming: Finite States," Papers 2401.10473, arXiv.org.
    15. Volker Krätschmer & Marcel Ladkau & Roger J. A. Laeven & John G. M. Schoenmakers & Mitja Stadje, 2018. "Optimal Stopping Under Uncertainty in Drift and Jump Intensity," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1177-1209, November.
    16. Mingsi Long & Hongzhong Zhang, 2017. "On the optimality of threshold type strategies in single and recursive optimal stopping under L\'evy models," Papers 1707.07797, arXiv.org, revised Aug 2018.
    17. Fabian Dickmann & Nikolaus Schweizer, 2014. "Faster Comparison of Stopping Times by Nested Conditional Monte Carlo," Papers 1402.0243, arXiv.org.
    18. Erhan Bayraktar & Masahiko Egami, 2008. "An Analysis of Monotone Follower Problems for Diffusion Processes," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 336-350, May.
    19. Neofytos Rodosthenous & Hongzhong Zhang, 2020. "When to sell an asset amid anxiety about drawdowns," Mathematical Finance, Wiley Blackwell, vol. 30(4), pages 1422-1460, October.
    20. Hongzhong Zhang, 2018. "Stochastic Drawdowns," World Scientific Books, World Scientific Publishing Co. Pte. Ltd., number 10078, January.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:1103.4483. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.