python - 在 Python 中逼近一个未知值

Question

我需要近似一个未知值，一个将发散值与收敛值分开的边界。

我正在尝试这样做:

# dont worry about the value of i, its one of many bounds checks
bounds = 1.0
for j in range(niters):
    if does_converge(i, bound):
        bound += bound / 2.0
    else:
        bound /= 2.0

我一直在谷歌上搜索更好的近似算法，但他们似乎都假设我对函数有所了解，但我不知道。我得到的只是一个黑框，告诉我值是否发散。

如有任何想法，我们将不胜感激!

编辑:我不能肯定地说，但假设函数是连续的，并且收敛的边界很可能在 0 和 1 之间，我会很好。

Answer 1

根据给定的信息，没有什么比某种形式的二分搜索更好的了。

编辑:请参阅此答案末尾的编辑/备注以获得更好的解决方案(尽管没有严格的理论解释)!

这可以使用 scipy 的 minimize_scalar 来实现.使用method: golden 很重要!

Method Golden uses the golden section search technique. It uses analog of the bisection method to decrease the bracketed interval.

问题是没有任何真正有值(value)的答案。只有是/否不允许形成任何类型的梯度信息或代理模型。

我假设:

• 我们正在寻找黑盒返回 1 的最小值
• 黑盒是确定性的

想法: 构建一些包装函数，它在返回 1 的最小值处具有最小值。

由于 x 应该在 [0,1] 中，尝试最小化 x，我们可以将包装函数表示为:x + 1 - black_box(x)。答案为 0 的每个解决方案 >= 答案为 1 的每个解决方案(可能在界限处需要一些保护措施；例如 x + (1 - eps) - black_box(x) eps 非常小!；可能需要在选择时考虑到 xtol)。

代码:

from scipy import optimize

SECRET_VAL = 0.7

def black_box(x):
    if x > SECRET_VAL:
        return 1.
    else:
        return 0.

def wrapper(x):
    return x + 1 - black_box(x)

res = optimize.minimize_scalar(wrapper, bracket=(0,1), method='golden')

print(res)

输出:

     fun: 0.7000000042155881
    nfev: 44
     nit: 39
 success: True
       x: 0.7000000042155881

或者使用secret_val=0.04:

     fun: 0.04000000033008555
    nfev: 50
     nit: 45
 success: True
       x: 0.040000000330085564

或者如果你知道你需要什么样的精度(原始 secret 0.7):

res = optimize.minimize_scalar(wrapper, bracket=(0,1), method='golden',
                            options={'xtol': 1e-2})

输出:

     fun: 0.7000733152965655
    nfev: 16                 !!!!!
     nit: 11
 success: True
       x: 0.7000733152965655

备注:

在这里编写一个自定义的基于二进制搜索的解决方案可能会更好(不是 100% 确定)。但是考虑到缺少单峰性等假设，需要小心。

编辑:好吧...我终于设法将这个最小化问题转化为一个寻根问题，这样可以更有效地解决!

警告:很明显，wrapper 永远不会返回 0.0 的值(找不到确切的根)!

但是二分法是关于新区间内的零交叉 wiki .

因此它在这里找到两个点 a, b，其中函数的 符号 正在改变并将其解释为根(给定一些公差!)。

与前一种方法相比，这种分析不如前一种方法严格(没有给出太多分析，但根据 scipy 的文档，在纯最小化方法中更容易做)。

def wrapper_bisect(x):
    return 1 - 2*black_box(x)

res = optimize.bisect(wrapper_bisect, 0, 1, xtol=1e-2, full_output=True)
print(res)

输出:

(0.6953125,       converged: True
           flag: 'converged'
 function_calls: 9
     iterations: 7
           root: 0.6953125)

鉴于上述假设(并且只有这些假设)，这应该是理论上最优的算法(我们将函数评估的数量从 16 减少到 9；优化目标更差，但在界限)!

最后一个测试:

secret :0.9813； xtol: 1e-4:

金色:

    fun: 0.9813254238281632
    nfev: 25
     nit: 20
 success: True
       x: 0.9813254238291631

二分法:

(0.98126220703125,       converged: True
           flag: 'converged'
 function_calls: 16
     iterations: 14
           root: 0.98126220703125)