使用CUDA以非线性最小二乘方式求解方程组

Question

使用CUDA,我想用非线性最小二乘求解器求解一个方程组.这些方法在一本优秀的小册子中讨论,可以在这里下载.

我的问题中的雅可比矩阵是稀疏的,下三角形.是否有可以使用这些方法的CUDA库,或者我是否必须自己从小册子中编写这些方法？

高斯 - 牛顿非线性最小二乘求解器,Levenberg-Marquardt或Powell的方法求解器是否可用于CUDA库(免费或非免费)？

Answer 1

在指出CUDA中准牛顿优化例程的可能简单实现之前,有关准牛顿优化器如何工作的一些话.

考虑N个实数变量x的函数f,并围绕某个点xi进行二阶扩展:

其中A是Hessian矩阵.

为了找到从点xi开始的最小值,牛顿的方法包括强制

这需要

反过来,它暗示知道Hessian的逆.此外,为确保功能降低,更新方向

应该这样

这意味着

根据上述不等式,Hessian矩阵应该是正定的.遗憾的是,Hessian矩阵不一定是正定的,特别是远离f的最小值,所以使用Hessian的逆,除了计算负担之外,也可能是有害的,将程序推向更远的最小值到增加值的区域的˚F.一般来说,使用拟牛顿方法更方便,即Hessian的逆的近似,其在迭代收敛到Hessian本身的逆之后保持确定的正和更新迭代.准牛顿法的粗略理由如下.考虑

和

减去这两个方程式,我们得到牛顿过程的更新规则

准牛顿程序的更新规则如下

其中Hi + 1是所提到的矩阵,近似于Hessian的逆矩阵并且逐步更新步骤.

更新Hi + 1有几条规则,我不会详细讨论这一点.Broyden-Fletcher-Goldfarb-Shanno提供了一个非常普遍的方法,但在许多情况下,Polak-Ribiére方案是有效的.

CUDA实现可以遵循经典的数字配方方法的相同步骤,但考虑到:

1)CUDA Thrust或cuBLAS可以有效地完成矢量和矩阵运算; 2)控制逻辑可以由CPU执行; 3)线路最小化,包括根包围和根发现,可以在CPU上执行,仅加速GPU的成本函数和梯度评估.

通过上述方案,可以在设备上保留未知数,梯度和Hessian,而无需在主机之间来回移动它们.

请注意,文献中还提供了一些方法,其中也提出了并行化线路最小化的方法,参见

Y. Fei,G.Rong,B.Wang,W.Wang,"GPU上的并行L-BFGS-B算法",计算机与图形学,第一卷.40,2014,pp.1-9.

在这个github页面上,可以使用完整的CUDA实现,概括了采用的Numerical Recipes方法linmin,mkbrak以及dbrentGPU并行的情况.这种方法实现了Polak-Ribiére的方案,但可以很容易地推广到其他准牛顿优化问题.