CycleUser

引子：怎么找一个单峰函数的极值

给定一个在区间 $[a,b]$ 上先降后升的单峰函数，怎么又快又稳地找到它的极小点？这是数值优化里最基础的一维问题，也是各种高维优化里"线搜索"（line search）步骤的内核。方法有一大把：三分查找、黄金分割、Fibonacci 查找、抛物线插值、Brent、二分/牛顿……

这篇文章把它们放在一起做个综述，全部用同一套基准诚实地量：同样的测试函数、同样的精度、数每种方法花了多少次函数求值，并检查是否都收敛到了正确答案。核心的一条主线是：一个方法用了函数的多少信息，决定了它能有多快，也决定了它的适用范围。

黄金分割"快"在哪：复用点

先从最经典的黄金分割查找（golden section search）说起。很多人以为它的精髓是那个神奇的比率 $\varphi=0.618\dots$，其实不是——精髓是"复用点"。

在区间 $[a,b]$ 放两个内点 $c = b - \varphi(b-a)$、$d = a + \varphi(b-a)$，比较 $f(c)$ 和 $f(d)$，丢掉更差的一端。黄金比率满足自相似性质 $\varphi^2 = 1-\varphi$，使得收缩后的新区间里，旧的一个内点恰好落在新的黄金分割位置。下一轮只需算一个新点，另一个直接复用。

黄金分割每轮只需 1 次新求值

一句话：黄金分割每轮区间收缩到 0.618，但只花 1 次函数求值。 对比之下，三分查找每轮把区间缩到 2/3，看起来比 0.618 更狠，可它两个内点每轮都要重算，每轮花 2 次求值，摊下来反而更亏。这说明衡量快慢不能只看单轮收缩幅度，要看"每次求值能换来多少收缩"。

有限轮数下的最优：Fibonacci 查找

黄金分割的比率是恒定的。有没有可能让比率逐轮变化，既缩得更聪明、又保持复用？

有。用 Fibonacci 数列 $F_n = 1,1,2,3,5,8,13,\dots$ 来定分点。给定精度需要的轮数 $n$，每轮的保留比率取 $F_{n-k}/F_{n-k+1}$。因为 Fibonacci 有递推 $F_{n} = F_{n-1}+F_{n-2}$，这个结构恰好也能复用一个旧点，每轮只算一个新点——和黄金分割一样省，但比率是逐轮变化的：

$$\frac{1}{2},\ \frac{2}{3},\ \frac{3}{5},\ \frac{5}{8},\ \frac{8}{13},\ \frac{13}{21},\dots \longrightarrow \varphi$$

Fibonacci 比率逐轮变化，极限是黄金比率

有意思的是：黄金分割查找其实就是 Fibonacci 查找在 $n\to\infty$ 时的极限——比率不再变化、恒为 $\varphi$。而对有限轮数，Fibonacci 是理论最优的：在"只能比较函数值大小"的框架下，给定固定的求值次数，Fibonacci 能把最终区间压到最小（Kiefer 1953 证明）。

import math
phi = (math.sqrt(5) - 1) / 2

def fibonacci_search(f, a, b, tol=1e-6):
    calls = 0
    def F(x):
        nonlocal calls; calls += 1; return f(x)
    fib = [1, 1]
    while fib[-1] < (b - a) / tol:
        fib.append(fib[-1] + fib[-2])
    n = len(fib) - 1
    c = a + fib[n-2]/fib[n]*(b-a)
    d = a + fib[n-1]/fib[n]*(b-a)
    fc, fd = F(c), F(d)
    for k in range(1, n-1):
        if fc < fd:
            b, d, fd = d, c, fc
            c = a + fib[n-k-2]/fib[n-k]*(b-a)   # 比率逐轮变
            fc = F(c)                            # 但只算 1 个新点
        else:
            a, c, fc = c, d, fd
            d = a + fib[n-k-1]/fib[n-k]*(b-a)
            fd = F(d)
    return (a + b) / 2, calls

上代码，诚实地量所有方法

同一套 8 个单峰测试函数（二次、四次、尖谷、非对称指数、平底等），统一收敛到 $10^{-6}$，数每种方法的函数求值次数，并检查是否收敛正确：

方法	需要什么	每轮求值	合计求值	收敛正确
三分查找	只比大小	2	560	8/8 ✅
黄金分割 GS	只比大小	1	248	8/8 ✅
Fibonacci	只比大小	1	240	8/8 ✅
抛物线插值	用曲率	1	151	8/8 ✅
Brent	用曲率+兜底	1	136	8/8 ✅
二分（需导数）	需梯度	1	120*	6/6 ✅

（*二分需要导数，仅在 6 个可导函数上统计）

各方法总求值次数对比

几个结论一目了然：

三分查找最慢：它不复用，每轮 2 次求值，虽然区间每轮缩到 2/3，但摊下来最亏。
Fibonacci 略胜黄金分割（240 vs 248）：因为它在有限轮数下是最优的，黄金分割只是它的极限近似。
黄金分割是"够用且简单"的选择：不用预先算轮数，实现最短，性能只比最优差一点点。

真正的加速：利用更多信息

黄金分割和 Fibonacci 都只用了 $f(c)<f(d)$ 这一个比较（一个比特），太浪费。想更快，就得用函数值里更多的信息。

抛物线插值（successive parabolic interpolation）用最近三点拟合抛物线，取顶点作为下一个试点：

$$x_{\text{new}} = x_1 - \frac{1}{2}\frac{(x_1-x_0)^2[f_1-f_2] - (x_1-x_2)^2[f_1-f_0]}{(x_1-x_0)[f_1-f_2] - (x_1-x_2)[f_1-f_0]}$$

在光滑函数附近超线性收敛，二次函数上一步到位（表中"二次"只用 5 次）。但它对尖谷、平底会失灵（"平底四次"用了 54 次，比黄金分割还慢）。

Brent 方法是工程上的标准答案：能抛物线插值就插值，插值越界或不老实就退回黄金分割兜底。既拿到插值的快，又保住黄金分割的稳，8 个函数只用 136 次，全部收敛正确。这也是 scipy.optimize.minimize_scalar 默认用的方法。

如果能拿到导数，那就更快：极值点等价于导数的零点，直接对导数做二分（120 次），甚至用牛顿法，但代价是必须有梯度。

方法家族全景

把这些方法按"用了多少信息"排一下，脉络就清楚了：信息用得越多，收敛越快，但对函数的要求也越高。

一维查找方法家族关系

只比函数值大小（最通用，连不可导、有噪声都能用）：三分 → 黄金分割 → Fibonacci（最优）。
还用函数值的具体数值（曲率）：抛物线插值 → Brent（插值+兜底）。
还能用导数：二分（导数符号）→ 牛顿法（导数值），最快但要求最苛刻。

三种区间法同屏对比

最后放一个动画，让三分、黄金分割、Fibonacci 在同一个函数上同屏收缩。三分的区间每轮缩得多但费两次求值；黄金分割和 Fibonacci 缩得稳，且每轮只花一次。

三分、黄金分割、Fibonacci 收缩过程对比

小结

黄金分割查找的精髓是复用点：每轮收缩到 0.618，只花 1 次求值；三分不复用，所以更慢。
想在保持复用的同时让比率变得更聪明，正确做法是 Fibonacci 查找：比率逐轮变化（0.5→0.667→0.6→…→φ）却仍复用一点，且在有限轮数下理论最优。黄金分割正是它 $n\to\infty$ 的极限。
真想更快，方向是用函数值里更多的信息：抛物线插值（用曲率）→ Brent（插值+黄金兜底，工程首选）；若有导数，二分/牛顿更快，但要求更高。
选型口诀：通用稳妥用 Brent，纯比较场景用黄金分割/Fibonacci，有梯度就上牛顿。