1. 黄金搜索算法到底在搜什么第一次看到黄金搜索算法这个词很多人会误以为是什么搜索引擎的排序策略或者某个电商平台的商品推荐机制。其实它跟这些都没关系。黄金搜索算法是一类基于黄金分割比例约0.618进行区间收缩的数值优化方法核心用途是在一个已知的单峰函数区间内快速逼近极值点。说白了就是当你面对一个碗状或山峰状的函数想知道它的最低点或最高点在哪里但又不想或不能求导、不想暴力遍历时黄金搜索算法就是一把非常好用的尺子。它的适用场景非常具体目标函数不可导、求导成本极高、或者根本写不出解析表达式但你可以在任意点采样得到函数值。比如调参时那个训练轮数 vs 验证集准确率的曲线比如某个物理仿真里某个结构参数 vs 能耗的关系只要它在搜索区间内是单峰的黄金搜索就能用极少的采样次数把极值点锁定到很高精度。这篇文章我会从算法原理、手算过程、代码实现、精度与迭代次数的取舍、常见踩坑几个角度把黄金搜索算法讲透。适合正在学数值优化的大学生、需要做参数寻优的工程师以及想搞懂0.618这个数字到底从哪来的人。读完你不仅能自己写出实现还能判断什么时候该用它、什么时候该换别的算法。2. 为什么是0.618而不是0.52.1 从三分法到黄金分割的进化要理解黄金搜索先看一个更朴素的想法三分搜索。假设区间是 [a, b]我在里面取两个点 x1、x2把区间分成三段比较 f(x1) 和 f(x2)然后丢掉不可能包含极值的那一段。这个思路没错但三分法有个问题每次迭代要重新计算两个新点采样成本高。黄金搜索的聪明之处在于它让每次迭代只需要新增一个采样点另一个点可以复用上一轮的结果。这就像你切蛋糕切一刀之后其中一块的形状和原来那块是相似的可以继续用同样的比例切下去。这个相似的比例正是黄金分割比。设区间长度为 L我们取两个对称的点把区间分成三段左边一段长 x中间一段长 y右边一段长 x。为了能复用我们希望丢掉一段后剩下的区间里原来的某个点仍然处于相同的相对位置。这个条件推导下来会得到一个方程x / y L / x令 L x y代入整理得到 x² y(xy)两边除以 y²设 t x/y则 t² t 1解出 t (1√5)/2 ≈ 1.618取倒数就是 0.618。这就是黄金分割比的来源也是算法名字的由来。2.2 复用点带来的效率优势这个复用到底省了多少我们算一笔账。假设要把区间精度收缩到原来的 1/1000也就是需要约 10 次有效收缩因为 0.618 的 10 次方约等于 0.008。三分法每次迭代算 2 个新点10 次迭代约 20 次函数求值。黄金搜索第一次算 2 个点之后每次只算 1 个新点10 次迭代约 11 次函数求值。看起来只差了一倍但如果你的单次函数求值需要跑一次几分钟的仿真这个差距就是几十分钟和十几分钟的区别。在工程优化里函数求值次数往往就是真金白银的成本这也是黄金搜索至今仍被广泛使用的原因。注意黄金搜索的前提是函数在区间内单峰。如果函数有多个局部极值黄金搜索可能收敛到其中一个局部极值而不是全局极值。这一点后面会专门讲怎么判断和处理。2.3 和其他一维搜索方法的对比方法是否需导数每次迭代新增求值收敛速度适用场景黄金搜索否1 次线性比率0.618单峰、不可导、求值贵三分搜索否2 次线性比率2/3单峰、实现简单斐波那契搜索否1 次线性理论最优已知迭代次数上限牛顿法需要二阶导1 次二次收敛函数光滑、可导梯度下降需要一阶导1 次线性/次线性高维、可导从表里能看出来黄金搜索的定位很清晰不需要导数、每次只加一个点、实现简单。斐波那契搜索在理论上比黄金搜索更优在固定迭代次数下区间收缩最快但黄金搜索不需要预先知道迭代次数比例固定写起来更省心所以实际工程里黄金搜索的出场率反而更高。3. 手把手推一遍迭代过程3.1 初始化两个内点的位置怎么算假设我们要在区间 [a, b] [0, 10] 上找函数 f(x) (x-3)² 1 的最小值。这个函数的最小值显然在 x3我们用它来验证算法。黄金分割比取 φ 0.618更精确地说是 (√5-1)/2 ≈ 0.6180339887。两个内点的位置x1 b - φ * (b - a) 10 - 0.618 * 10 3.82 x2 a φ * (b - a) 0 0.618 * 10 6.18计算函数值f(3.82) (3.82-3)² 1 0.6724 1 1.6724 f(6.18) (6.18-3)² 1 10.1124 1 11.1124因为 f(x1) f(x2)说明最小值在 [a, x2] 这一侧所以新区间变成 [0, 6.18]同时原来的 x13.82 可以复用为新的 x2。3.2 第二轮复用点如何更新新区间 [0, 6.18]长度 6.18。原来的 x13.82 现在应该作为新的 x2 吗我们验证一下新 x2 按公式应该是 a φ*(b-a) 0 0.618*6.18 3.819和 3.82 几乎一致差异来自四舍五入。所以确实可以复用。新的 x1 b - φ*(b-a) 6.18 - 0.618*6.18 2.36。计算 f(2.36) (2.36-3)² 1 0.4096 1 1.4096。比较 f(2.36)1.4096 和 f(3.82)1.6724前者更小所以最小值在 [0, 3.82]新区间 [0, 3.82]复用 x12.36 作为新 x2。3.3 完整迭代表格继续迭代我整理成表格方便对照迭代区间 [a,b]x1x2f(x1)f(x2)保留区间1[0, 10]3.826.181.67211.112[0, 6.18]2[0, 6.18]2.363.821.4101.672[0, 3.82]3[0, 3.82]1.462.361.3721.410[1.46, 3.82]4[1.46, 3.82]2.362.921.4101.006[2.36, 3.82]5[2.36, 3.82]2.923.261.0061.068[2.36, 3.26]6[2.36, 3.26]2.702.921.0901.006[2.70, 3.26]到第 6 轮区间已经收缩到 [2.70, 3.26]长度 0.56中点约 2.98离真实最小值 3 已经很近了。可以看到每轮区间长度乘以 0.618收缩非常稳定。提示手算时建议保留 4 位小数因为黄金分割比本身是无理数过早四舍五入会累积误差导致复用点位置对不上。4. 代码实现与工程化细节4.1 最小可运行版本先用 Python 写一个最朴素的版本把逻辑跑通import math def golden_section_search(f, a, b, tol1e-6, max_iter1000): phi (math.sqrt(5) - 1) / 2 # 0.6180339887... x1 b - phi * (b - a) x2 a phi * (b - a) f1, f2 f(x1), f(x2) for i in range(max_iter): if abs(b - a) tol: break if f1 f2: b x2 x2, f2 x1, f1 x1 b - phi * (b - a) f1 f(x1) else: a x1 x1, f1 x2, f2 x2 a phi * (b - a) f2 f(x2) return (a b) / 2, (a b) / 2, i 1这段代码里有个关键点复用点的时候函数值也要一起搬过去不能只搬坐标。我见过有人只更新了 x1、x2 却忘了 f1、f2结果每轮都多算一次函数白白浪费了黄金搜索最大的优势。4.2 收敛判据怎么选上面用的是区间长度abs(b-a) tol作为停止条件。这是最常用的判据但工程里还有几种选择区间长度判据b - a tol简单直观适合对自变量精度有要求的场景。函数值变化判据abs(f1 - f2) tol适合关心目标值精度、对自变量精度不敏感的场景。相对精度判据(b - a) / max(abs(a), abs(b)) tol适合区间量级差异大的情况。我个人的经验是如果函数值量级很大比如上百万用绝对区间长度判据更稳如果自变量本身很小比如 1e-3 量级用相对判据更合理。选错判据可能导致要么迭代次数爆炸要么精度不够。4.3 迭代次数与精度的定量关系黄金搜索每轮区间收缩比固定为 0.618所以迭代 n 次后区间长度是初始长度的 0.618ⁿ 倍。反过来如果要求精度达到 ε需要的迭代次数是n ceil( log(ε / L0) / log(0.618) )举个例子初始区间长度 L0 10要求精度 ε 1e-6n ceil( log(1e-7) / log(0.618) ) ceil( -16.118 / -0.481 ) ceil(33.5) 34也就是约 34 次迭代总共约 35 次函数求值。这个数字可以提前算出来方便你评估这个优化跑一次要多久。如果单次求值要 1 秒那就是 35 秒可以接受如果要 1 小时那就要考虑换更高效的方法或者降低精度要求。目标精度初始区间10初始区间1初始区间1001e-318 次14 次22 次1e-634 次29 次38 次1e-949 次44 次53 次从表里能看出一个规律精度每提高 1000 倍迭代次数大约增加 15 次。这个增长是对数级的非常温和所以黄金搜索在追求高精度时也不会突然变得不可用。5. 单峰假设被打破时会发生什么5.1 多峰函数的典型翻车现场黄金搜索最容易被忽视的前提就是单峰性。我拿一个双峰函数试过f(x) sin(x) 0.3*sin(3x)在 [0, 6] 上有多个局部极值。用黄金搜索跑结果完全取决于初始区间和函数形状有时候收敛到第一个峰有时候收敛到第二个峰而且算法本身不会报错它会安安静静地给你一个局部最优解让你误以为找到了全局最优。这是最危险的地方算法不报错但答案是错的。在调参场景里这意味着你可能错过了一个更好的参数组合却浑然不知。5.2 怎么判断函数是否单峰实际工程里判断单峰性有几个实用手段先粗扫一遍在区间内均匀取 20~50 个点画出函数值曲线肉眼看是否有多个峰谷。这一步成本很低但能避免大部分翻车。多起点跑多次把区间分成几段每段分别跑黄金搜索比较结果。如果不同段给出不同的极值点说明函数多峰。结合先验知识如果目标函数来自某个物理过程通常能从机理上判断它是否单峰。比如误差平方和类目标函数在参数空间里往往是单峰的。注意如果确认是多峰函数黄金搜索只能作为局部搜索使用需要配合网格搜索、随机重启、或者模拟退火等全局策略。不要指望黄金搜索自己跳出局部最优。5.3 区间端点处极值的处理还有一种边界情况极值恰好落在区间端点上。比如 f(x) x² 在 [0, 10] 上最小值在 x0。黄金搜索的内点永远在区间内部它会把区间不断向 0 收缩但永远取不到 0最后返回一个非常接近 0 的小正数。这在数学上没问题精度足够时误差可忽略但如果你的业务逻辑要求必须精确取到端点就需要额外判断迭代结束后比较端点值和内点值取最小的那个。这个细节很多教程不讲但实际用的时候不加这一步可能会在边界场景下得到偏差较大的结果。6. 实战中的参数取舍与踩坑记录6.1 精度设太高反而出问题我踩过一个坑把 tol 设成 1e-12结果程序跑了很久还没停。原因是浮点数精度极限。当区间长度小到 1e-16 量级时b - a的计算会因为浮点舍入误差而失去意义x1 和 x2 可能算出来相等导致死循环或者结果抖动。经验值是双精度浮点数下tol 不要小于 1e-10。如果确实需要更高精度应该换用更高精度的数值类型或者改用解析方法。盲目追求极小 tol 是新手常见误区。6.2 函数求值有噪声时的应对如果目标函数带随机噪声比如每次调用返回的值有波动黄金搜索的比较步骤f1 f2会变得不可靠。噪声可能让算法误判方向把本该保留的区间丢掉。应对办法有两个一是对每个点多次求值取平均降低噪声影响二是改用容忍度比较比如f1 f2 - delta才认为 f1 更小其中 delta 是噪声量级。第二种方法更省求值次数但 delta 的选取需要一点经验一般取噪声标准差的 1~2 倍。6.3 和网格搜索的配合策略在实际调参里我很少单独用黄金搜索更常见的组合是先用网格搜索粗定位再用黄金搜索精修。网格搜索负责排除多峰干扰、找到大致的最优区间黄金搜索负责在这个小区间里快速逼近。这样既避免了黄金搜索陷入局部最优又避免了网格搜索精度不够的问题。具体做法在参数范围里均匀取 10~20 个点找到函数值最小的那个点以它为中心、左右各取一个网格间距作为新的搜索区间然后交给黄金搜索。这个组合策略在我做过的几个参数寻优任务里都很稳。6.4 一个容易忽略的初始化细节初始化时 x1 和 x2 的计算公式不同资料写法略有差异有的用x1 a (1-φ)(b-a)有的用x1 b - φ(b-a)。这两个式子在数学上等价但浮点计算下可能产生微小差异。如果代码里初始化和迭代更新用了不一致的公式复用点就可能对不上导致每轮多算一次函数。我的建议是初始化和迭代更新统一用同一套公式要么都用b - φ(b-a)和a φ(b-a)要么都用a (1-φ)(b-a)和a φ(b-a)不要混用。7. 黄金搜索在更大框架里的位置黄金搜索虽然是个一维算法但它的思想经常被用在更高维的优化里。比如坐标下降法就是每次固定其他维度、只对一个维度做一维搜索而这一维搜索就可以用黄金搜索来完成。再比如线性搜索在梯度下降的每一步确定步长时黄金搜索也是一个可选方案虽然实践中更常用 Armijo 等基于导数的准则。它的局限也很明确只适合一维、单峰、求值成本可接受的场景。维度一高黄金搜索就无能为力了这时候要考虑 Nelder-Mead、贝叶斯优化等方法。但反过来说正因为它的适用面窄它在自己擅长的场景里表现得非常可靠——实现简单、不需要导数、收敛稳定、迭代次数可预测这些优点让它在工程实践中一直有一席之地。我自己在做仿真参数标定时如果确认目标函数是单峰的第一反应就是上黄金搜索通常几十次仿真就能把参数精度做到 1e-4 以内比手动试凑快太多了。真正需要警惕的不是算法本身而是用之前有没有确认单峰性、用之后有没有检查结果是否落在合理范围内。把这两步做到位黄金搜索就是一个非常省心的工具。
