寻找凹函数f(x)≥a区间端点的优化算法技术咨询

针对你提到的拥有连续、凹特性的黑箱函数，要以最少步骤找到f(x)≥a的区间端点x0（左端点）和x1（右端点），我整理了对应的算法细节、实现方式以及可用的Python工具，具体如下：

一、算法名称 #

这个问题本质是求解方程f(x) = a的两个实根（因为连续凹函数的上水平集是凸集，在一维空间中就是一个闭区间[x0, x1]）。

如果你的黑箱函数无法提供导数信息，最稳定且高效的算法是二分查找法（对左右端点分别进行查找）——它是确定性算法，每一步都能缩小搜索范围，步骤可控，且不需要额外信息。如果能获取或近似得到函数的导数，牛顿-拉夫逊法（Newton-Raphson Method）的收敛速度会更快，但需要导数支持（黑箱场景下可以用数值导数近似）。

另外，利用凹函数的特性，我们可以先快速定位包含根的初始区间，再进行二分，进一步减少步骤：先找到一个已知满足f(x)≥a的点，然后向左右两侧以加倍步长扩展，直到找到函数值小于a的点，这样就能得到包含x0和x1的初始区间。

二、算法实现步骤 & Python代码 #

1. 核心思路 #

• 先确定包含左端点x0的初始区间：从已知满足f(x)≥a的点向左扩展，找到第一个f(x)<a的点，此时x0在这个点和已知点之间。
• 同理确定包含右端点x1的初始区间：从已知点向右扩展，找到第一个f(x)<a的点，x1在已知点和这个点之间。
• 对两个初始区间分别执行二分查找，直到区间长度小于设定的精度阈值。

2. 手动实现代码 #

def find_left_endpoint(f, a, x_init, step=1.0, tol=1e-6):
    # 快速扩展找到左边界初始区间
    x_left = x_init
    while f(x_left) >= a:
        x_left -= step
        step *= 2  # 加倍步长，快速缩小搜索范围
    # 二分查找精确左端点
    x_right = x_init
    while x_right - x_left > tol:
        x_mid = (x_left + x_right) / 2
        if f(x_mid) >= a:
            x_right = x_mid
        else:
            x_left = x_mid
    return (x_left + x_right) / 2

def find_right_endpoint(f, a, x_init, step=1.0, tol=1e-6):
    # 快速扩展找到右边界初始区间
    x_right = x_init
    while f(x_right) >= a:
        x_right += step
        step *= 2
    # 二分查找精确右端点
    x_left = x_init
    while x_right - x_left > tol:
        x_mid = (x_left + x_right) / 2
        if f(x_mid) >= a:
            x_left = x_mid
        else:
            x_right = x_mid
    return (x_left + x_right) / 2

# 测试用例：凹函数 f(x) = -(x-3)²，找f(x)≥-4的区间端点
def test_f(x):
    return -(x-3)**2

a = -4
x_init = 3  # 已知该点满足f(x)=0≥-4
x0 = find_left_endpoint(test_f, a, x_init)
x1 = find_right_endpoint(test_f, a, x_init)
print(f"左端点x0≈{x0:.6f}，右端点x1≈{x1:.6f}")  # 预期输出：x0≈1.0，x1≈5.0

三、标准Python库支持 #

Python标准库中没有专门针对该场景的函数，但可以使用scipy.optimize模块中的root_scalar函数，它支持多种根查找算法，非常适合这个问题：

• 推荐使用bisect（二分法）方法，只需要函数值，稳定性强，适合黑箱函数。
• 如果能提供导数，也可以使用newton方法，收敛速度更快。

使用scipy的示例代码 #

from scipy.optimize import root_scalar

def test_f(x):
    return -(x-3)**2

a = -4
# 定义目标方程：f(x) - a = 0
target_func = lambda x: test_f(x) - a

# 找左端点x0，需指定包含根的区间（两端函数值异号）
res_left = root_scalar(target_func, bracket=[0, 3], method='bisect')
x0 = res_left.root

# 找右端点x1，同样指定包含根的区间
res_right = root_scalar(target_func, bracket=[3, 6], method='bisect')
x1 = res_right.root

print(f"左端点x0≈{x0:.6f}，右端点x1≈{x1:.6f}")

需要注意的是，使用bisect方法时，必须提供一个包含根的区间，区间两端的目标函数值符号相反（即一端f(x)-a < 0，另一端f(x)-a > 0）。

内容的提问来源于stack exchange，提问作者user7468395