局部最优与全局最优（local versus global optimum）

站在山坡上的一个小凹处：在局部，你已在底部——每往附近迈一步都向上。但放眼整片山脉，也许有一条你看不见、深得多的谷。局部最优只相对于它紧邻的邻域是最好的；全局最优才是整个可行区域中最好的。把它们区分开来，是优化的核心难题之一。

形式上，若 f 在某点小于等于所有邻近点的 f，该点是局部极小；若 f 在某点小于等于定义域中每一点的 f，则是全局极小。微积分条件——梯度为零、黑塞矩阵正定——本质上是局部的：它们只考察无穷小邻域，所以能认证局部极小，却对别处是否存在更低值只字不提。一个函数可以有许多深浅不一的局部极小；一般而言要找出全局的那个，要么逐一检查所有局部极小，要么利用特殊结构，要么退而求一个足够好的局部解。

这道鸿沟正是真正困难之所在。凸性是伟大的化解者：在凸集上的凸函数上，每个局部极小都是全局极小，于是局部方法解决了全局问题。一旦离开凸世界——在蛋白质折叠、神经网络训练、组合设计中——一般并没有高效找到全局最优的保证，从业者会用多次重启、随机搜索，或干脆接受一个强的局部解。诚实地分清能认证局部与已找到全局之别，是成熟优化实践的一部分。