文章

径向基函数法文献总结

总结使用径向基函数求解 PDE 的相关文献。

径向基函数法文献总结

概述

大部分衍生品定价问题最终归结为求解 PDE 的数值解,最常见的数值方法莫过于 FDM。假设定价问题对应的 PDE 问题如下:

\[\begin{align*} \frac{\partial U(\bar{x},t)}{\partial t} + LU(\bar{x},t) &= 0 ,& \bar{x} \in \Omega \\ BU(\bar{x},t) &= f(\bar{x},t),& \bar{x} \in \partial \Omega \\ U(\bar{x},T) &= g(\bar{x}) \end{align*} \tag{1}\]

$L$ 是关于 $\bar{x}$ 的微分算子,$B$ 表示边界条件对应的微分算子。

FDM 首先在一个规则的求解域 $\Omega$ 内划定网格,并在网格上对 $L$ 和 $B$ 做差分近似。其次在时间 $t$ 维度上做一阶差分近似,以隐式欧拉格式为例,FDM 的整个计算过程被分解为求解一连串的线性方程组。现实中求解域 $\Omega$ 的形状通常是线段、矩形和(超)立方体。

FDM 中线性方程组的尺寸和求解域 $\Omega$ 维度成指数关系,这使得 FDM 较难处理两维以上的 PDE。举个例子,一个表示三标的篮子期权的 BS-PDE,$(x_1,x_2,x_3)$ 三个维度分别划分为 100 份,那么线性方程组中的矩阵的维度将会是 $10^6$,尽管这个矩阵是高度稀疏的,求解起来依旧耗时。

既然作为网格法代表的 FDM 无力解决较高维度的 PDE,一个自然的想法是用无网格法求解 PDE,衍生品定价领域中无网格法的代表就是基于径向基函数(Radial Basis Function)衍生出的一系列数值方法(关于径向基函数更具体的介绍参考文献1)。

将径向基函数用于计算 PDE 数值解的想法最早由 Kansa 在文献23中以“全局 RBF 法”的形式引入,经过几十年的发展,全局 RBF 法及其衍生出的一系列数值方法(包括 RBF-PU、RBF-QI、RBF-FD、RBF-DQ)已经在计算流体力学、电磁学、热力学、工业设计和衍生品定价等领域有了成熟的应用。

全局 RBF 法

在问题(1)将 $U(\bar{x}, t)$ 中 $t$ 的动态部分分离出来,而 $\bar{x}$ 的部分用 RBF 拟合近似,这便是全局 RBF 法的基本思想。

在求解域 $\Omega$ 中选定一组支点 $x_i(i = 1,\dots,N)$,将 $U$ 表示为

\[U(\bar{x},t) = \sum_{i=1}^N \alpha_i(t) \phi(\parallel \bar{x} - x_i \parallel)\]

其中 $\phi(r)$ 就是径向基函数,$\parallel \parallel$ 表示空间向量的范数,于是问题(1)表示为

\[\sum_{i=1}^N \frac{d \alpha_i(t)}{dt} \phi(\parallel \bar{x} - x_i \parallel) + \sum_{i=1}^N \frac{d \alpha_i(t)}{dt} L \phi(\parallel \bar{x} - x_i \parallel) = 0 \tag{2}\]

将 $x_i(i = 1,\dots,N)$ 代入到等式(2)中得到

\[\Phi \frac{d\alpha(t)}{dt} + L_{\Phi} \alpha(t)=0\]

其中 $\alpha(t)=[\alpha_1(t),\dots,\alpha_N(t)]^T$ ,$\Phi$ 和 $L_{\Phi}$ 都是矩阵,$\Phi(i,j) = \phi(\parallel x_i - x_j \parallel)$,$L_{\Phi}(i,j) = L\phi(\parallel \bar{x} - x_i \parallel)\mid_{\bar{x}=x_j}$。如此一来求解 PDE 的问题便转化成了求解一个 N 维 ODE 问题,这便是全局 RBF 法的基本思路。

文献4最早将全局 RBF 法引入到单标的欧式和美式期权的求解中,文章总结出应用 RBF 的一般流程;文献5将全局 RBF 法应用于双标的欧式和美式期权,并讨论了边界条件和支点布局对结果的影响;文献6对全局 RBF 法做了误差分析;文献7在用全局 RBF 法计算美式期权时采用了“惩罚法”技术,将自由边界问题转化为非线性 PDE,发挥了 RBF 处理非线性 PDE 的优势;文献8提出了处理不光滑初始条件的特殊算法,即一个计算矩阵指数的简单快速的方法;文献9将全局 RBF 法与广义傅里叶变换结合以提高计算速度;文献10讨论了全局 RBF 法用于多标的欧式期权定价时,边界条件、支点的分布和形状参数对定价精度的影响;文献11和文献12将全局 RBF 法用于跳扩散模型的求解;文献13全局 RBF 法与算子分离结合求解多维 PDE;文献14总结了全局 RBF 在期权定价中的应用,并和 FDM \ FEM 比较。

总结文献可以发现全局 RBF 法相较于 FDM 有以下优点:

  • 维度无关,全局 RBF 法的计算量由 $x_i(i = 1,\dots,N)$ 的数量决定,不依赖于问题的维度;
  • 对求解域 $\Omega$ 的形状没有严格要求,FDM 通常要求求解域是一个矩形或立方体,事实上应用 RBF 时,不少文献的求解域是一个三角形或四面体(例如文献10);
  • 收敛迅速,精度高(文献6和文献10)。

全局 RBF 法也有一些缺点:

  • 矩阵 $\Phi$ 和 $L_{\Phi}$ 都是稠密矩阵,导致计算效率较低;
  • 大部分基函数的形状依赖于事先选定的“形状参数”,形状参数的选择会显著影响结果的精度,但最优形状参数的选择并没有固定方法;
  • 研究表明基函数形状趋于“扁平”时(即形状参数趋于 0)可以提高结果的精度,但也会导致矩阵 $\Phi$ 趋于病态(条件数巨大),致使求解线性代数问题的稳定性下降。

处理病态矩阵

为处理病态矩阵,需要研究矩阵 $\Phi$ 在形状参数趋于 0 时的渐进行为,并作出特殊处理。

文献15第一个细致的研究了这个问题,提出用 提出 Contour-Pade 算法解决形状函数趋于 0 时矩阵病态的问题;文献16提出了 RBF-QR 算法专门用于球面上的全局 RBF 法;文献17又将 RBF-QR 算法推广到一维和三维;文献18提出 RBF-GA 算法,作为 RBF-QR 的推广,但仅限于高斯基函数;文献19提出 RBF-RA 算法,推广了 RBF-QR 和 RBF-GA,可以适应多种类型的基函数。

稀疏化策略

全局 RBF 法的一项重要发展是局部化。通过局部化,矩阵 $\Phi$ 和 $L_{\Phi}$ 变为稀疏矩阵(带状矩阵),一方面提高了代数计算的效率,另一方面较少了矩阵的病态。

RBF 法的稀疏化策略有以下几种:

  • 借助单位分解法(Partition of Unity Method),仅通过局部的支点近似 PDE,称为 RBF-PU;
  • 借助拟插值(Quasi Interpolation),通过舍弃接近 0 的数直接稀疏化矩阵 $\Phi$ 和 $L_{\Phi}$,称为 RBF-QI。

RBF-PU

在 RBF-PU 法中,除了原有的密集支点 $x_i(i = 1,\dots,N)$ 外,还规定了一组稀疏的支点 $y_j(j = 1,\dots,M)$ 以及对应的半径 $R$。若 $x_i$ 落在了 $y_j$ 划定的圆或球内部,划定范围内部的支点会用来近似 PDE,范围外的支点不起作用,这就是 RBF-PU 法的基本思想。

文献20、文献21和文献22介绍了如何将 RBF-PU 用于多标的的欧式和美式期权定价,其中美式采用了“惩罚法”技术和算子分离技术;文献23将 RBF-PU 用于跳扩散模型以及局部波动率模型;文献24将 RBF-PU 用于随机波动率下的美式期权定价;文献25讨论了 RBF-PU 在复杂定价模型中的应用(包括 Quadratic SLV、SABR、Heston-Hull-White、Heston-Cox-Ingersoll-Ross 模型);文献26和文献27分别提出并推广了 D-RBF-PU 法,以提高 RBF-PU 的计算效率。

RBF-PU 对矩阵的稀疏化效果可以参考文献20的图 5、文献22的图 1、文献24的图 4。

RBF-QI

拟插值(Quasi-Interpolation)是一类基于 RBF 的特殊插值方法,问题(1)中将 $U(\bar{x},t)$ 用拟插值近似

\[U(\bar{x}, t) = \sum_{i=1}^N \alpha_i(t) \Phi_i(x)\]

其中 $\Phi_i(x)$ 是基函数 $\phi$ 的线性组合,利用 $\Phi_i(x)$ 会衰减至 0 的特性,通过舍弃接近 0 的参数直接稀疏化矩阵 $\Phi$ 和 $L_{\Phi}$。

文献28首次使用拟插值技术求解单标的欧式和美式期权;文献29和文献30将 RBF-QI 法扩展到多标的期权上。

RBF-FD

全局 RBF 法的另一项重要发展是 RBF-FD 法。回想 FDM,对于求解域 $\Omega$ 中的一个特定支点 $x_i$,存在若干围绕 $x_i$ 的支点 $x_j^i$(成为 stencil),FDM 的一个基本理念是用 $U(x_j^i,t)$ 的线性组合来近似 $LU(x_i,t)$。将 RBF 的无网格拟合能力与 FDM 格式结合起来,令

\[LU(x_i,t) = \sum_{j=1}^N w_j U(\parallel x_j^i - x_i \parallel)\]

为得到 $w$,可以要求临近支点 $x_j^i$ 代入 $x$ 后均满足下面的等式

\[L \phi(x,t) = \sum_{j=1}^N w_j^i \phi(\parallel x - x_j^i \parallel)\]

最终,问题(1)将得到类似 FDM 形式的离散近似,

\[\frac{\partial U(\bar{x},t)}{\partial t} = W U(\bar{x},t)\]

和 FDM 的情况类似,$W$ 将会是一个带状矩阵,这就是 RBF-FD 的基本想法。

文献31最早提出了 RBF-FD 的概念;文献32分析了 RBF-FD 的收敛性;文献33和文献34用 RBF-FD 求解跳扩散模型;文献35总结了全局 RBF 和 RBF-FD 在求解 PDE 中的应用;文献25讨论了 RBF-FD 在复杂定价模型中的应用;文献36提出重合 RBF-FD 的概念,改进了传统的 RBF-FD,大幅提高速度和准确性。文献37在 RBF-FD 法中添加 Polyharmonic Splines(PHS)以提高近似的精度,并讨论了支点的分布问题;RBF-FD 结合 PHS 更细致的内容参考文献38、文献39和文献40;文献41和文献42 RBF-FD 法配合算子分离技术分别计算美式期权和机制转换跳扩散模型;文献43用 RBF-FD 解随机利率随机波动率的外汇期权(产生一个 4D-PDE),为提高计算精度采用了非均匀布点,解 ODE 的时候用了 Krylov 法计算矩阵的指数;文献44将 RBF-FD 用于双标的期权,并讨论了平滑初始状态的方法、非均匀布点、stencil 大小的选择;文献45和文献46分别用 RBF-FD 解 Heston-Hull-White 模型和 Hexton-CIR 模型;文献47和文献48总结了 RBF-FD。

目前,RBF-FD 可能是径向基函数法家族中使用最广泛、最成功的一个。

RBF-DQ

正如 RBF 与 FDM 结合产生了 RBF-FD 法,RBF 与 Differential Quadrature 的结合产生了 RBF-DQ 法。和 RBF-FD 类似,RBF-DQ 中 $U$ 的一二阶导数值被要求用 $U$ 在支点值的线性组合表示,

\[\frac{\partial U(\bar{x},t)}{\partial x_i} = \sum_{j=1}^N \alpha_j^i U(x_j,t)\\ \frac{\partial^2 U(\bar{x},t)}{\partial x_i^2} = \sum_{j=1}^N \beta_j^i U(x_j,t)\]

为得到 $\alpha_j^i$ 和 $\beta_j^i$,将 $U$ 替换成基函数 $\phi$,并遍历所有支点可以解出 $\alpha$ 和 $\beta$ 组成的矩阵。

文献49提出 RBF-DQ 法;文献50用 RBF-DQ 求解跳扩散模型;传统的 RBF-DQ 法无法处理混合导数,文献51改进了 RBF-DQ 法,以处理混合导数项并提高了计算速度;文献52主张通过对坐标线性变化以消除 PDE 中的混合导数。

RBF-DQ 也可以通过局部化提升效率和稳定性,文献53545556分别介绍了 RBF-DQ 的局部化。文献57将局部 RBF-DQ 用于多标的期权定价。

形状参数的选择

前面提到形状参数的选择对结果的精度有显著影响,但是最优形状参数的选择并没有确定性的方法,通常是基于实验和统计的方法的到特定 PDE 问题对应的最优形状参数。

文献58主张用统计学习中的技术 Leave-One-Out Cross Validation(LOOCV)选择最优形状参数。

支点布局和 Stencil 的选择

对于 FDM 来说,对求解域划分网格非常简单,难点在于在网格上构造 PDE 算子的离散近似。而 RBF 法则相反,构造 PDE 算子的离散近似不难,难点反而在于生成合适的支点布局,现实中生成支点是一个重要但常被忽略的问题。直接沿用 FDM 的网格划分是最容易实现的布局方法,但通常不能达到很好的收敛性;采用伪随机数或拟随机数生成的支点无法避免支点出现局部的聚集(使用伪随机数时情况更严重),当支点距离过近可能会使矩阵的条件数增大,带来意外的不稳定性;生成非均匀的支点布局本身就是一个有挑战性的问题。

文献59最早关注了这个问题,介绍了 2D 平面上支点布局的一般方法(即 Fornberg-Flyer 法);文献60介绍了 2D 平面和 3D 曲面上支点布局的一般方法(即 Shankar-Kirby-Fogelson 法),推广了 Fornberg-Flyer 法;文献61改进了 Fornberg-Flyer 法的实现,提高生成速度,并适用于高维求解域,另外提出了基于 Poisson Disk Sampling 的布局生成法;文献62推广了 Fornberg-Flyer 法和 Shankar-Kirby-Fogelson 法,可用于更高维度的解域。上述提到的生成法大多支持生成非均匀的支点布局。

对于 RBF-FD 而言,除了支点的生成问题,stencil 的选择也很重要。文献63、文献64和文献65分别研究了这个问题。

其他

  • 开源项目——RBF,用 Python 实现了 RBF 插值、RBF-FD 求解 PDE 等功能。
  • 开源项目——Medusa,用 C++ 实现了 RBF-FD 以及二维、三维空间中支点布局的算法,应用于工业设计。
  • 学术团体——Uppsala 大学的 RBF 组

参考文献

  1. Recent Advances in Radial Basis Function Collocation Methods ↩︎

  2. Multiquadrics - a Scattered Data Approximation Scheme with Applications to Computational Fluid Dynamics - I ↩︎

  3. Multiquadrics - a Scattered Data Approximation Scheme with Applications to Computational Fluid Dynamics - II ↩︎

  4. A Radial Basis Function Method For Solving Options Pricing Model ↩︎

  5. On the Use of Boundary Conditions for Variational Formulations Arising in Financial Mathematics ↩︎

  6. Convergence Error Estimate in Solving Free Boundary Diffusion Problem by Radial Basis Functions Method ↩︎ ↩︎2

  7. Using Meshfree Approximation for Multi‐Asset American Options ↩︎

  8. A Parallel Time Stepping Approach Using Meshfree Approximations for Pricing Options with Non-Smooth Payoffs ↩︎

  9. Multi-Dimensional Option Pricing Using Radial Basis Functions and the Generalized Fourier Transform ↩︎

  10. Improved Radial Basis Function Methods for Multi-Dimensional Option Pricing ↩︎ ↩︎2 ↩︎3

  11. Meshfree Approximation for Multi-Asset Options ↩︎

  12. Radial Basis Functions with Application to Finance: American Put Option Under Jump Diffusion ↩︎

  13. Pricing European and American Options with Two Stochastic Factors: A Highly Efficient Radial Basis Function Approach ↩︎

  14. Option Pricing Via Radial Basis Functions: Performance Comparison with Traditional Numerical Integration Scheme and Parameters Choice for a Reliable Pricing ↩︎

  15. Stable Computation of Multiquadric Interpolants for All Values of the Shape Parameter ↩︎

  16. A Stable Algorithm for Flat Radial Basis Functions on a Sphere ↩︎

  17. Stable Computations with Gaussian Radial Basis Functions ↩︎

  18. Stable Calculation of Gaussian-Based RBF-FD Stencils ↩︎

  19. Stable Computations with Flat Radial Basis Functions Using Vector-Valued Rational Approximations ↩︎

  20. A Radial Basis Function Partition of Unity Collocation Method for Convection-Diffusion Equations Arising in Financial Applications ↩︎ ↩︎2

  21. Radial Basis Function Partition of Unity Methods for Pricing Vanilla Basket Options ↩︎

  22. Radial Basis Function Partition of Unity Operator Splitting Method for Pricing Multi-Asset American Options ↩︎ ↩︎2

  23. RBF-PU Method for Pricing Options Under the Jump–Diffusion Model with Local Volatility ↩︎

  24. Radial Basis Functions with Partition of Unity Method for American Options with Stochastic Volatility ↩︎ ↩︎2

  25. Pricing Derivatives Under Multiple Stochastic Factors by Localized Radial Basis Function Methods ↩︎ ↩︎2

  26. The Direct Radial Basis Function Partition of Unity (D-RBF-PU) Method for Solving PDEs ↩︎

  27. A Compact Radial Basis Function Partition of Unity Method ↩︎

  28. A Quasi-Radial Basis Functions Method for American Options Pricing ↩︎

  29. Multivariate Option Pricing Using Quasi-interpolation Based on Radial Basis Functions ↩︎

  30. A Computationally Efficient Numerical Approach for Multi-Asset Option Pricing ↩︎

  31. On Using Radial Basis Functions in a Finite Difference Mode with Applications to Elasticity Problems ↩︎

  32. RBF-FD Formulas and Convergence Properties ↩︎

  33. An Efficient Numerical Method for Pricing Option Under Jump Diffusion Model ↩︎

  34. A Radial Basis Function Based Implicit-Explicit Method for Option Pricing Under Jump-Diffusion Models ↩︎

  35. Solving PDEs with Radial Basis Functions ↩︎

  36. The Overlapped Radial Basis Function-Finite Difference (rbf-Fd) Method: A Generalization of RBF-FD ↩︎

  37. Pricing Financial Derivatives Using Radial Basis Function Generated Finite Differences with Polyharmonic Splines on Smoothly Varying Node Layouts ↩︎

  38. On the Role of Polynomials in RBF-FD Approximations: I. Interpolation and Accuracy ↩︎

  39. On the Role of Polynomials in RBF-FD Approximations: Ii. Numerical Solution of Elliptic Pdes ↩︎

  40. On the Role of Polynomials in RBF-FD Approximations: Iii. Behavior Near Domain Boundaries ↩︎

  41. Radial-Basis-Function-Based Finite Difference Operator Splitting Method for Pricing American Options ↩︎

  42. A RBF Based Finite Difference Method for Option Pricing Under Regime-Switching Jump-Diffusion Model ↩︎

  43. Pricing Foreign Exchange Options Under Stochastic Volatility and Interest Rates Using an RBF-FD Method ↩︎

  44. A High Order Method for Pricing of Financial Derivatives Using Radial Basis Function Generated Finite Differences ↩︎

  45. An Efficient Localized RBF-FD Method to Simulate the Heston–Hull–White PDE in Finance ↩︎

  46. Numerical Investigation of the Three-Dimensional HCIR Partial Differential Equation Utilizing a New Localized RBF-FD Method ↩︎

  47. Radial Basis Function Generated Finite Difference Methods for Pricing of Financial Derivatives ↩︎

  48. Radial Basis Function Generated Finite Differences for Option Pricing Problems ↩︎

  49. Solution of Partial Differential Equations by a Global Radial Basis Function-Based Differential Quadrature Method ↩︎

  50. A New Radial Basis Functions Method for Pricing American Options Under Merton’s Jump-Diffusion Model ↩︎

  51. A Numerical Method to Approximate Multi-Asset Option Pricing Under Exponential Lévy Model ↩︎

  52. A Numerical Study of RBF-DQ Method for Multi-Asset Option Pricing Problems ↩︎

  53. Numerical Solution of the System of Second-Order Boundary Value Problems Using the Local Radial Basis Functions Based Differential Quadrature Collocation Method ↩︎

  54. Local Rbf-Based Differential Quadrature Collocation Method for the Boundary Layer Problems ↩︎

  55. Numerical Simulation of Partial Differential Equations Via Local Meshless Method ↩︎

  56. Numerical Simulation of PDEs by Local Meshless Differential Quadrature Collocation Method ↩︎

  57. Local RBF Method for Multi-Dimensional Partial Differential Equations ↩︎

  58. On Choosing Optimal Shape Parameters for RBF Approximation ↩︎

  59. Fast Generation of 2-D Node Distributions for Mesh-Free Pde Discretizations ↩︎

  60. Robust Node Generation for Mesh-free Discretizations on Irregular Domains and Surfaces ↩︎

  61. Fast Generation of Variable Density Node Distributions for Mesh-Free Methods ↩︎

  62. On Generation of Node Distributions for Meshless PDE Discretizations ↩︎

  63. Adaptive RBF-FD Method for Elliptic Problems with Point Singularities in 2D ↩︎

  64. Guidelines for RBF-FD Discretization: Numerical Experiments on the Interplay of a Multitude of Parameter Choices ↩︎

  65. Improved Stencil Selection for Meshless Finite Difference Methods in 3d ↩︎

本文由作者按照 CC BY 4.0 进行授权