无导数优化

无导数优化（derivative-free optimization）只通过目标函数评价选择候选点，不要求提供解析梯度。它适用于导数不可得、计算难或目标由黑箱程序给出的情形。无导数不等于没有数学条件；不同方法仍依赖单峰性、光滑性、噪声模型或搜索方向结构。下面用黄金分割区间法完整展示一维机制。

比较两点而不计算斜率

设连续函数f在 $[a, b]$ 上严格单峰：存在唯一最小点 $x^{*}$ ，函数在它左侧严格递减、右侧严格递增，最小点可位于端点。取 $a < c < d < b$ 。若 $f (c) \leq f (d)$ ，则 $x^{*} < d$ ：否则c、d均在严格递减侧，应有 $f (c) > f (d)$ ，矛盾。因此可保留 $[a, d]$ 。若 $f (c) > f (d)$ ，对称地可保留 $[c, b]$ 。

取教学目标 $f (x) = (x - 1.5)^{2} + 1$ 、初区间 $[0, 4]$ 。令 $r = (\sqrt{5} - 1) / 2 \approx 0.618034$ ，取 $c = b - r (b - a) \approx 1.527864$ 、 $d = a + r (b - a) \approx 2.472136$ 。函数值约为 $1.000776$ 与 $1.945049$ ，所以留下 $[0, 2.472136]$ 。

黄金分割首次查询点及保留区间 — 比较 c、d 的函数值后，金色轴段保留从零到 d 的范围。

黄金比例来自复用一次评价

新旧区间长度之比为r。希望旧的c在新区间 $[a, d]$ 中恰好成为右内点，需满足 $c - a = r (d - a) = r^{2} (b - a)$ 。旧定义给出 $c - a = (1 - r) (b - a)$ ，故要求 $r^{2} = 1 - r$ ；取位于零一之间的根便得到上述比例。于是每轮只需评价一个新点，另一个值可以复用。

前面的比较论证保证每轮区间都含真实最小点。经过k轮，长度为 $(b_{0} - a_{0}) r^{k}$ ，返回中点 $m_{k}$ 时有 $| m_{k} - x^{*} | \leq \frac{b_{0} - a_{0}}{2} r^{k} .$ 这证明了在声明单峰条件下的位置误差界；不需知道最小点的导数，也不直接给出目标值误差。若另外知道目标的Lipschitz常数，才可把位置误差乘该常数转为目标误差。SciPy的golden接口也使用黄金分割缩小夹持区间，但其两点brack会先作扩展搜索，不能当成这里固定端点的同一接口。^[1]

黄金分割区间的确定收缩 — 严格单峰条件保证每个区间含最小点，宽度按同一比例衰减。

单峰假设、变式与黑箱噪声

变式将最小点改为三，目标为 $(x - 3)^{2} + 1$ ，初始两点的比较方向反转，第一轮保留 $[1.527864, 4]$ 。其长度仍是原来的r倍，误差界不变。

若函数多峰，上述排除规则可删掉真正最好的一段。例如把点 $(0, 3), (1.5, 1), (2.5, 2), (3.8, - 10), (4, 3)$ 用直线相连。相同两内点的函数值约为1.027864、1.972136，程序仍舍去右侧，但真正最小值在3.8处。连续性并不足以代替单峰性。含噪声评价也可能颠倒两点次序，从而失去确定的夹持不变量。

高维无导数方法包括直接搜索、局部插值模型、贝叶斯优化和种群方法；它们的停止证据各不相同，不能把这一维误差界直接搬过去。用有限差分从函数值近似导数，与完全不形成导数近似的直接比较，也是不同实现选择。

只评价函数值的实现

函数输入可调用目标、有限端点和正容限，返回最终区间、中点、评价次数及区间历史，不改写输入；调用者须保证严格单峰，程序无法从有限评价验证它。每轮一次新评价，达到宽度ε约需 $O (\log ((b - a) / ε))$ 次，常数工作空间；这里保留历史另需同阶空间。目标每次评价成本另计。

Python 3

import math

def golden_interval(f,a=0.0,b=4.0,tolerance=1e-5,budget=100):
    if not a < b or tolerance <= 0 or budget < 1:
        raise ValueError("invalid interval or tolerance")
    r = (math.sqrt(5)-1)/2
    c,d = b-r*(b-a),a+r*(b-a)
    fc,fd = f(c),f(d)
    evaluations,trace = 2,[(a,b,c,d,fc,fd)]
    for _ in range(budget):
        if b-a <= tolerance:
            break
        if fc <= fd:
            b,d,fd = d,c,fc
            c = b-r*(b-a)
            fc = f(c)
        else:
            a,c,fc = c,d,fd
            d = a+r*(b-a)
            fd = f(d)
        evaluations += 1
        trace.append((a,b,c,d,fc,fd))
    return (a,b),(a+b)/2,evaluations,trace

bracket,mid,calls,trace = golden_interval(lambda x:(x-1.5)**2+1)
print("first",trace[0])
print("next",trace[1])
print("result",bracket,mid,calls)
assert bracket[0] <= 1.5 <= bracket[1]
assert golden_interval(lambda x:(x-3)**2+1)[0][0] <= 3

参考文献

↑ SciPy，scipy.optimize.golden，brack参数与Notes。

[1] SciPy，scipy.optimize.golden，brack参数与Notes。

[1]