每日算法 — 使用java实现黄金分割比：黄金分割搜索与单峰函数极值查找

引言

在优化问题中，寻找单峰函数的极值是一项基础而重要的任务。与二分搜索类似，黄金分割搜索（Golden Section Search）通过不断缩小区间来逼近最优解，但它不需要计算导数，仅依靠函数值比较即可工作。其核心思想源自神秘的黄金分割比 $\phi \approx 1.618$，这一比例保证了每次迭代区间收缩的效率最优。

本文将用Java实现黄金分割搜索算法，并与三分搜索进行对比分析，帮助读者理解这一优雅算法的数学原理与工程实践。

算法原理

黄金分割比的由来

黄金分割比 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ 满足性质：

$$\frac{1}{\phi} = \phi – 1 \approx 0.618$$

在搜索区间 $[l, r]$ 内，我们选取两个内点 $m_1$ 和 $m_2$，使得：

$$m_1 = r – \frac{r-l}{\phi}, \quad m_2 = l + \frac{r-l}{\phi}$$

这两个点关于区间中点对称，且满足区间 reuse 性质：无论舍弃哪一侧，剩余区间内的内点都可以被下一次迭代复用，仅需计算一个新点的函数值。

与三分搜索的对比

黄金分割搜索在函数计算代价较高时优势明显，因为它每轮仅需一次新的函数求值。

Java实现

import java.util.function.DoubleFunction;

/**
 * 黄金分割搜索算法实现
 * 用于在单峰函数区间上寻找极值点
 */
public class GoldenSectionSearch {

    // 黄金分割比 phi = (1 + sqrt(5)) / 2
    private static final double PHI = (1.0 + Math.sqrt(5.0)) / 2.0;
    // 黄金分割比的倒数 resphi = 2 - phi = 1 / phi ≈ 0.618
    private static final double RESPHI = 2.0 - PHI; // ≈ 0.6180339887

    /**
     * 寻找单峰函数在区间[a, b]上的最大值点
     * @param f 目标函数
     * @param a 区间左端点
     * @param b 区间右端点
     * @param eps 精度阈值
     * @return 最大值点的近似坐标
     */
    public static double findMax(DoubleFunction<Double> f, double a, double b, double eps) {
        // 初始内点
        double c = a + RESPHI * (b - a);
        double d = a + (1 - RESPHI) * (b - a); // 或使用 b - RESPHI * (b - a)

        // 实际上更对称的写法：
        // c = b - (b - a) / PHI = a + RESPHI * (b - a)
        // d = a + (b - a) / PHI = b - RESPHI * (b - a)
        // 但为了保证 c < d，我们使用标准形式

        return findMaxRecursive(f, a, b, c, f.apply(c), d, f.apply(d), eps);
    }

    private static double findMaxRecursive(DoubleFunction<Double> f, 
                                            double a, double b, 
                                            double c, double fc, 
                                            double d, double fd, 
                                            double eps) {
        // 当区间足够小时返回中点
        if (Math.abs(b - a) < eps) {
            return (a + b) / 2.0;
        }

        if (fc > fd) {
            // 最大值在 [a, d] 区间内，舍弃 [d, b]
            // 复用 c 点作为新的 d 点
            double newB = d;
            double newD = c;
            double newFd = fc;
            double newC = a + RESPHI * (newB - a);
            double newFc = f.apply(newC);
            return findMaxRecursive(f, a, newB, newC, newFc, newD, newFd, eps);
        } else {
            // 最大值在 [c, b] 区间内，舍弃 [a, c]
            // 复用 d 点作为新的 c 点
            double newA = c;
            double newC = d;
            double newFc = fd;
            double newD = newA + (1 - RESPHI) * (b - newA);
            double newFd = f.apply(newD);
            return findMaxRecursive(f, newA, b, newC, newFc, newD, newFd, eps);
        }
    }

    /**
     * 寻找单峰函数在区间[a, b]上的最小值点（迭代版本）
     */
    public static double findMinIterative(DoubleFunction<Double> f, double a, double b, double eps) {
        double c = a + RESPHI * (b - a);
        double d = a + (1 - RESPHI) * (b - a);
        double fc = f.apply(c);
        double fd = f.apply(d);

        while (Math.abs(b - a) > eps) {
            if (fc < fd) { // 找最小值，保留fc较小的一侧
                b = d;
                d = c;
                fd = fc;
                c = a + RESPHI * (b - a);
                fc = f.apply(c);
            } else {
                a = c;
                c = d;
                fc = fd;
                d = a + (1 - RESPHI) * (b - a);
                fd = f.apply(d);
            }
        }
        return (a + b) / 2.0;
    }

    /**
     * 对比测试：黄金分割搜索 vs 三分搜索
     */
    public static double ternarySearch(DoubleFunction<Double> f, double a, double b, double eps) {
        while (Math.abs(b - a) > eps) {
            double m1 = a + (b - a) / 3.0;
            double m2 = b - (b - a) / 3.0;
            if (f.apply(m1) < f.apply(m2)) {
                a = m1;
            } else {
                b = m2;
            }
        }
        return (a + b) / 2.0;
    }

    public static void main(String[] args) {
        // 测试函数1：f(x) = -x^2 + 4x + 5，在[0, 5]上的最大值应在 x=2
        DoubleFunction<Double> f1 = x -> -x * x + 4 * x + 5;

        // 测试函数2：f(x) = sin(x)，在[0, PI]上的最大值应在 x=PI/2
        DoubleFunction<Double> f2 = Math::sin;

        // 测试函数3：复杂单峰函数
        DoubleFunction<Double> f3 = x -> Math.exp(-x * x) * Math.cos(2 * x);

        double eps = 1e-7;

        System.out.println("=== 黄金分割搜索测试 ===");

        double max1 = findMax(f1, 0, 5, eps);
        System.out.printf("函数1最大值点: x=%.10f, f(x)=%.10f (理论值: x=2)%n", 
                          max1, f1.apply(max1));

        double max2 = findMax(f2, 0, Math.PI, eps);
        System.out.printf("函数2最大值点: x=%.10f, f(x)=%.10f (理论值: x=%.10f)%n", 
                          max2, f2.apply(max2), Math.PI / 2);

        double min3 = findMinIterative(f3, -2, 2, eps);
        System.out.printf("函数3最小值点: x=%.10f, f(x)=%.10f%n", 
                          min3, f3.apply(min3));

        // 性能对比
        System.out.println("\n=== 性能对比（函数计算次数统计） ===");
        FunctionCallCounter counter1 = new FunctionCallCounter(f1);
        findMax(counter1::apply, 0, 5, eps);
        System.out.println("黄金分割搜索函数调用次数: " + counter1.getCount());

        FunctionCallCounter counter2 = new FunctionCallCounter(f1);
        ternarySearch(counter2::apply, 0, 5, eps);
        System.out.println("三分搜索函数调用次数: " + counter2.getCount());
    }

    // 辅助类：统计函数调用次数
    static class FunctionCallCounter {
        private final DoubleFunction<Double> f;
        private int count = 0;

        FunctionCallCounter(DoubleFunction<Double> f) {
            this.f = f;
        }

        double apply(double x) {
            count++;
            return f.apply(x);
        }

        int getCount() {
            return count;
        }
    }
}

算法分析

时间复杂度

黄金分割搜索的区间每轮缩小比例为 $1/\phi \approx 0.618$，设初始区间长度为 $L$，要达到精度 $\epsilon$，需要迭代轮数：

$$n = \log_{\phi}\left(\frac{L}{\epsilon}\right) = O\left(\log\frac{L}{\epsilon}\right)$$

由于每轮仅需一次函数求值，总时间复杂度为 $O(\log(L/\epsilon))$，但常数因子比三分搜索更小。

空间复杂度

迭代版本仅需常数额外空间，空间复杂度为 $O(1)$。递归版本的空间复杂度为 $O(\log(L/\epsilon))$。

收敛性保证

黄金分割搜索的收敛性是确定的：只要函数在区间内是严格单峰的，算法必定收敛到唯一的极值点。这与依赖随机性的优化算法（如模拟退火）形成鲜明对比。

扩展应用

多维黄金分割搜索

对于多维优化问题，可以结合坐标下降法（Coordinate Descent），轮流对每个维度执行一维黄金分割搜索。虽然收敛速度不如梯度方法，但在目标函数不可导或梯度计算困难时非常实用。

工程实践要点

1. 单峰性验证：实际应用中需确保目标函数在搜索区间内确实是单峰的，否则可能收敛到局部极值。
2. 数值稳定性：当区间极小时，$a + \text{RESPHI} \times (b-a)$ 可能比直接计算更稳定。
3. 提前终止：除了区间长度判据，还可以增加函数值变化量判据作为停止条件。

总结

黄金分割搜索是一种优雅而高效的单峰函数优化算法。它利用黄金分割比的几何性质，在每轮迭代中仅需一次新的函数求值即可缩小搜索区间。相比三分搜索，它在函数计算代价高昂的场景下具有明显优势。掌握这一算法，不仅能解决一维优化问题，还能作为多维坐标下降法的基石，在机器学习超参数调优、信号处理峰值检测等领域发挥重要作用。