无约束优化方法及其收敛
Unconstrained optimization methods and their convergence
我是凝聚态物理专业的学生。我有 运行 很多需要 全局优化 的问题，例如 find the most stable crystal form for a given components。
这些问题可以概括为（我相信是 NP-hard）：
1) 给定一个函数f(x1,x2,x3,...)，它完全是一个黑盒子，有时计算起来很昂贵
2) 给定一个区域S，它是离散的
3) 求函数的全局最大值f
我知道有很多算法，比如evolutionary algorithms、particle swarm optimization、simulated annealing，如果f(x)不是很贵，我可以用一些点来训练一个neuronal network，和meta-dynamics，但我想知道：
1) 是否有更多的算法可以做同样的事情？
2) 这些算法的收敛性和收敛速度如何？我发现一些论文说大多数这些算法收敛，但与整个 space?
的粗暴搜索相比，它们的收敛速度有多快？
非常感谢谁能提供信息或在哪里可以找到有关上述问题的信息
难度理论的一般工作方式是，如果你能证明所研究的算法可以用来解决已知的难题，那么该算法不能保证正确性和易处理的多项式计算机时间（否则我们会得到 P=NP，虽然目前还没有证据证明，但事实并非如此）。现在有大量的 NP 完全问题和 NP 难问题。为了您的目的，请特别注意 https://en.wikipedia.org/wiki/Quadratic_programming#Complexity 是其中之一。通常也很容易解决组合问题并得出一个连续函数，该函数在组合问题的解中具有全局最小值，因此如果您能在连续问题中找到全局最小值，您就可以解决困难组合问题。
数值分析书籍中充满了在给定合理假设的情况下求导并快速收敛到局部最优值的方法。还有 Torczon Simplex，它具有合理假设的收敛性证明，但不需要导数。 （参考 https://en.wikipedia.org/wiki/Pattern_search_(optimization), see also https://help.scilab.org/doc/5.5.2/en_US/optimsimplex_overview.html）。这里的问题是收敛被证明是局部最优的，并且可能有很多局部最优。请注意，即使 SUM_i (X_i^2-1)^2 也具有指数级的许多局部最优值，尽管它们都产生相同的值。一种想法是从随机的起始位置反复收敛并选择找到的最佳答案，但显然找到全局最优解的机会可能很小。
模拟退火及其变体证明了收敛到全局最优，但如果你看看它是如何证明的，它归结为如果你离开程序 运行 足够长的时间它会最终会被正确答案绊倒，因此收敛时间会随着问题的大小呈指数增长，并且与从多个随机开始反复收敛到局部最优值的数量级相同（或更差）。有时在这里做出的假设——特别是你正在优化一个随机函数——也可能证明 https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization 定理，这表明这些奇特的方法有其自身的弱点，或者至少没有一个最好的通用算法.
谢谢大家！我发现这个陈述解决了我想的问题
While metaheuristics are not able to certify the optimality of the
solutions they find, exact procedures (which theoretically can provide such a certification, if allowed to run long enough) have often proved incapable of finding solutions whose quality is close to that obtained by the leading metaheuristics — particularly for real-world problems, which often attain notably high levels of complexity
来自 Glover、Fred W. 和 Gary A. Kochenberger 编着。元启发式手册。卷。 57. Springer Science & Business Media, 2006.
（犯了一个愚蠢的错误，没有复制整个句子，现在完整了）
我是凝聚态物理专业的学生。我有 运行 很多需要 全局优化 的问题，例如 find the most stable crystal form for a given components。
这些问题可以概括为（我相信是 NP-hard）：
1) 给定一个函数f(x1,x2,x3,...)，它完全是一个黑盒子，有时计算起来很昂贵
2) 给定一个区域S，它是离散的
3) 求函数的全局最大值f
我知道有很多算法，比如evolutionary algorithms、particle swarm optimization、simulated annealing，如果f(x)不是很贵，我可以用一些点来训练一个neuronal network，和meta-dynamics，但我想知道：
1) 是否有更多的算法可以做同样的事情？
2) 这些算法的收敛性和收敛速度如何？我发现一些论文说大多数这些算法收敛，但与整个 space?
的粗暴搜索相比，它们的收敛速度有多快？非常感谢谁能提供信息或在哪里可以找到有关上述问题的信息
难度理论的一般工作方式是，如果你能证明所研究的算法可以用来解决已知的难题，那么该算法不能保证正确性和易处理的多项式计算机时间（否则我们会得到 P=NP，虽然目前还没有证据证明，但事实并非如此）。现在有大量的 NP 完全问题和 NP 难问题。为了您的目的，请特别注意 https://en.wikipedia.org/wiki/Quadratic_programming#Complexity 是其中之一。通常也很容易解决组合问题并得出一个连续函数，该函数在组合问题的解中具有全局最小值，因此如果您能在连续问题中找到全局最小值，您就可以解决困难组合问题。
数值分析书籍中充满了在给定合理假设的情况下求导并快速收敛到局部最优值的方法。还有 Torczon Simplex，它具有合理假设的收敛性证明，但不需要导数。 （参考 https://en.wikipedia.org/wiki/Pattern_search_(optimization), see also https://help.scilab.org/doc/5.5.2/en_US/optimsimplex_overview.html）。这里的问题是收敛被证明是局部最优的，并且可能有很多局部最优。请注意，即使 SUM_i (X_i^2-1)^2 也具有指数级的许多局部最优值，尽管它们都产生相同的值。一种想法是从随机的起始位置反复收敛并选择找到的最佳答案，但显然找到全局最优解的机会可能很小。
模拟退火及其变体证明了收敛到全局最优，但如果你看看它是如何证明的，它归结为如果你离开程序 运行 足够长的时间它会最终会被正确答案绊倒，因此收敛时间会随着问题的大小呈指数增长，并且与从多个随机开始反复收敛到局部最优值的数量级相同（或更差）。有时在这里做出的假设——特别是你正在优化一个随机函数——也可能证明 https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization 定理，这表明这些奇特的方法有其自身的弱点，或者至少没有一个最好的通用算法.
谢谢大家！我发现这个陈述解决了我想的问题
While metaheuristics are not able to certify the optimality of the solutions they find, exact procedures (which theoretically can provide such a certification, if allowed to run long enough) have often proved incapable of finding solutions whose quality is close to that obtained by the leading metaheuristics — particularly for real-world problems, which often attain notably high levels of complexity
来自 Glover、Fred W. 和 Gary A. Kochenberger 编着。元启发式手册。卷。 57. Springer Science & Business Media, 2006.
（犯了一个愚蠢的错误，没有复制整个句子，现在完整了）