具有非常小的数字的非负最小二乘

计算科学 约束优化 最小二乘 预处理 可能性 数值限制
2021-12-17 06:18:22

(我之前在 StackOverflow 上问过这个问题,但有人指出 CSSE 或 MSE 可能更合适)

我必须解决以下形式的约束优化问题,其中唯一的未知数是x

x=argminxAxb2xR0n, AR0n×n,bR0n

换句话说,一个非负最小二乘问题(NNLS)。或者,我可以解决一个线性程序(知道这些是不一样的,但我想要一个更方便的解决方案):

minimizeiξi
subject to:  Ax=b +ξ
xR0n,ξR0n

现在到目前为止一切顺利。我的问题是我使用的矩阵 A 和向量 b 包含非常小的条目(1e-60,1e-100)请注意,所有数字都大致如此之小。这是因为它们来自对高维 pdf 的评估。据我所知,即使是最精确的求解器也无法正确处理这些数字。我的算法的其余部分可以很好地处理这些数字,因为所有操作都是在对数空间中执行的,因为它在概率中很常见。

尝试使用我提出的任何一种方法来解决原始问题,即使用例如scipy.optimize.nnlsor scipy.optimize.linprog,导致求解器仅返回一个零向量。

可以考虑解决以下修改后的问题(例如):

x=argminxlog(A)xlog(b)2xR0n, AR0n×n,bR0n

可以对前面显示的 LP 进行模拟修改。虽然这不会遇到相同的优化问题,但这个修改后的问题的最佳解决方案与原始问题的最佳解决方案不同。那是,xx并且xexp(x). 解决这个修改后的问题并将其取幂并不会给出完全荒谬的结果,但对于我的目的来说还不够好。

尽管小条目给出了优化问题,我将如何解决原始问题Ab?

1个回答

要解决非常非常小的数字的问题,您需要使用任意精度的算术库,例如 MPFR。https://www.mpfr.org/

MPFR 非常棒,并且会不断提高精度,直到足以避免舍入误差或内存不足。根据我的经验,我从未使用超过 128 位尾数(双精度数类似于 53)。告别数字限制!你的程序会运行得更慢,但它会成功。

如果您首选的求解器不支持这种数据类型,您可以使用非常简单的梯度下降实现和变量更改来编写自己的求解器。

xi=yi2. 向量函数现在表示为F=Ay2b. 梯度下降迭代是这样的:

ynew=yoldγ||F||2
在哪里||F||2=2(F)TFFij=2Aijyjγ是一个任意(通常很小)的正步长。恢复x通过平方值y,它总是非负的。有多种复杂的方法γ提高收敛性的每一步。无论您做什么,您很可能都必须尝试几个(或多个)随机起点来找到最佳解决方案。