全局优化是什么？寻找整个范围内真正最好的解

全局优化（Global Optimization）是应用数学和数值分析的一个分支，研究如何在所有可能的解中，找到使目标函数取得全局最优值的那个解，也就是全局最小值或全局最大值，而不仅仅是某个局部范围内的最优值。

为什么全局优化很难

大多数常用的优化方法，比如梯度下降、牛顿法，都是局部优化方法：它们从某个起点出发，根据当前位置周围的信息，比如坡度，一步步往更好的方向移动，直到无法继续改进。对于凸函数，这样一定能找到全局最优。但很多实际问题的目标函数是非凸的，有许多个局部最优解，就像一片有很多山谷的山地。局部优化方法很容易陷在某个山谷里，而不知道其他地方还有更深的山谷。要确保找到全局最优，原则上需要对整个搜索空间有充分的了解，当变量很多时，搜索空间会大到难以想象，这被称为维度灾难。很多全局优化问题在计算复杂性上属于非常困难的一类，比如旅行商问题。

确定性方法

确定性方法能够在一定条件下保证找到全局最优，或者给出与全局最优相差多少的保证。最典型的是分支定界法：把搜索空间不断地划分成更小的区域，对每个区域估计目标函数可能取到的最好值的界限，如果某个区域的最好可能值都不如已经找到的解，就可以直接排除这个区域，不必再搜索。它被广泛用于整数规划等组合优化问题。此外还有区间分析、利用利普希茨常数等方法。这些方法的缺点是计算量可能随问题的规模急剧增长。

随机方法和启发式方法

在实际中更常用的是随机方法和启发式方法，它们不能保证一定找到全局最优，但往往能在合理的时间内找到很好的解。多起点法：从许多个随机的起点分别进行局部优化，取其中最好的结果，简单而有效。模拟退火：借鉴了金属退火的物理过程，在搜索的早期允许以一定的概率接受更差的解，从而有机会跳出局部最优，随着“温度”逐渐降低，越来越少地接受更差的解，最终稳定在一个好的解上。它在 1983 年由 Scott Kirkpatrick 等人提出。遗传算法：模仿生物的进化，维护一个由多个候选解组成的“种群”，通过选择、交叉和变异产生新的一代，适应度高的解更容易被保留下来，经过许多代的进化逐步改进。粒子群优化：模仿鸟群觅食的行为，一群“粒子”在搜索空间中飞行，每个粒子根据自己找到的最好位置和整个群体找到的最好位置来调整飞行的方向。此外还有差分进化、蚁群算法等。

贝叶斯优化

当目标函数每计算一次都代价很高时，比如训练一次深度学习模型要几个小时，需要尽可能少地评估目标函数。贝叶斯优化用一个替代模型，通常是高斯过程，来近似目标函数，并根据它的预测和不确定性，智能地选择下一个最值得尝试的点，在探索未知区域和深挖有希望的区域之间取得平衡。它被广泛用于机器学习的超参数调优、实验设计和材料研发。

应用

全局优化被用于工程设计、物流调度和路线规划、化学中寻找分子最稳定的结构、蛋白质折叠、金融投资组合优化、芯片布局设计，以及机器学习中的超参数搜索和神经网络结构搜索等。