整数优化/最大化

Question

我需要estimate一个总体的大小，通过找到使scipy.misc.comb(n, a)/n**b最大化的n值，其中a和{}是常量。n、a和{}都是整数。在

显然，我可以在range(SOME_HUGE_NUMBER)中有一个循环，计算每个n的值，并在曲线中到达拐点时脱离循环。但我想知道是否有一种优雅的方法可以用（比如）numpy/scipy来实现，还是有其他一些优雅的方法可以在纯Python中实现（例如，牛顿方法的整数等价物？）在

Answer 1

实际上，你有一个很好的平滑函数n，你想最大化它。n必须是整数，但我们可以将该函数视为实数的函数。在这种情况下，n的最大整数值必须接近（紧挨着）最大化实数值。在

我们可以使用伽马函数将{}转换为实函数，并使用数值优化技术来寻找最大值。另一种方法是用斯特林近似代替阶乘。这给出了一个中等复杂但容易处理的代数表达式。这个表达式不难区分，设置为零就可以找到极值。在

我这样做了，得到了

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

用代数方法求解并不简单，但在数值上却很容易（如你所建议的，使用牛顿法）。在

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

Answer 2

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

^{pr2}$

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