使用 CUDA，我想用非线性最小二乘求解器求解方程组。这些方法在一本优秀的小册子中进行了讨论，可以在这里下载。
我的问题中的雅可比矩阵是稀疏的下三角矩阵。是否有可用于这些方法的 CUDA 库，还是我必须自己从手册中编写这些方法？
CUDA 库（免费或非免费）中是否提供 Gauss-Newton 非线性最小二乘求解器、Levenberg-Marquardt 或 Powell 方法求解器？
问问题
7677 次
4 回答
8
在指出 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，第 1-9 页。
在这个github 页面上，可以使用完整的 CUDA 实现，将使用 的数值配方方法推广到linminGPU并行案例。该方法实现了 Polak-Ribiére 的方案，但可以很容易地推广到其他准牛顿优化问题。mkbrakdbrent
于 2015-01-31T21:32:04.140 回答
1
也看看这个：libflame包含由 BLAS 和 LAPACK 库提供的许多操作的实现
于 2012-11-08T00:36:50.757 回答
0
目前在任何库中都没有可用的程序来实现使用 CUDA 平台使用非线性最小二乘求解器求解方程组。这些算法必须从头开始编写，并借助其他一些使用稀疏矩阵实现线性代数的库。此外，正如上面评论中提到的，cuBLAS 库将有助于线性代数。
于 2012-11-07T23:36:33.003 回答
0
对于那些仍在寻找答案的人，这个适用于稀疏矩阵：OpenOF，“Framework for Sparse Non-linear Least Squares Optimization on a GPU”
GPU之于g2o之于CPU。
于 2015-10-13T13:26:29.790 回答