4、单变量无约束优化：斐波那契法原理与实现
聊到单变量无约束优化，很多人第一反应就是黄金分割法。但说实话，在精度要求极高的情况下，黄金分割法并不是最优解。今天我要讲的斐波那契法，才是真正能把区间压缩到极限的“精确制导武器”。
我在做某个精密仪器的参数校准时遇到过这么个场景：目标函数计算一次要跑 20 分钟，总共只能跑 30 次。黄金分割法算下来误差总差那么一点点，换用斐波那契法之后，刚好卡在允许的误差范围内。嗯，从那以后我就记住了——函数求值次数固定时，斐波那契法就是理论最优。
4.1 斐波那契法的核心思想
斐波那契法的思路其实很朴素：在总求值次数 N 固定的前提下，每一步的区间压缩比都按斐波那契数列来动态调整。你想想看，黄金分割法每一步的压缩比都是 0.618，固定不变；而斐波那契法每一步的压缩比都在变，越到后面压缩得越狠。
为什么会这样？因为斐波那契法知道“终点在哪里”。它提前算好了总共能求几次函数值，然后像倒计时一样，把最猛的压缩留到最后几步。说白了，这是一种全局最优的区间收缩策略。
核心结论：给定相同的函数求值次数 N，斐波那契法能达到的最终区间长度是黄金分割法的 1.17 倍左右。换句话说，斐波那契法更短、更准。
4.2 斐波那契数列与压缩比
先回顾一下斐波那契数列的定义：
F₀ = 0, F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂, n ≥ 2前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
在斐波那契法中，第 k 步的压缩比 ρₖ 是这样算的：
| 步骤 k | 压缩比 ρₖ | 说明 |
|---|---|---|
| 1 | Fₙ₋₁ / Fₙ | 第一步压缩比最大 |
| 2 | Fₙ₋₂ / Fₙ₋₁ | 逐步递减 |
| … | … | … |
| k | Fₙ₋ₖ / Fₙ₋ₖ₊₁ | 越往后压缩越猛 |
| N-1 | F₁ / F₂ = 1/2 | 最后一步压缩到一半 |
注意看，最后一步的压缩比是 1/2，而黄金分割法最后一步还是 0.618。这就是斐波那契法更精确的原因——它把“弹药”集中在了最后几轮。
4.3 算法流程
我个人习惯把斐波那契法的流程拆成三步：
- 预计算阶段：根据目标精度 ε 和初始区间长度 L₀，反推出最少需要的求值次数 N。
- 初始化阶段：在区间内放置两个对称的试探点，计算函数值。
- 迭代收缩阶段：每次比较两个试探点的函数值，缩小区间，并利用斐波那契数列计算下一个试探点的位置。
具体来说，假设初始区间为 [a, b]，总求值次数为 N：
第 1 步：计算两个试探点
x₁ = a + (Fₙ₋₂ / Fₙ) × (b - a)
x₂ = a + (Fₙ₋₁ / Fₙ) × (b - a)
第 2 步：比较 f(x₁) 和 f(x₂)
如果 f(x₁) < f(x₂)：新区间为 [a, x₂]
如果 f(x₁) > f(x₂)：新区间为 [x₁, b]
第 3 步：利用对称性，只需再计算一个新试探点
例如新区间为 [a, x₂]，则 x₁ 成为新的 x₂，只需计算新的 x₁这里有个关键点：每次迭代只需要新算一个函数值，另一个试探点是从上一轮继承下来的。这就是斐波那契法效率高的原因之一。
我的经验：在实际编码时，建议先把斐波那契数列预计算好存成数组，不要在迭代过程中递归计算。我曾经踩过这个坑——递归算斐波那契数列的时间复杂度是 O(2ⁿ)，N 稍微大一点就直接卡死了。
4.4 代码实现
下面是我写的一个 Python 实现，注释写得比较详细：
def fibonacci_search(f, a, b, n):
"""
斐波那契法求解单变量无约束优化问题
参数:
f: 目标函数
a, b: 初始区间
n: 总函数求值次数
返回:
x_opt: 最优解近似值
f_opt: 最优函数值
"""
# 预计算斐波那契数列
fib = [0, 1]
for i in range(2, n + 2):
fib.append(fib[i-1] + fib[i-2])
# 初始化试探点
x1 = a + (fib[n-2] / fib[n]) * (b - a)
x2 = a + (fib[n-1] / fib[n]) * (b - a)
f1, f2 = f(x1), f(x2)
# 迭代收缩
for k in range(1, n):
if f1 < f2:
# 缩小区间到 [a, x2]
b = x2
x2 = x1
f2 = f1
x1 = a + (fib[n-k-2] / fib[n-k]) * (b - a)
f1 = f(x1)
else:
# 缩小区间到 [x1, b]
a = x1
x1 = x2
f1 = f2
x2 = a + (fib[n-k-1] / fib[n-k]) * (b - a)
f2 = f(x2)
# 返回区间中点作为最优解
x_opt = (a + b) / 2
return x_opt, f(x_opt)注意：代码中 fib[n-k-2] 和 fib[n-k-1] 的下标计算很容易写错。我曾经在这里 debug 了整整一个下午，最后发现是索引偏移了一位。建议你在写的时候，先用小规模数据（比如 n=5）手算一遍，再对照代码验证。
4.5 与黄金分割法的对比
很多同学会问：既然斐波那契法更优，为什么市面上黄金分割法更流行？
原因很简单：黄金分割法不需要预先知道求值次数。你可以一直迭代下去，直到满足精度为止。而斐波那契法必须提前定好 N，一旦 N 定小了，精度就不够；定大了，又浪费计算资源。
下面这个表格可以帮你快速对比：
| 对比维度 | 斐波那契法 | 黄金分割法 |
|---|---|---|
| 压缩比 | 动态变化，最后达 1/2 | 固定 0.618 |
| 最终区间长度 | L₀ / Fₙ | L₀ × 0.618ⁿ⁻¹ |
| 是否需要预知 N | 是 | 否 |
| 理论最优性 | 是（给定 N 时） | 否 |
| 适用场景 | 函数求值成本极高 | 通用场景 |
我个人建议：如果你能提前估算出最多能算多少次函数值，就用斐波那契法；如果不知道，或者想随时停下来，就用黄金分割法。
4.6 知识结构图
下面这张图帮你理清斐波那契法的整体脉络：
4.7 避坑指南
最后，分享几个我在实际项目中踩过的坑：
- N 的取值问题：N 不能太小，否则区间压缩不够。我一般用公式 N ≥ log₁.₆₁₈(L₀ / ε) 来估算下限，然后向上取整到最近的斐波那契数。
- 浮点数精度：当 N 较大时（比如 N > 40），斐波那契数会超过 2³²，用 32 位整数会溢出。建议用 Python 的大整数或浮点数。
- 函数值相等的情况：如果 f(x₁) == f(x₂)，理论上可以任意缩小区间。但我建议统一缩到 [x₁, x₂]，这样代码更简洁，也不会出错。
- 最后一步的处理：迭代到第 N-1 步时，两个试探点会非常接近。这时候直接取中点作为最优解即可，不需要再算函数值了。
嗯，斐波那契法就讲到这里。它的原理不复杂，但实现细节确实容易出问题。建议你动手写一遍代码，跑几个测试函数感受一下。相信我，当你看到它比黄金分割法多压缩那 17% 的区间时，会有一种“赚到了”的快感。