numpy的整数优化/最大化

我需要estimate人口的大小，通过找到最大化n的值scipy.misc.comb(n, a)/n**b其中a和b是常数。 n，a和b都是整数。numpy的整数优化/最大化

很明显，我可以只在range(SOME_HUGE_NUMBER)有一个循环，计算每个n的值，并在曲线拐点出现时跳出循环。但我想知道是否有一个用（比如说）numpy/scipy做这件事的优雅方式，还是有其他一些优雅的方式来做到这一点，就像在纯Python中一样（例如像牛顿法的整数相同）

来源

2016-10-25 TimGJ

你认为'n'有多大？在相关答案中的181个数量级，还是地球上75亿人类的数量级？ – jotasi

我会（直觉）期望n <1000，肯定是10000，但直到我运行真实的数据时，我绝对没有办法知道！ – TimGJ

您可以通过gamma函数（或通过近似斯特林公式）将'comb'转换为实数的函数。然后你可以做一个数值求解技术，然后检查哪个附近的整数是最大值。 – strubbly

As只要你的号码是n相当小（小于约1500），我最快的方法就是尝试所有可能的值。您可以通过使用numpy迅速做到这一点：

import numpy as np 
import scipy.misc as misc 

nMax = 1000 
a = 77 
b = 100 
n = np.arange(1, nMax+1, dtype=np.float64) 
val = misc.comb(n, a)/n**b 
print("Maximized for n={:d}".format(int(n[val.argmax()]+0.5))) 
# Maximized for n=181

这不是特别优雅，但相当快的为范围的n。问题在于n>1484分子已经太大而无法存储在float中。这种方法会失败，因为你会遇到溢出。但是这不仅是numpy.ndarray与python整数不起作用的问题。只要你想在你的大于最大值的两个数字部门的float结果在python float可以保持（我的系统上max_10_exp = 1024

misc.comb(10000, 1000, exact=True)/10000**1001

见：即使它们，你将无法计算。 sys.float_info()。）。在这种情况下，你也不能使用你的range。如果你真的想做这样的事情，你将不得不采取更多的照顾数字。

来源

2016-10-25 09:21:31 jotasi

谢谢。我会假设强力是最有效的方式（如果这不是矛盾的话）。从我提供的数据中感觉到，n将在100到500之间，尽管直到我运行我无法说出的软件。但我只想知道是否有一种简单/优雅的方式。（奇怪的是，昨晚我在YouTube上观看了一段视频，其中Brian Kernighan正在谈论AMPL，这听起来正好可以解决这类问题）。 – TimGJ

@TimGJ可能有更优雅的解决方案。无论如何，你必须非常小心你的数字，尽管数字很大。 – jotasi

您可以通过避免首先计算分子然后除以计算较大数字的函数。相反，如果您使用迭代方法来计算'comb'，那么随着您继续控制中间值的大小，您可以反复划分'n'。通过这种方式，只要总体结果不太大，就可以评估函数的任意大值'n'。 – strubbly

你基本上有一个很好的平滑功能n，你想最大化。 n必须是不可或缺的，但我们可以考虑将函数作为实数的函数。在这种情况下，n的最大整数值必须接近（接近）最大化的实际值。

我们可以将comb转换成一个真正的函数，通过使用gamma函数并使用数值优化技术来找到最大值。另一种方法是用斯特林近似代替因子。这给出了一个适度复杂但易处理的代数表达式。这个表达式不难区分并设置为零来找到极值。

我这样做，并获得

n * (b + (n-a) * log((n-a)/n)) = a * b - a/2

这不是简单的解决代数，但很容易的数字（例如，使用牛顿法，你的建议）。

我可能在代数上犯了一个错误，但我把a = 77，b = 100的例子输入Wolfram Alpha并得到了180.58，所以这个方法似乎有效。

来源

2016-10-25 14:37:30 strubbly

numpy的整数优化/最大化

回答

相关问题