数值求解非线性方程
我需要解决 Java 程序中的非线性最小化（N 个未知数的最小残差平方）问题。 解决这些问题的常用方法是 Levenberg-Marquardt 算法。 我有几个问题
有人对可用的不同 LM 实现有经验吗？ LM 的风格略有不同，我听说算法的精确实现对其数值稳定性有重大影响。 我的函数表现得非常好，所以这可能不会成为问题，但我当然想选择更好的替代方案之一。 以下是我发现的一些替代方案：
FPL 统计组的非线性优化 Java 包。 这包括经典 Fortran MINPACK 例程的 Java 翻译。
JLAPACK，另一个 Fortran 翻译。
一些 Python 实现。 纯 Python 就可以了，因为它可以用 jythonc 编译为 Java。
是否有任何常用的启发式方法来进行 LM 所需的初始猜测？
在我的应用程序中，我需要对解决方案设置一些约束，但幸运的是它们很简单：我只要求解决方案（为了成为物理解决方案）是非负的。 轻微负解是数据测量不准确的结果，显然应该为零。 我正在考虑使用“常规”LM，但进行迭代，以便如果某些未知数变为负值，我将其设置为零并从中解决其余问题。 真正的数学家可能会嘲笑我，但你认为这可行吗？
感谢您的任何意见！
更新：这不是火箭科学，要求解的参数数量 (N) 最多为 5 个，并且数据集勉强大到足以使求解成为可能，所以我相信 Java 足够高效解决这个问题。 我相信聪明的应用数学家已经多次解决了这个问题，所以我只是在寻找一些现成的解决方案，而不是自己解决。 例如，如果它是纯Python，Scipy.optimize.minpack.leastsq 可能会没问题。
I need to solve nonlinear minimization (least residual squares of N unknowns) problems in my Java program. The usual way to solve these is the Levenberg-Marquardt algorithm. I have a couple of questions
Does anybody have experience on the different LM implementations available? There exist slightly different flavors of LM, and I've heard that the exact implementation of the algorithm has a major effect on the its numerical stability. My functions are pretty well-behaved so this will probably not be a problem, but of course I'd like to choose one of the better alternatives. Here are some alternatives I've found:
FPL Statistics Group's Nonlinear Optimization Java Package. This includes a Java translation of the classic Fortran MINPACK routines.
JLAPACK, another Fortran translation.
Some Python implementation. Pure Python would be fine, since it can be compiled to Java with jythonc.
Are there any commonly used heuristics to do the initial guess that LM requires?
In my application I need to set some constraints on the solution, but luckily they are simple: I just require that the solutions (in order to be physical solutions) are nonnegative. Slightly negative solutions are result of measurement inaccuracies in the data, and should obviously be zero. I was thinking to use "regular" LM but iterate so that if some of the unknowns becomes negative, I set it to zero and resolve the rest from that. Real mathematicians will probably laugh at me, but do you think that this could work?
Thanks for any opinions!
Update: This is not rocket science, the number of parameters to solve (N) is at most 5 and the data sets are barely big enough to make solving possible, so I believe Java is quite efficient enough to solve this. And I believe that this problem has been solved numerous times by clever applied mathematicians, so I'm just looking for some ready solution rather than cooking my own. E.g. Scipy.optimize.minpack.leastsq would probably be fine if it was pure Python..
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您的初始猜测越接近解决方案，收敛的速度就越快。
你说这是一个非线性问题。 您可以进行线性化的最小二乘解。 也许您可以使用该解决方案作为第一个猜测。 一些非线性迭代会告诉您假设的好坏。
另一个想法是尝试另一种优化算法。 如果遗传算法和蚁群算法可以在许多 CPU 上运行，那么它们可能是一个不错的选择。 它们也不需要连续导数，因此如果您有离散、不连续的数据，它们就很好。
The closer your initial guess is to the solution, the faster you'll converge.
You said it was a non-linear problem. You can do a least squares solution that's linearized. Maybe you can use that solution as a first guess. A few non-linear iterations will tell you something about how good or bad an assumption that is.
Another idea would be trying another optimization algorithm. Genetic and ant colony algorithms can be a good choice if you can run them on many CPUs. They also don't require continuous derivatives, so they're nice if you have discrete, discontinuous data.
如果您的问题有约束，则不应使用无约束求解器。 为了
实例如果知道你的一些变量必须是非负的你应该告诉
这给你的解算器。
如果您乐意使用 Scipy，我会推荐 scipy.optimize.fmin_l_bfgs_b
您可以使用 L-BFGS-B 对变量设置简单的界限。
请注意，L-BFGS-B 采用一般非线性目标函数，而不仅仅是
非线性最小二乘问题。
You should not use an unconstrained solver if your problem has constraints. For
instance if know that some of your variables must be nonnegative you should tell
this to your solver.
If you are happy to use Scipy, I would recommend scipy.optimize.fmin_l_bfgs_b
You can place simple bounds on your variables with L-BFGS-B.
Note that L-BFGS-B takes a general nonlinear objective function, not just
a nonlinear least-squares problem.
我同意codehippo； 我认为解决约束问题的最佳方法是使用专门设计来处理它们的算法。 在这种情况下，L-BFGS-B 算法可能是一个很好的解决方案。
但是，如果使用 python 的 scipy.optimize.fmin_l_bfgs_b 模块在您的情况下不是一个可行的选择（因为您使用的是 Java），您可以尝试使用我编写的库：L-BFGS 的原始 Fortran 代码的 Java 包装器-B算法。 您可以从 http://www.mini.pw.edu.pl 下载它/~mkobos/programs/lbfgsb_wrapper 并查看它是否符合您的需求。
I agree with codehippo; I think that the best way to solve problems with constraints is to use algorithms which are specifically designed to deal with them. The L-BFGS-B algorithm should probably be a good solution in this case.
However, if using python's scipy.optimize.fmin_l_bfgs_b module is not a viable option in your case (because you are using Java), you can try using a library I have written: a Java wrapper for the original Fortran code of the L-BFGS-B algorithm. You can download it from http://www.mini.pw.edu.pl/~mkobos/programs/lbfgsb_wrapper and see if it matches your needs.
FPL 包相当可靠，但由于它对旧的 Fortran 代码的字面解释，有一些怪癖（数组访问从 1 开始）。 如果您的函数表现良好，那么 LM 方法本身就相当可靠。 强制非负约束的一个简单方法是使用参数的平方而不是直接使用参数。 这可能会引入虚假的解决方案，但对于简单的模型，这些解决方案很容易被筛选出来。
有可用于“约束”LM 方法的代码。 看这里 http://www.physicals.wisc.edu/~craigm/ idl/fitting.html 用于 mpfit。 有一个 python（不幸的是依赖于 Numeric）和一个 C 版本。 LM 方法大约有 1500 行代码，因此您可能倾向于将 C 移植到 Java。 事实上，“约束”LM 方法与你想象的方法没有太大区别。 在 mpfit 中，代码调整相对于变量边界的步长。 我用 mpfit 也取得了很好的结果。
我对 BFGS 没有太多经验，但代码要复杂得多，而且我一直不清楚代码的许可。
祝你好运。
The FPL package is quite reliable but has a few quirks (array access starts at 1) due to its very literal interpretation of the old fortran code. The LM method itself is quite reliable if your function is well behaved. A simple way to force non-negative constraints is to use the square of parameters instead of the parameters directly. This can introduce spurious solutions but for simple models, these solutions are easy to screen out.
There is code available for a "constrained" LM method. Look here http://www.physics.wisc.edu/~craigm/idl/fitting.html for mpfit. There is a python (relies on Numeric unfortunately) and a C version. The LM method is around 1500 lines of code, so you might be inclined to port the C to Java. In fact, the "constrained" LM method is not much different than the method you envisioned. In mpfit, the code adjusts the step size relative to bounds on the variables. I've had good results with mpfit as well.
I don't have that much experience with BFGS, but the code is much more complex and I've never been clear on the licensing of the code.
Good luck.
我实际上没有使用过任何这些 Java 库，所以对此持保留态度：基于后端，我可能会首先查看 JLAPACK。 我相信 LAPACK 是 Numpy 的后端，它本质上是在 Python 中进行线性代数/数学操作的标准。 至少，您绝对应该使用优化良好的 C 或 Fortran 库，而不是纯 Java，因为对于大型数据集，此类任务可能会变得极其耗时。
为了创建初始猜测，这实际上取决于您想要拟合的函数类型（以及您拥有的数据类型）。 基本上，只需寻找一些相对快速（可能是 O(N) 或更好）的计算即可给出所需参数的近似值。 （我最近在 Numpy 中使用高斯分布进行了此操作，我将平均值估计为平均值（值，权重 = 计数），即直方图中计数的加权平均值，即它不是我正在寻找的峰值的确切中心，但它足够接近，并且算法完成了其余的工作。）
至于保持正约束，您的方法似乎是合理的。 由于您正在编写一个程序来完成这项工作，也许只需创建一个布尔标志，即可让您轻松启用或禁用“强制非负”行为，并以两种方式运行它以进行比较。 只有当您得到很大的差异（或者算法的一个版本花费的时间过长）时，才可能需要担心。 （真正的数学家会从头开始分析最小二乘法；-P 所以我认为你是那个可以嘲笑他们的人......开玩笑。也许吧。）
I haven't actually used any of those Java libraries so take this with a grain of salt: based on the backends I would probably look at JLAPACK first. I believe LAPACK is the backend of Numpy, which is essentially the standard for doing linear algebra/mathematical manipulations in Python. At least, you definitely should use a well-optimized C or Fortran library rather than pure Java, because for large data sets these kinds of tasks can become extremely time-consuming.
For creating the initial guess, it really depends on what kind of function you're trying to fit (and what kind of data you have). Basically, just look for some relatively quick (probably O(N) or better) computation that will give an approximate value for the parameter you want. (I recently did this with a Gaussian distribution in Numpy and I estimated the mean as just
average(values, weights = counts)- that is, a weighted average of the counts in the histogram, which was the true mean of the data set. It wasn't the exact center of the peak I was looking for, but it got close enough, and the algorithm went the rest of the way.)As for keeping the constraints positive, your method seems reasonable. Since you're writing a program to do the work, maybe just make a boolean flag that lets you easily enable or disable the "force-non-negative" behavior, and run it both ways for comparison. Only if you get a large discrepancy (or if one version of the algorithm takes unreasonably long), it might be something to worry about. (And REAL mathematicians would do least-squares minimization analytically, from scratch ;-P so I think you're the one who can laugh at them.... kidding. Maybe.)