我正在优化 10-20 个变量的函数。坏消息是每个函数评估都很昂贵，大约需要 30 分钟的串行计算。好消息是我有一个包含几十个计算节点的集群可供我使用。
因此，问题是：是否有可用的优化算法可以让我有效地使用所有计算能力？
一方面是穷举搜索：将整个搜索空间细分为精细网格，并独立计算每个网格点的函数。这当然是一个非常并行的计算，但该算法效率极低。
另一方面是准牛顿算法：根据先前的历史，智能地更新参数的下一个估计。这是一种有效的算法，但我不知道如何使其并行：“基于先前历史的参数估计”的概念听起来像串行计算。
二次算法似乎处于中间位置：可以通过并行计算一堆值来构建初始的“代理模型”，但我不知道剩余的迭代是否可以并行化。
关于哪种无梯度优化方法可以在集群上表现良好的任何建议？此外，目前是否有任何优化算法的并行实现可用？
正如保罗所说，没有更多信息，很难在没有假设的情况下给出建议。
对于 10-20 个变量和昂贵的函数评估，趋势是推荐无导数优化算法。我将强烈反对 Paul 的建议：您通常需要机器精度梯度，除非您使用某种特殊方法（例如，机器学习中的随机梯度下降将利用目标的形式提出合理的梯度估计）。
每个准牛顿步将采用以下形式：
在哪里是 Hessian 矩阵的某种近似，是搜索方向，是当前迭代中决策变量的值，是你的目标函数，并且是您的目标的梯度，决策变量的更新如下， 在哪里是以某种方式确定的步长（如线搜索）。您可以通过某些方式来近似 Hessian，并且您的迭代将收敛，尽管如果您通过精确梯度使用 Hessian 的有限差分近似，您可能会因病态条件而遇到问题。通常，Hessian 使用梯度来近似（例如，BFGS 类型的方法对 Hessian 进行 rank-1 更新）。
通过有限差分来近似 Hessian 和梯度是一个坏主意，原因有很多：
因此，要获得一次糟糕的准牛顿迭代，您需要在每次评估 30 分钟内进行多达 420 次函数评估，这意味着您要么为每次迭代等待一段时间，要么您将只需要一个大集群来进行功能评估。实际的线性求解将是 20 x 20 矩阵（最多！），因此没有理由将它们并行化。如果您可以通过例如解决伴随问题来获得梯度信息，那么它可能更值得，在这种情况下，可能值得一看像 Nocedal & Wright 这样的书。
如果您要并行执行大量函数评估，则应先查看代理建模方法或生成集搜索方法，然后再考虑准牛顿方法。经典的评论文章是Rios 和 Sahinidis 关于无衍生方法的文章，发表于 2012 年，提供了非常好的、广泛的比较；More and Wild 2009 年的基准测试文章；Conn、Scheinberg 和 Vicente 的 2009 年教科书“无导数优化简介”；以及Kolda、Lewis 和 Torczon于 2003 年撰写的关于生成集搜索方法的评论文章。
如上所述，DAKOTA 软件包将实现其中一些方法，实现 DIRECT 的NLOPT和 Powell 的一些代理建模方法也将实现。你也可以看看MCS；它是用 MATLAB 编写的，但也许您可以将 MATLAB 实现移植到您选择的语言。DAKOTA 本质上是一组脚本，可用于运行昂贵的模拟并收集优化算法的数据，而 NLOPT 具有多种语言的接口，因此在使用任何一种软件包时，编程语言的选择都不应该是一个大问题；不过，DAKOTA 确实需要一段时间来学习，并且有大量的文档需要筛选。
也许您正在寻找基于代理的优化算法。这些算法在优化过程中使用代理模型来替换真正的计算成本高的模型，并尝试使用尽可能少的计算成本高模型的评估来获得合适的解决方案。
我认为Mode Pursuing Sampling 方法可以用来解决你的问题。该算法使用 RBF 代理模型来逼近昂贵的目标函数，并且可以处理非线性约束。更重要的是，它会选择多个候选者进行昂贵的函数评估，以便您可以将这些候选者分配给并行计算，以进一步加快搜索过程。该代码是开源的，并用 MATLAB 编写。
参考
Wang, L., Shan, S., & Wang, GG (2004)。用于昂贵黑盒函数全局优化的模式追踪采样方法。工程优化，36（4），419-438。
我不确定并行算法是否真的是您正在寻找的。您的功能评估非常昂贵。您要做的是并行化函数本身，而不一定是优化算法。
如果你不能这样做，那么在穷举搜索和牛顿算法之间有一个中间地带，那就是蒙特卡洛方法。您可以在一堆不同的核心/节点上启动易于陷入局部最优的相同算法（例如准牛顿算法），但所有这些算法都具有随机初始条件。那么对于真正的最优值，你最好的猜测是最小值中的最小值。这对于并行化来说是微不足道的，可用于扩展任何方法。虽然效率不高，但如果你有足够的计算能力可供使用，它肯定会赢得编程效率与算法性能的战斗（如果你有很多计算能力，这可以在你完成制作更高级的算法之前完成）。
优化算法（及其并行化）的选择很大程度上取决于目标函数和约束的属性。在不了解更多问题的情况下，很难给出任何有意义的建议。
但是根据您对牛顿方法的考虑，我推断您的目标函数是可微的。如果可能的话，您的问题将从并行化函数评估中受益匪浅。如果不可能，那么您也可以考虑一种不精确的牛顿法，它用有限差分近似代替精确的梯度/粗麻布。然后，正如@stali 建议的那样，您可以使用所有这些处理器来计算雅可比的每个非零元素。
有关更多信息，请阅读Nocedal 和 Wright 的数值优化，第 7 章。有许多优化软件包可以并行实现这一点。使用最广泛的免费软件是DAKOTA 软件包（桑迪亚国家实验室）。