High-Dimensional Regression on Sparse Grids Applied to Pricing Moving Window Asian Options
ABSTRACT
The pricing of moving window Asian option with an early exercise feature is considered a challenging problem in option pricing. The computational challenge lies in the unknown optimal exercise strategy and in the high dimensionality required for approximating the early exercise boundary. We use sparse grid basis functions in the Least Squares Monte Carlo approach to solve this “curse of dimensionality” problem. The resulting algorithm provides a general and convergent method for pricing moving window Asian options. The sparse grid technique presented in this paper can be generalized to pricing other high-dimensional, early-exercisable derivatives.
Cite this paper
S. Dirnstorfer, A. Grau and R. Zagst, "High-Dimensional Regression on Sparse Grids Applied to Pricing Moving Window Asian Options," Open Journal of Statistics, Vol. 3 No. 6, 2013, pp. 427-440. doi: 10.4236/ojs.2013.36051.
S. Dirnstorfer, A. Grau and R. Zagst, "High-Dimensional Regression on Sparse Grids Applied to Pricing Moving Window Asian Options," Open Journal of Statistics, Vol. 3 No. 6, 2013, pp. 427-440. doi: 10.4236/ojs.2013.36051.
References
[1] S. Achatz, “Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients,” Computing, Vol. 71, No. 1, 2003, pp. 1-15.
http://dx.doi.org/10.1007/s00607-003-0012-8 [2] V. Bathelmann, E. Novak and K. Ritter, “High Dimensional Polynomial Interpolation on Sparse Grids,” Advances in Compuational Mathematics, Vol. 12, No. 4, 2000, pp. 273-288.
http://dx.doi.org/10.1023/A:1018977404843 [3] M. Bernhart, P. Tankov and X. Warin, “A Finite Dimensional Approximation for Pricing Moving Average Options,” Journal on Financial Mathematics, Vol. 2, No. 1, 2011, pp. 989-1013.
http://dx.doi.org/10.1137/100815566 [4] R. Bilger, “Valuing American-Asian Options Using the Longstaff-Schwartz Algorithm,” Msc Thesis in Computational Finance, Oxford University, Oxford, 2003. [5] F. Black and M. Scholes, “The Pricing Of Options and Corporate Liabilities,” Journal on Political Economy, Vol. 81, No. 3, 1973, pp. 637-659.
http://dx.doi.org/10.1086/260062 [6] T. Bonk, “A New Algorithm for Multi-Dimensional Adaptic Numerical Quadrature,” In: W. Hackbush, Ed., Adaptive Methods—Algorithms, Theory and Applications, Notes on Numerical Fluid Mechanics, Vieweg + Teubner, Braunschweig, 1994, pp. 54-68. [7] M. Broadie and M. Cao, “Improved Lower and Upper Bound Algorithms for Pricing American Options by Simulation,” Quantitative Finance, Vol. 8, No. 8, 2008, pp. 845-861.
http://dx.doi.org/10.1080/14697680701763086 [8] H.-J. Bungartz, “A Multigrid Algorithm for Higher Order Finite Elements on Sparse Grid,” Electronic Transactions on Numerical Analysis, Vol. 6, 1997, pp. 63-77. [9] J. F. Carriere, “Valuation of the Early-Exercise Price for Options Using Simulations and Nonparametric Regression,” Insurance: Mathematics and Economics, Vol. 19, No. 1, 1996, pp. 19-30.
http://dx.doi.org/10.1016/S0167-6687(96)00004-2 [10] M. Dai, P. Li and J. E. Zhang, “A Lattice Algorithm for Pricing Moving Average Barrier Options,” Journal of Economic Dynamics and Control, Vol. 34, No. 3, 2010, pp. 542-554.
http://dx.doi.org/10.1016/j.jedc.2009.10.008 [11] S. Dirnstorfer, A. J. Grau and H. Li, “ThetaML Handbook,” edition winterwork, 2012. [12] S. Dirnstorfer and A. J. Grau, “Computer Aided Finance: Another Journey in the Quest for the Holy Grail of Financial Engineering,” WILMOTT Magazine, 2008, pp. 68-73. [13] J. Garcke, M. Griebel and M. Thess, “Data Mining with Sparse Grids,” Computing, Vol. 67, No. 3, 2001, pp. 225253. http://dx.doi.org/10.1007/s006070170007 [14] K. Hallatschek, “Fouriertransformation auf Dünnen Gittern mit Hierarchischen Basen,” Numerische Mathematik, Vol. 63, No. 1, 1992, pp. 83-97.
http://dx.doi.org/10.1007/BF01385849 [15] C.-H. Kao and Y.-D. Lyuu, “Pricing of Moving AverageType Options with Applications,” Journal of Futures Markets, Vol. 23, No. 5, 2003, pp. 415-440.
http://dx.doi.org/10.1002/fut.10072 [16] A. Klimke and B. Wohlmuth, “Algorithm 847: Spinterp: Piecewise Multilinear Hierarchical Sparse Grid Interpolation in Matlab,” ACM Transactions on Mathematical Software, Vol. 31, No. 4, 2005, pp. 561-579.
http://dx.doi.org/10.1145/1114268.1114275 [17] F. A. Longstaff and E. S. Schwartz, “Valuing American Options by Simulation—A Simple Least-Squares Approach,” The Review of Financial Studies, Vol. 14, No. 1, 2001, pp. 113-147.
http://dx.doi.org/10.1093/rfs/14.1.113 [18] B. D. Martin, “Radial Basis Functions: Theory and Implementations,” Cambridge University Press, Cambridge, 2003. [19] M. Griebel, P. Oswald and T. Schiekoffer, “Sparse Grids for Boundary Integral Equations,” Numerische Mathematik, Vol. 83, No. 2, 1999, pp. 279-312.
http://dx.doi.org/10.1007/s002110050450 [20] B. Nicolas, “Elements of Mathematics, Algebra I,” SpringerVerlag, Berlin, 1989. [21] C. Reisinger, “Numerische Methoden für Hochdimensionale Parabolische Gleichungen am Beispiel von Optionspreisaufgaben,” Dissertation, Ruprecht-Karls-Universitat, Heidelberg, 2004. [22] S. Schraufstetter, “A Pricing Framework for the Efficient Evaluation of Financial Derivatives Based on Theta Calculus and Adaptive Sparse Grids,” Dr. Hut, 2012. [23] S. A. Smolyak, “Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,” Doklady Akademii Nauk SSSR, Vol. 148, 1963, pp. 10421043. English Russian Translation: Soviet Mathematics Doklady, Vol. 4, 1963, pp. 240-243. [24] C. Zenger, “Sparse Grids,” In: W. Hackbusch, Ed., Notes on Numerical Fluid Mechanics, Vol. 31, Vieweg, Braunschweig, 1991, 1990, pp. 241-251.
[1] S. Achatz, “Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients,” Computing, Vol. 71, No. 1, 2003, pp. 1-15.
http://dx.doi.org/10.1007/s00607-003-0012-8 [2] V. Bathelmann, E. Novak and K. Ritter, “High Dimensional Polynomial Interpolation on Sparse Grids,” Advances in Compuational Mathematics, Vol. 12, No. 4, 2000, pp. 273-288.
http://dx.doi.org/10.1023/A:1018977404843 [3] M. Bernhart, P. Tankov and X. Warin, “A Finite Dimensional Approximation for Pricing Moving Average Options,” Journal on Financial Mathematics, Vol. 2, No. 1, 2011, pp. 989-1013.
http://dx.doi.org/10.1137/100815566 [4] R. Bilger, “Valuing American-Asian Options Using the Longstaff-Schwartz Algorithm,” Msc Thesis in Computational Finance, Oxford University, Oxford, 2003. [5] F. Black and M. Scholes, “The Pricing Of Options and Corporate Liabilities,” Journal on Political Economy, Vol. 81, No. 3, 1973, pp. 637-659.
http://dx.doi.org/10.1086/260062 [6] T. Bonk, “A New Algorithm for Multi-Dimensional Adaptic Numerical Quadrature,” In: W. Hackbush, Ed., Adaptive Methods—Algorithms, Theory and Applications, Notes on Numerical Fluid Mechanics, Vieweg + Teubner, Braunschweig, 1994, pp. 54-68. [7] M. Broadie and M. Cao, “Improved Lower and Upper Bound Algorithms for Pricing American Options by Simulation,” Quantitative Finance, Vol. 8, No. 8, 2008, pp. 845-861.
http://dx.doi.org/10.1080/14697680701763086 [8] H.-J. Bungartz, “A Multigrid Algorithm for Higher Order Finite Elements on Sparse Grid,” Electronic Transactions on Numerical Analysis, Vol. 6, 1997, pp. 63-77. [9] J. F. Carriere, “Valuation of the Early-Exercise Price for Options Using Simulations and Nonparametric Regression,” Insurance: Mathematics and Economics, Vol. 19, No. 1, 1996, pp. 19-30.
http://dx.doi.org/10.1016/S0167-6687(96)00004-2 [10] M. Dai, P. Li and J. E. Zhang, “A Lattice Algorithm for Pricing Moving Average Barrier Options,” Journal of Economic Dynamics and Control, Vol. 34, No. 3, 2010, pp. 542-554.
http://dx.doi.org/10.1016/j.jedc.2009.10.008 [11] S. Dirnstorfer, A. J. Grau and H. Li, “ThetaML Handbook,” edition winterwork, 2012. [12] S. Dirnstorfer and A. J. Grau, “Computer Aided Finance: Another Journey in the Quest for the Holy Grail of Financial Engineering,” WILMOTT Magazine, 2008, pp. 68-73. [13] J. Garcke, M. Griebel and M. Thess, “Data Mining with Sparse Grids,” Computing, Vol. 67, No. 3, 2001, pp. 225253. http://dx.doi.org/10.1007/s006070170007 [14] K. Hallatschek, “Fouriertransformation auf Dünnen Gittern mit Hierarchischen Basen,” Numerische Mathematik, Vol. 63, No. 1, 1992, pp. 83-97.
http://dx.doi.org/10.1007/BF01385849 [15] C.-H. Kao and Y.-D. Lyuu, “Pricing of Moving AverageType Options with Applications,” Journal of Futures Markets, Vol. 23, No. 5, 2003, pp. 415-440.
http://dx.doi.org/10.1002/fut.10072 [16] A. Klimke and B. Wohlmuth, “Algorithm 847: Spinterp: Piecewise Multilinear Hierarchical Sparse Grid Interpolation in Matlab,” ACM Transactions on Mathematical Software, Vol. 31, No. 4, 2005, pp. 561-579.
http://dx.doi.org/10.1145/1114268.1114275 [17] F. A. Longstaff and E. S. Schwartz, “Valuing American Options by Simulation—A Simple Least-Squares Approach,” The Review of Financial Studies, Vol. 14, No. 1, 2001, pp. 113-147.
http://dx.doi.org/10.1093/rfs/14.1.113 [18] B. D. Martin, “Radial Basis Functions: Theory and Implementations,” Cambridge University Press, Cambridge, 2003. [19] M. Griebel, P. Oswald and T. Schiekoffer, “Sparse Grids for Boundary Integral Equations,” Numerische Mathematik, Vol. 83, No. 2, 1999, pp. 279-312.
http://dx.doi.org/10.1007/s002110050450 [20] B. Nicolas, “Elements of Mathematics, Algebra I,” SpringerVerlag, Berlin, 1989. [21] C. Reisinger, “Numerische Methoden für Hochdimensionale Parabolische Gleichungen am Beispiel von Optionspreisaufgaben,” Dissertation, Ruprecht-Karls-Universitat, Heidelberg, 2004. [22] S. Schraufstetter, “A Pricing Framework for the Efficient Evaluation of Financial Derivatives Based on Theta Calculus and Adaptive Sparse Grids,” Dr. Hut, 2012. [23] S. A. Smolyak, “Quadrature and Interpolation Formulas for Tensor Products of Certain Classes of Functions,” Doklady Akademii Nauk SSSR, Vol. 148, 1963, pp. 10421043. English Russian Translation: Soviet Mathematics Doklady, Vol. 4, 1963, pp. 240-243. [24] C. Zenger, “Sparse Grids,” In: W. Hackbusch, Ed., Notes on Numerical Fluid Mechanics, Vol. 31, Vieweg, Braunschweig, 1991, 1990, pp. 241-251.