优化算法通常依赖于梯度信息 ∇f(x)，有时也依赖于Hessian信息 ∇2f(x)。然而，在机器学习 (machine learning)及相关学科中，有些情况此类信息根本无法获取或难以实际得到。无导数优化（DFO），也称为黑盒 (black box)优化（BBO），通过仅使用函数评估 f(x) 来解决这些问题。
设想一下，你正在尝试调整一个复杂仿真模型的参数 (parameter)，该模型可能在模拟气候变化或金融市场。每次仿真运行给定参数集都会产生一个输出（即我们的目标函数值），但计算该输出相对于输入参数的梯度可能无法实现或计算量过大。类似地，考虑优化机器学习模型的超参数 (hyperparameter)，其目标是完整训练运行后的验证准确度；将超参数与准确度关联的函数评估成本很高，且其导数不易获取。
这些情况需要优化方法，仅根据在不同点观察到的目标函数值来搜索参数空间并做出决策。
核心思想：仅从函数值中获取信息
DFO方法在以下约束下运行：它们可以在任何点 x 查询目标函数 f 以获取值 f(x)，但无法访问 ∇f(x) 或 ∇2f(x)。主要难题是仅使用先前已评估点的历史记录及其相应的函数值，智能地选择下一个要评估的点，以朝着最小值前进。
可以将其想象为在迷雾中行进以找到最低点。你只知道当前海拔 (f(x)) 以及你到过的其他地点的海拔。你必须根据这些有限信息决定下一步走向何处。当然，与有梯度指引下坡相比，进展可能更慢，方向性也更弱。
无导数方法的分类
DFO涵盖了一系列不同的算法，通常大致分为以下几类：
1. 直接搜索方法
这些方法通过比较函数值来维护并更新搜索空间中的一组点。它们通常遵循特定的几何规则，在当前最优解的附近进行搜索。
- Nelder-Mead方法（单纯形法）： 这种经典的启发式算法维护一个单纯形，它是在n维空间中由n+1个顶点定义的几何形状（例如，2D中的三角形，3D中的四面体）。该算法通过反射、扩展、收缩和缩小等操作，迭代地用最差函数值的顶点替换，试图使单纯形朝着更低的函数值移动。尽管因其简单性而被广泛使用，但Nelder-Mead有时会停滞不前或收敛到非驻点，特别是在高维空间 (high-dimensional space)中。对于一般函数，它缺乏强有力的理论收敛保证。
- 模式搜索方法（例如，广义模式搜索，GPS）： 这些方法比Nelder-Mead更有结构。它们在预定义的网格或模式上搜索围绕当前最优解的点。如果在此“探测”步骤中找到一个具有更低函数值的点，模式的中心会移动到该点（成功步骤）。如果未找到改进，网格大小通常会减小（不成功步骤），以便后续进行更精细的搜索。模式搜索方法通常比Nelder-Mead具有更好的理论收敛性质，保证在函数和探测策略的特定条件下收敛到驻点。
2. 基于模型的方法
基于模型的方法不直接几何地操作一组点，而是构建一个局部代理模型（通常是二次的），用于近似当前点或区域附近的真实目标函数 f(x)。该模型可微且易于优化。
一般步骤包括：
- 在一组初始点评估 f(x)。
- 对这些点 (xi,f(xi)) 拟合一个代理模型（例如，使用插值或回归）。
- 找到代理模型的最小值，可能在一个模型被认为是准确的“信任区域”内。
- 在代理模型最小值建议的点评估真实函数 f(x)。
- 更新已评估点的集合并优化代理模型。
- 重复。
这些方法旨在通过形成对函数局部形状的认识，更有效地使用函数评估。针对DFO的信任域方法等都属于此类。我们将在后面介绍的贝叶斯优化是基于模型优化的一种高级概率形式。
3. 随机和启发式方法
这类方法在搜索策略中融入了随机性。它们常受到自然现象的启发，对于全局优化或应对非常崎岖、非光滑的地形很有效。
- 模拟退火（SA）： 受冶金退火过程启发，SA开始时在空间中进行广泛搜索，并逐渐集中搜索范围。它以概率接受移向更高函数值的点，尤其是在早期阶段（“温度”较高时），从而使其能够跳出局部最小值。随着过程“冷却”，接受更差移动的概率降低，使搜索变得更贪婪。
- 进化算法（EAs），包括遗传算法（GAs）： 这些方法维护一个候选解的“种群”。在每一代中，根据其“适应度”（函数值）选择解。通过“交叉”（组合现有解的部分）和“变异”（随机变化）创建新解。随着时间推移，种群倾向于演化出更好的解。
- 粒子群优化（PSO）： 这种方法模拟社会行为，例如鸟群觅食。一个“粒子”群体在参数 (parameter)空间中移动。每个粒子的移动受到其自身找到的最佳位置以及整个群体发现的最佳位置的影响。
随机方法可能很强大，但通常缺乏正式的收敛保证，可能需要大量的函数评估，且其性能可能对算法特定参数（例如，种群规模、变异率、冷却计划）的调整很敏感。
何时使用无导数优化
DFO方法在以下情况最适用：
- 梯度不可用时： 目标函数来源于黑盒 (black box)仿真、外部系统或无法进行微分的遗留代码库。
- 梯度不可靠或有噪声时： 函数评估本身具有显著噪声（例如，来自蒙特卡洛仿真或物理实验），使得梯度的有限差分近似不准确。
- 梯度计算成本过高时： 即使理论上可行，计算梯度所需的资源也远超评估函数本身。
- 目标函数非光滑或不连续时： 虽然存在次梯度方法，DFO有时能更直接地处理具有跳跃或拐点的函数，尽管收敛保证可能较弱。
- 处理离散或整数参数 (parameter)时： 某些DFO方法可调整以处理非连续参数空间。
- 超参数 (hyperparameter)优化时： 如前所述，为机器学习 (machine learning)模型寻找最优超参数是一个常见应用场景，此应用中目标函数评估成本高昂，且梯度通常不可用。
局限性与注意事项
虽然有价值，DFO方法但存在显著的限制：
- 可扩展性（维度灾难）： 随着参数 (parameter)数量 (n) 增加，性能下降迅速。直接搜索方法会呈指数级变慢，而基于模型的方法需要大量的点（通常与 n 呈平方关系或更差）来构建准确的模型。DFO通常仅适用于参数数量相对较少的问题（最多几十个，或几百个，取决于方法和问题结构）。
- 收敛速度： 当梯度可用且函数表现良好时，基于梯度的方法几乎总是比DFO方法快得多、效率高得多。DFO方法通常最多呈现线性或次线性收敛，在实践中往往慢得多。
- 调优： 许多DFO算法，特别是随机算法，有多个内部参数需要仔细调优才能获得良好性能。
- 局部优化与全局优化： 许多直接搜索和基于模型的方法本质上是局部优化器，类似于梯度下降 (gradient descent)。随机方法可能提供更好的全局搜索能力，但代价是接近最优解时的收敛速度较慢。
总而言之，无导数优化为梯度信息无法使用的问题提供了一套必要的工具。理解直接搜索、基于模型和随机方法等不同方法，以及它们各自的优点和缺点，能够帮助你在面对黑盒 (black box)优化难题时选择合适的策略，特别是在基于仿真的优化和超参数 (hyperparameter)调优等场景。然而，始终要考虑到它们与基于梯度的替代方案相比在可扩展性和收敛速度方面的局限性。
