numpy 中的整数 optimization/maximization

Question

我需要 estimate 人口规模，方法是找到使 scipy.misc.comb(n, a)/n**b 最大化的 n 值，其中 a 和 b 是常量。 n、a 和 b 都是整数。

显然，我可以在 range(SOME_HUGE_NUMBER) 中创建一个循环，计算每个 n 的值，并在曲线出现拐点时跳出循环。但是我想知道是否有一种优雅的方式使用（比如）numpy/scipy 来做到这一点，或者是否有其他一些优雅的方式来做到这一点只是在纯 Python 中（例如像牛顿方法的整数等效？ )

Answer 1

只要您的数字 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 整数的问题。即使有了它们，您也无法计算：

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

因为您想在两个数字的除法中得到一个浮点数，结果大于 python 中的 float 可以容纳的最大值（max_10_exp = 1024 在我的系统上。参见 sys.float_info().)。在那种情况下，您也不能使用 range。如果你真的想做那样的事情，你将不得不在数字上更加小心。

Answer 2

你基本上有一个你想要最大化的 n 的平滑函数。 n 必须是整数，但我们可以将该函数视为实数函数。在这种情况下，n 的最大积分值必须接近（接近）最大实数值。

我们可以使用伽玛函数将 comb 转换为实函数，并使用数值优化技术找到最大值。另一种方法是用斯特林近似代替阶乘。这给出了一个适度复杂但易于处理的代数表达式。这个表达式不难区分，置零求极值。

我这样做并获得了

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

这在代数上并不简单，但在数值上很容易解决（例如，如您所建议的，使用牛顿法）。

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

numpy 中的整数 optimization/maximization

Integer optimization/maximization in numpy

python

numpy

mathematical-optimization