AI 与工程数学 / 系统课时
用区间缩减定位一维极小值
用区间缩减定位一维极小值
当目标函数的一阶导数难以获得,但能够直接计算函数值时,可以通过不断缩短极小值所在区间来完成搜索。黄金分割法利用固定比例复用已有函数值,在单峰假设成立时,以较少的函数评估逐步逼近一维极小点。
学习目标
- 理解区间缩减依赖的单峰假设,以及每轮为何可以舍弃一部分区间
- 实现黄金分割搜索,并记录区间长度随迭代的变化
- 根据终止精度估算迭代次数和函数评估成本
单峰假设决定能否安全缩区间
设要在闭区间 上最小化函数 。区间缩减方法并不要求导数,但通常要求函数在搜索区间内是单峰的:从左向极小点逐渐下降,越过极小点后逐渐上升。
如果在区间内部选择 ,并且得到 ,在单峰假设下可以判断极小点不可能位于 的右侧,因此把新区间缩为 。反之则保留 。
如果函数在搜索区间内有多个局部极小值,这个推理就可能失效。区间缩减法找到的是当前单峰区间对应的极小值,而不是自动解决任意多峰全局优化问题。
黄金分割如何复用函数值
黄金分割法选取固定比例
并在区间内部设置两个点
每轮比较 与 后舍弃一侧区间。黄金比例的关键价值不是数字本身漂亮,而是新区间中的一个内部点可以直接复用,因此正常情况下每轮只需要新增一次函数评估。

若初始区间长度为 ,连续迭代 次后有近似关系 。因此终止条件设为 时,迭代次数随精度要求呈对数增长,而不是与 成正比。
用代码记录每轮收缩
下面搜索函数 在 上的极小值。实现中保存每轮区间长度,并复用上一轮已经计算过的函数值。
import math
def golden_search(f, a, b, tol=1e-4):
rho = (math.sqrt(5) - 1) / 2
x1 = b - rho * (b - a)
x2 = a + rho * (b - a)
f1, f2 = f(x1), f(x2)
evaluations = 2
lengths = [b - a]
while b - a > tol:
if f1 <= f2:
# 极小点保留在左侧,并复用旧的 x1 与 f1。
b, x2, f2 = x2, x1, f1
x1 = b - rho * (b - a)
f1 = f(x1)
else:
a, x1, f1 = x1, x2, f2
x2 = a + rho * (b - a)
f2 = f(x2)
evaluations += 1
lengths.append(b - a)
return (a + b) / 2, evaluations, lengths
def objective(x):
return (x - 2) ** 2 + 1
x_star, evaluations, lengths = golden_search(objective, -1.0, 5.0)
print(f"x* ≈ {x_star:.4f}")
print(f"f(x*) ≈ {objective(x_star):.8f}")
print(f"迭代次数 = {len(lengths) - 1}")
print(f"搜索函数评估次数 = {evaluations}")
print("前5个区间长度 =", [round(v, 6) for v in lengths[:5]])
print("最终区间 <= 1e-4:", lengths[-1] <= 1e-4)预期输出
x* ≈ 2.0000
f(x*) ≈ 1.00000000
迭代次数 = 23
搜索函数评估次数 = 25
前5个区间长度 = [6.0, 3.708204, 2.291796, 1.416408, 0.875388]
最终区间 <= 1e-4: True这里的函数评估次数只统计搜索过程中用于区间判断的调用;最后打印 的调用没有计入该计数。可以看到区间长度近似按固定比例递减,而不是每轮重新任意选择试探点。
精度与函数评估次数的权衡
若希望 ,可以估算所需迭代次数为
因为 ,分母为负数,但当 时整个比值为正。初始区间越宽或终止精度越严格,需要的迭代次数越多。
实际工程中不要盲目把 tol 设置得极小。若一次函数评估本身很昂贵,应该根据最终变量精度、测量噪声和浮点误差选择合理阈值;当区间长度已经小于业务真正能够区分的尺度时,继续搜索通常只会增加计算成本。