我正在通过运行诸如 BOBYQA 之类的算法和其他一些无导数算法来优化 10-20 个变量的函数。坏消息是每个函数评估都非常昂贵，大约需要 30 分钟的计算时间。好消息是，我从全局最小值开始，朝“正确方向”走几步就足够了。
问题是：我不知道需要多少功能评估才能开始朝着“正确的方向”前进。我天真的估计是这样的：你必须在初始点加上评估每一个中的一阶和二阶导数的点方向加评估混合的二阶导数，然后您可以朝着“正确的方向”迈出相当自信的第一步。
另一方面，上述在变量数量上呈二次方的估计似乎过分了。我怀疑一个人是否真的需要那么多信息才能开始接近局部最小值。因此问题是：给定一个在全局最小值附近表现良好的问题，经过多少次迭代后，无导数优化方法（例如鲍威尔的优化方法）预计将开始向局部最小值移动，函数为变量？
您的估计更多地是指为 BOBYQA 构建二次代理模型所需的函数评估次数。构建代理模型的无导数方法必须采用一定数量的函数评估来构建代理模型才能进行优化。这个函数评估的数量是采取一个步骤所需的最小数量。在一些代理建模方法中，可以重用一些函数评估并用一些新的函数评估来增加这些评估以构建一个新的代理模型。但是，在初始化算法时不可能进行这样的重用。
ORBIT基于使用径向基函数代理模型，需要较少的评估来构建代理模型（它在状态变量的数量上是线性的）。我不知道公开可用的实现。倾向于推荐鲍威尔的方法的部分原因是因为库质量的实现是可用的。
当涉及到优化迭代——而不是函数评估——在某些假设下，有可能限制达到所需的迭代次数-最优性。Kantorovich 有一个著名的证明，在某些假设下对牛顿的方法也是如此。我不知道专门针对无导数优化的结果。例如，我们确实知道非凸优化是 NP 难的，所以我希望任何这样的结果都需要凸性，可能还需要一些技术条件（比如 Kantorovich 的证明，以及 Nesterov 和 Nemirovskii 的内点方法的结果）凸非线性程序）。