核心概述
在闭区间上对单峰实函数进行导数无关的一维极值搜索，按黄金比例复用内部点以单调收缩区间，达到给定精度阈值。
原文引述
Description: Derivative-free 1D optimization for unimodal functions on [L,R]. Uses golden ratio to reuse interior points and shrink interval deterministically. Time: O(log((R−L)/eps)) function evaluations Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景
- 黄金分割搜索（Golden Section Search）：在闭区间 [L,R] 上，针对“单峰”（仅一处极小/极大）函数做极值搜索；不需要导数信息，适合黑箱评估。
-
接口/字段与输入输出语义（据实现约定）
- double goldenSectionMin(double L, double R, auto f, double eps=1e-12)
- 返回在 [L,R] 上的近似极小点 x（需要时再评估 f(x) 得最小值近似）。
- double goldenSectionMax(L,R,f,eps)：对 −f 取最小即可实现最大化。
- 要求：f 在 [L,R] 上单峰且可在任意点评估；eps 为停止阈值（可为绝对/相对长度判据的组合）。
- double goldenSectionMin(double L, double R, auto f, double eps=1e-12)
-
核心流程与关键要点（重用点位 + 黄金比例）
- 设 φ=(1+√5)/2，ρ=φ−1≈0.618。
- 取内部两点：
- m1 = R − ρ·(R−L)
- m2 = L + ρ·(R−L)（保证 m1 < m2，比例固定）
- 评估 f(m1), f(m2) 并更新：
- 若 f(m1) < f(m2)，极小值在 [L, m2]，令 R=m2，并将 m1 复用为新的 m2，重算新的 m1；
- 否则在 [m1, R]，令 L=m1，并将 m2 复用为新的 m1，重算新的 m2。
- 每次仅新增一次函数评估；当 R−L ≤ eps 时终止，通常返回 (L+R)/2 作为代表点。
-
数值稳定性与精度注意
- 停机准则：在长度与相对误差双条件下更稳健，避免极窄区间的舍入影响。
- 噪声/不连续：若 f 含噪声或跳变，适当放宽 eps；或采用更鲁棒的启发式（见 102-数值算法-爬山算法）。
- 离散域：对整数/离散自变量不直接适用，可参考 140-杂项-三分搜索 或对邻近点做比较。
-
复杂度与边界条件
- 区间长度每步乘以 ρ≈0.618；迭代次数 O(log((R−L)/eps))。
- 函数评估次数为首轮 2 次，之后每步新增 1 次；总体近似 1 + ⌈log_φ((R−L)/eps)⌉。
-
常见变体/扩展与取舍
- 最大化通过最小化 −f 实现；亦可对比较方向取反。
- 与 140-杂项-三分搜索：三分对“明确凸/凹段”也常用，但黄金分割通过复用点减少评估。
- 与 102-数值算法-爬山算法：后者适合非单峰/噪声目标的启发式局部搜索。