An effective algorithm to solve option pricing problems

Moradipour, Mojtaba

doi:10.22075/ijnaa.2021.4782

An effective algorithm to solve option pricing problems

Document Type : Research Paper

Author

Mojtaba Moradipour

Department of Mathematics‎, ‎Lorestan University‎, ‎Khorramabad‎, ‎Iran‎‎

10.22075/ijnaa.2021.4782

Abstract

‎We are aimed to develop a fast and direct algorithm to solve linear‎ complementarity problems (LCP's) arising from option pricing problems‎. We discretize the free boundary problem of American options in temporal direction and obtain a sequence of linear complementarity problems (LCP's) in the finite dimensional Euclidian space $\mathbb{R}^m$‎. ‎We develop a fast and direct algorithm based on the active set strategy to solve the LCP's‎. The active set strategy in general needs $O(2^m m^3)$ operations to solve $m$ dimensional LCP's‎. ‎Using Thomas algorithm‎, ‎we develop an algorithm with order of complexity $O(m)$ which can extremely speed up the computations‎.

Keywords

20.1001.1.20086822.2021.12.1.21.6

References

[1] R.W. Cottle, J.S. Pang and R.E. Stone, The Linear Complementarity Problem, Society for Industrial and Applied Mathematics, 2009.

[2] J. Crank, Free and Moving Boundary Problems, Oxford Science Publications, Clarendon Press, 1984.

[3] D.J. Duffy, Finite Difference Methods in Financial Engineering, Wiley Finance Series, John Wiley & Sons, Ltd., Chichester, 2006.

[4] M.B. Giles and R. Carter, Convergence analysis of Crank-Nicholson and Rannacher time-marching, J. Comput. Finance 9 (2006) 89–112.

[5] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Scientific Computation, Springer Berlin Heidelberg, 2013.

[6] P. Hartman and G. Stampacchia, On some non-linear elliptic differential-functional equations, Acta Math. 115(1) (1966) 271–310.

[7] A.D. Holmes, A Front-Fixing Finite Element Method for the Valuation of American Options, PhD thesis, University of Nevada, Las Vegas, 2010.

[8] S. Ikonen and J. Toivanen, Pricing American options using LU decomposition, Appl. Math. Sci. (Ruse) 1(49-52) (2007) 2529–2551.

[9] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.

[10] M. Moradipour and S.A. Yousefi, Using spectral element method to solve variational inequalities with applications in finance, Chaos, Solitons Fractals 81 (2015) 208–217.

[11] J.L. Morales, J. Nocedal and M. Smelyanskiy, An algorithm for the fast solution of symmetric linear complementarity problems, Numer. Math. 111(2) (2008) 251–266.

[12] R. Rannacher, Finite element solution of diffusion problems with irregular data, Numerische Math. 43(2) (1984) 309–327.

[13] R.U. Seydel, Tools for Computational Finance, Universitext Springer-Verlag, Berlin, Fourth Edition, 2009.

[14] J. Toivanen, Numerical valuation of European and American options under Kou’s jump-diffusion model, SIAM J. Sci. Comput. 30(4) (2008) 1949–1970.