逼近 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

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

编辑： 请参阅本答案末尾的 edit/remark 以获得更好的解决方案（尽管没有严格的理论解释）！

这可以使用 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.

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

我假设：

我们正在寻找黑盒 returns 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

或者如果你知道你需要什么样的精度（原始秘密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 的值（找不到确切的根）！

但是二分法是关于 zero crossing within the new interval 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；优化-objective 更差，但在范围内）！

最后一个测试：

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)

逼近 Python 中的未知值

Approximating an unknown value in Python

python

algorithm

optimization

mathematical-optimization

numerical-methods