A numerical method for parabolic complementarity problem

Haiyan Song; Fei Sun; Haiyan Song; Fei Sun

doi:10.3934/era.2023052

Electronic Research Archive

2023, Volume 31, Issue 2: 1048-1064. doi: 10.3934/era.2023052

Previous Article Next Article

Theory article Special Issues

A numerical method for parabolic complementarity problem

Haiyan Song ¹,
Fei Sun ^{2
,
,}

1.
School of Computer and Data Engineering, NingboTech University, Ningbo 315100, China
2.
School of Mathematics and Computational Science, Wuyi University, Jiangmen 529020, China

Received: 06 October 2022 Revised: 24 November 2022 Accepted: 30 November 2022 Published: 13 December 2022

In this paper, we study the numerical solution of a parabolic complementarity problem which is a widely used model in many fields, such as option pricing, risk measures, etc. Using a power penalty method we represent the complementarity problem as a nonlinear parabolic partial differential equation (PDE). Then, we use the trapezoidal rule as the time discretization, for which we have to solve a nonlinear equation at each time step. We solve such a nonlinear equation by the fixed-point iteration and in this methodology solving a tridiagonal linear system is the major computation. We present an efficient backward substitution algorithm to handle this linear system. Numerical results are given to illustrate the advantage of the proposed algorithm (compared to the built-in command backslash in Matlab) in terms of CPU time.
- complementarity problem,
- discretization,
- trapezoidal rule,
- penalty method,
- risk measures
Citation: Haiyan Song, Fei Sun. A numerical method for parabolic complementarity problem[J]. Electronic Research Archive, 2023, 31(2): 1048-1064. doi: 10.3934/era.2023052

Related Papers:

Abstract

In this paper, we study the numerical solution of a parabolic complementarity problem which is a widely used model in many fields, such as option pricing, risk measures, etc. Using a power penalty method we represent the complementarity problem as a nonlinear parabolic partial differential equation (PDE). Then, we use the trapezoidal rule as the time discretization, for which we have to solve a nonlinear equation at each time step. We solve such a nonlinear equation by the fixed-point iteration and in this methodology solving a tridiagonal linear system is the major computation. We present an efficient backward substitution algorithm to handle this linear system. Numerical results are given to illustrate the advantage of the proposed algorithm (compared to the built-in command backslash in Matlab) in terms of CPU time.

References

[1]	L. Angermann, S. Wang, Convergence of a fitted finite volume method for European and American option valuation, Numer. Math., 106 (2007), 1–40. https://doi.org/10.1007/s00211-006-0057-7 doi: 10.1007/s00211-006-0057-7
[2]	A. Bensoussan, J. L. Lions, Applications of Variational Inequalities in Stochastic Control, North-Holland Amsterdam, New York, Oxford, 1978.
[3]	T. B. Gyulov, M. N. Koleva, Penalty method for indifference pricing of American option in a liquidity switching market, Appl. Numer. Math., 172 (2022), 525–545. https://doi.org/10.1016/j.apnum.2021.11.002 doi: 10.1016/j.apnum.2021.11.002
[4]	J. Haslinger, M. Miettinen, Finite Element Method for Hemivariational Inequalities, Kluwer Academic Publisher, 1999. https://doi.org/10.1007/978-1-4757-5233-5
[5]	L. Scurria, D. Fauconnier, P. Jiranek, T. Tamarozzi, A Galerkin/hyper-reduction technique to reduce steady-state elastohydrodynamic line contact problems, Comput. Methods Appl. Mech. Eng., 386 (2021), 114132. https://doi.org/10.1016/j.cma.2021.114132 doi: 10.1016/j.cma.2021.114132
[6]	W. D. Zhao, Numerical methods for forward backward stochastic differential equations, Math. Numer. Sin., 37 (2015), 337–373. https://doi.org/10.12286/jssx.2015.4.337 doi: 10.12286/jssx.2015.4.337
[7]	L. Jiang, Convexity, translation invariance and subadditivity for g-expectations and related risk measures, Ann. Appl. Probab., 18 (2008), 245–258. https://doi.org/10.1214/105051607000000294 doi: 10.1214/105051607000000294
[8]	I. Penner, A. Reveillac, Risk measures for processes and BSDEs, Finance Stochastics, 19 (2015), 23–66. https://doi.org/10.1007/s00780-014-0243-x doi: 10.1007/s00780-014-0243-x
[9]	R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, 1984. https://doi.org/10.1007/978-3-662-12613-4
[10]	S. Wang, X. Q. Yang, K. L. Teo, Power penalty method for a linear complementarity problem arising from American option valuation, J. Optim. Theory Appl., 129 (2006), 227–254. https://doi.org/10.1007/s10957-006-9062-3 doi: 10.1007/s10957-006-9062-3
[11]	S. Wang, C. S. Huang, A power penalty method for solving a nonlinear parabolic complementarity problem, Nonlinear Anal. Theory Methods Appl., 69 (2008), 1125–1137. https://doi.org/10.1016/j.na.2007.06.014 doi: 10.1016/j.na.2007.06.014
[12]	M. Chen, C. Huang, A power penalty method for a class of linearly constrained variational inequality, J. Ind. Manage. Optim., 14 (2018), 1381–1396. https://doi.org/10.3934/jimo.2018012 doi: 10.3934/jimo.2018012
[13]	A. M. Rubinov, X. Q. Yang, Lagrange-type Functions in Constrained Non-convex Optimization, Kluwer Academic Publishers, Dordrecht, Holland, 2003.
[14]	X. Q. Yang, X. X. Huang, Nonlinear lagrangian approach to constrained optimization problems, SIAM J. Optim., 11 (2001), 1119–1144. https://doi.org/10.1137/S1052623400371806 doi: 10.1137/S1052623400371806
[15]	M. H. Holmes, Introduction to Mumerical Methods in Differential Equations, Springer New York, 2009.
[16]	O. T. Hanna, New explicit and implicit "improved Euler" methods for the integration of ordinary differential equations, Comput. Chem. Eng., 12 (1988), 1083–1086. https://doi.org/10.1016/0098-1354(88)87030-3 doi: 10.1016/0098-1354(88)87030-3
[17]	R. Santos, L. Alves, A comparative analysis of explicit, IMEX and implicit strong stability preserving Runge-Kutta schemes, Appl. Numer. Math., 159 (2021), 204–220. https://doi.org/10.1016/j.apnum.2020.09.007 doi: 10.1016/j.apnum.2020.09.007
[18]	E. Zeidler, Nonlinear Functional Analysis and Its Applications Ⅱ/B: Nonlinear Monotone Operators, Springer-Verlag, New York, 1990.
[19]	Y. L. Zhao, P. Y. Zhu, X. M. Gu, X. L. Zhao, H. Y. Jian, A preconditioning technique for all-at-once system from the nonlinear tempered fractional diffusion equation, J. Sci. Comput., 83 (2020), 10. https://doi.org/10.1007/s10915-020-01193-1 doi: 10.1007/s10915-020-01193-1
[20]	G. H. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, 2012.
[21]	C. M. da Fonseca, On the eigenvalues of some tridiagonal matrices, J. Comput. Appl. Math., 200 (2007), 283–286. https://doi.org/10.1016/j.cam.2005.08.047 doi: 10.1016/j.cam.2005.08.047
[22]	A. R. Willms, Analytic results for the eigenvalues of certain tridiagonal matrices, SIAM J. Matrix Anal. Appl., 30 (2008), 639–656. https://doi.org/10.1137/070695411 doi: 10.1137/070695411
[23]	W. Luo, X. M. Gu, B. Carpentieri, A hybrid triangulation method for banded linear systems, Math. Comput. Simul., 194 (2022), 97–108. https://doi.org/10.1016/j.matcom.2021.11.012 doi: 10.1016/j.matcom.2021.11.012

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)