11

我需要在我的 Java 程序中解决非线性最小化(N 个未知数的最小残差平方)问题。解决这些问题的常用方法是Levenberg-Marquardt算法。我有一些问题

  • 有人对可用的不同 LM 实现有经验吗?LM 的风格略有不同,我听说该算法的确切实现对其数值稳定性有重大影响。我的功能表现得非常好,所以这可能不是问题,但我当然想选择一个更好的选择。以下是我发现的一些替代方案:

  • 是否有任何常用的启发式方法来进行 LM 所需的初始猜测?

  • 在我的应用程序中,我需要对解决方案设置一些约束,但幸运的是它们很简单:我只要求解决方案(为了成为物理解决方案)是非负的。稍微负的解决方案是数据测量不准确的结果,显然应该为零。我正在考虑使用“常规”LM,但会进行迭代,以便如果某些未知数变为负数,我将其设置为零并从中解决其余的问题。真正的数学家可能会嘲笑我,但你认为这可行吗?

感谢您的任何意见!

更新:这不是火箭科学,要解决的参数数量(N)最多为 5 个,数据集几乎不足以解决问题,所以我相信 Java 足够有效地解决这个问题。而且我相信这个问题已经被聪明的应用数学家解决了无数次,所以我只是在寻找一些现成的解决方案,而不是自己做饭。例如,如果它是纯 Python,Scipy.optimize.minpack.leastsq 可能会很好。

4

5 回答 5

2

您最初的猜测越接近解决方案,您收敛的速度就越快。

你说这是一个非线性问题。您可以做一个线性化的最小二乘解决方案。也许您可以使用该解决方案作为第一个猜测。一些非线性迭代将告诉您假设的好坏。

另一个想法是尝试另一种优化算法。如果您可以在许多 CPU 上运行遗传算法和蚁群算法,它们可能是一个不错的选择。它们也不需要连续的导数,所以如果你有离散的、不连续的数据,它们就很好。

于 2009-02-12T14:07:24.310 回答
2

如果您的问题有约束,则不应使用无约束求解器。例如,如果知道你的一些变量必须是非负的,你应该告诉你的求解器。

如果您乐于使用 Scipy,我会推荐 scipy.optimize.fmin_l_bfgs_b 您可以使用 L-BFGS-B 对变量设置简单的界限。

请注意,L-BFGS-B 采用一般非线性目标函数,而不仅仅是非线性最小二乘问题。

于 2009-06-26T23:45:13.973 回答
2

我同意codehippo;我认为解决约束问题的最佳方法是使用专门设计用于处理它们的算法。在这种情况下,L-BFGS-B 算法应该是一个很好的解决方案。

但是,如果在您的情况下使用 python 的 scipy.optimize.fmin_l_bfgs_b 模块不是一个可行的选择(因为您使用的是 Java),您可以尝试使用我编写的库:a Java wrapper for the original Fortran code of the L-BFGS -B 算法。您可以从http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper下载它,看看它是否符合您的需求。

于 2011-06-27T15:10:01.977 回答
1

FPL 包非常可靠,但由于它对旧 fortran 代码的字面解释,有一些怪癖(数组访问从 1 开始)。如果你的函数表现良好,LM 方法本身就非常可靠。强制非负约束的一种简单方法是使用参数的平方而不是直接使用参数。这可能会引入虚假的解决方案,但对于简单的模型,这些解决方案很容易被筛选掉。

有可用于“受约束”LM 方法的代码。在这里查看http://www.physics.wisc.edu/~craigm/idl/fitting.html以获取 mpfit。有一个 python(不幸的是依赖于 Numeric)和一个 C 版本。LM 方法大约有 1500 行代码,因此您可能倾向于将 C 移植到 Java。事实上,“受约束的”LM 方法与您设想的方法并没有太大区别。在 mpfit 中,代码根据变量的界限调整步长。我在 mpfit 上也取得了不错的成绩。

我在 BFGS 方面没有太多经验,但代码要复杂得多,而且我一直不清楚代码的许可。

祝你好运。

于 2009-07-25T08:21:18.540 回答
0

我实际上并没有使用过任何这些 Java 库,所以对此持保留态度:基于后端,我可能会首先查看 JLAPACK。我相信 LAPACK 是Numpy的后端,它本质上是在 Python 中进行线性代数/数学运算的标准。至少,您绝对应该使用优化良好的 C 或 Fortran 库而不是纯 Java,因为对于大型数据集,这些类型的任务可能会变得非常耗时。

对于创建初始猜测,这实际上取决于您尝试拟合的函数类型(以及您拥有的数据类型)。基本上,只需寻找一些相对快速(可能是 O(N) 或更好)的计算,这些计算将为您想要的参数提供一个近似值。(我最近在 Numpy 中使用高斯分布进行了此操作,并且我估计了平均值average(values, weights = counts)- 即直方图中计数的加权平均值,这是数据集的真实平均值。它不是精确的中心我正在寻找的峰值,但它已经足够接近了,算法完成了剩下的工作。)

至于保持约束积极,你的方法似乎是合理的。由于您正在编写一个程序来完成这项工作,也许只需制作一个布尔标志,让您轻松启用或禁用“强制非负”行为,并以两种方式运行以进行比较。只有当你得到一个很大的差异(或者如果一个版本的算法花费了不合理的时间),它可能是值得担心的。(真正的数学家会从头开始分析地进行最小二乘法最小化;-P 所以我认为你是可以嘲笑他们的人......开玩笑。也许吧。)

于 2009-02-12T08:28:17.587 回答