3、单变量无约束优化：黄金分割法原理与实现

说到一维搜索，很多初学者第一反应就是求导。但现实哪有那么理想？我在项目中遇到过好几次，目标函数根本没法求导，或者导数计算代价高得离谱。这时候，黄金分割法就派上用场了。

说白了，黄金分割法就是一种不依赖导数的区间收缩方法。它只靠比较函数值的大小，就能一步步逼近极小点。你想想看，这多实用？

3.1 黄金分割法的核心思想

它的思路其实很朴素：

• 在一个已知的区间 [a, b] 内，函数是单峰的（只有一个极小点）
• 我们在区间内插两个点，比较它们的函数值
• 根据比较结果，扔掉一部分区间，保留包含极小点的那一段
• 不断重复，直到区间足够小

嗯，这里要注意：两个插入点的位置不是随便选的。黄金分割法用了一个神奇的比例——0.618，也就是黄金分割比 φ ≈ 1.618 的倒数。

3.2 算法步骤详解

我个人习惯把流程拆成 5 步，这样写代码时不容易乱：

1. 初始化：给定初始区间 [a, b] 和精度 ε
2. 插点：计算两个内点
   • x₁ = a + 0.382 × (b - a)
   • x₂ = a + 0.618 × (b - a)
3. 比较：计算 f(x₁) 和 f(x₂)
   • 如果 f(x₁) < f(x₂)，极小点在 [a, x₂]，令 b = x₂
   • 如果 f(x₁) > f(x₂)，极小点在 [x₁, b]，令 a = x₁
4. 收缩：新区间长度变为原来的 0.618 倍
5. 判断：如果 |b - a| < ε，输出 (a+b)/2；否则回到第 2 步

3.3 黄金分割法的流程图

下面这张图把整个流程串起来了，建议你对照着看：

3.4 代码实现

下面是我写的一个 Python 实现。代码不长，但该有的细节都有了：

def golden_section_search(f, a, b, eps=1e-6, max_iter=100):
    """
    黄金分割法求解单峰函数极小点
    
    参数:
        f: 目标函数
        a, b: 初始区间
        eps: 精度要求
        max_iter: 最大迭代次数
    
    返回:
        x_opt: 极小点近似值
        iter_count: 实际迭代次数
    """
    # 黄金分割比例
    phi = (1 + 5**0.5) / 2  # ≈ 1.618
    tau = 1 / phi           # ≈ 0.618
    
    # 初始化两个内点
    x1 = a + (1 - tau) * (b - a)  # 0.382 位置
    x2 = a + tau * (b - a)        # 0.618 位置
    
    f1 = f(x1)
    f2 = f(x2)
    
    iter_count = 0
    
    while (b - a) > eps and iter_count < max_iter:
        iter_count += 1
        
        if f1 < f2:
            # 极小点在 [a, x2]
            b = x2
            x2 = x1
            f2 = f1
            # 计算新的 x1
            x1 = a + (1 - tau) * (b - a)
            f1 = f(x1)
        else:
            # 极小点在 [x1, b]
            a = x1
            x1 = x2
            f1 = f2
            # 计算新的 x2
            x2 = a + tau * (b - a)
            f2 = f(x2)
    
    x_opt = (a + b) / 2
    return x_opt, iter_count

3.5 收敛性与精度分析

黄金分割法的收敛速度是线性的，收敛比约为 0.618。什么意思？每次迭代区间长度缩小到原来的 0.618 倍。

举个例子：

迭代次数	区间长度（初始为 1）	精度提升
0	1.000	-
5	0.090	约 11 倍
10	0.008	约 125 倍
15	0.0007	约 1429 倍
20	0.00006	约 16667 倍

你看，10 次迭代就能把区间缩小 100 多倍。对于大多数工程问题，这个精度已经够用了。

3.6 适用场景与局限性

我总结了一下，黄金分割法最适合下面这些情况：

• 函数不可导：比如有噪声、不光滑的目标函数
• 导数计算太贵：每次求导要跑仿真，算不起
• 函数是单峰的：区间内只有一个极小点
• 精度要求中等：不需要高精度，10⁻⁶ 左右就够了

但也要注意它的短板：

• 收敛速度比牛顿法慢（人家是二次收敛）
• 对多峰函数无效（会收敛到局部极小）
• 初始区间必须包含极小点