AI 与工程数学 / 系统课时

用区间缩减定位一维极小值

用区间缩减定位一维极小值

当目标函数的一阶导数难以获得,但能够直接计算函数值时,可以通过不断缩短极小值所在区间来完成搜索。黄金分割法利用固定比例复用已有函数值,在单峰假设成立时,以较少的函数评估逐步逼近一维极小点。

学习目标

  • 理解区间缩减依赖的单峰假设,以及每轮为何可以舍弃一部分区间
  • 实现黄金分割搜索,并记录区间长度随迭代的变化
  • 根据终止精度估算迭代次数和函数评估成本

单峰假设决定能否安全缩区间

设要在闭区间 [a,b][a,b] 上最小化函数 f(x)f(x)。区间缩减方法并不要求导数,但通常要求函数在搜索区间内是单峰的:从左向极小点逐渐下降,越过极小点后逐渐上升。

如果在区间内部选择 x1<x2x_1<x_2,并且得到 f(x1)<f(x2)f(x_1)<f(x_2),在单峰假设下可以判断极小点不可能位于 x2x_2 的右侧,因此把新区间缩为 [a,x2][a,x_2]。反之则保留 [x1,b][x_1,b]。

如果函数在搜索区间内有多个局部极小值,这个推理就可能失效。区间缩减法找到的是当前单峰区间对应的极小值,而不是自动解决任意多峰全局优化问题。

黄金分割如何复用函数值

黄金分割法选取固定比例

ρ=5−12≈0.618\rho=\frac{\sqrt{5}-1}{2}\approx 0.618

并在区间内部设置两个点

x1=b−ρ(b−a),x2=a+ρ(b−a)x_1=b-\rho(b-a),\qquad x_2=a+\rho(b-a)

每轮比较 f(x1)f(x_1) 与 f(x2)f(x_2) 后舍弃一侧区间。黄金比例的关键价值不是数字本身漂亮,而是新区间中的一个内部点可以直接复用,因此正常情况下每轮只需要新增一次函数评估。

黄金分割法的区间收缩过程

若初始区间长度为 L0=b−aL_0=b-a,连续迭代 kk 次后有近似关系 Lk=ρkL0L_k=\rho^kL_0。因此终止条件设为 Lk≤εL_k\le\varepsilon 时,迭代次数随精度要求呈对数增长,而不是与 1/ε1/\varepsilon 成正比。

用代码记录每轮收缩

下面搜索函数 f(x)=(x−2)2+1f(x)=(x-2)^2+1 在 [−1,5][-1,5] 上的极小值。实现中保存每轮区间长度,并复用上一轮已经计算过的函数值。

python
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)

预期输出

text
x* ≈ 2.0000
f(x*) ≈ 1.00000000
迭代次数 = 23
搜索函数评估次数 = 25
前5个区间长度 = [6.0, 3.708204, 2.291796, 1.416408, 0.875388]
最终区间 <= 1e-4: True

这里的函数评估次数只统计搜索过程中用于区间判断的调用;最后打印 f(x∗)f(x^*) 的调用没有计入该计数。可以看到区间长度近似按固定比例递减,而不是每轮重新任意选择试探点。

精度与函数评估次数的权衡

若希望 honL0≤εho^nL_0\le\varepsilon,可以估算所需迭代次数为

n≥ln⁡(ε/L0)ln⁡ρn\ge\frac{\ln(\varepsilon/L_0)}{\ln\rho}

因为 0<ρ<10<\rho<1,分母为负数,但当 ε<L0\varepsilon<L_0 时整个比值为正。初始区间越宽或终止精度越严格,需要的迭代次数越多。

实际工程中不要盲目把 tol 设置得极小。若一次函数评估本身很昂贵,应该根据最终变量精度、测量噪声和浮点误差选择合理阈值;当区间长度已经小于业务真正能够区分的尺度时,继续搜索通常只会增加计算成本。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用区间缩减定位一维极小值

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通