玻尔百科对“最佳”可能结果——最低成本、最高效率或最稳定构型的探索，是推动科学与工程进步的根本动力。然而，对于复杂问题，通往真正最优解的道路往往充满险阻。简单的优化策略很容易陷入局部看起来最优、但远非真正全局最佳的解中。本文通过介绍确定性全局优化来应对这一关键挑战，这是一类旨在找到有保证的全局最小值的强大方法。在接下来的章节中，我们将首先探讨定义局部最优点问题的“原理与机制”，并详细介绍提供严谨解决方案的系统性“分而治之”策略，如分支定界法。随后，“应用与跨学科联系”一章将展示这些方法并非仅仅是理论上的奇珍，而是解决现实世界问题的基本工具，从设计新分子、构建更安全的工程结构到打造更鲁棒的人工智能。
想象一下，你是一名徒步旅行者，任务是在一片广阔、大雾弥漫的山脉中找到绝对的最低点。你有一个高度计，但只能看到脚下的地面。最简单的策略是永远朝下坡走。这是一个不错的计划，你会很快找到你所在山谷的底部。但这是整个山脉的最低点吗？你无从知晓。你可能身处一个宜人的高山草甸，而就在下一座山脊之后，可能有一个深达数千英尺的峡谷。你被困在了一个局部最小值（local minimum）中，这是一个比其紧邻周围环境低，但并非真正的全局最小值（global minimum）的点。
这个简单的类比抓住了全局优化的根本挑战。对于科学与工程中许多最引人入胜的问题——从为新药设计最稳定的蛋白质，到寻找原子团簇的最低能量构型——我们本质上是在一个复杂、高维的“能量景观”上寻找最低点。我们最简单的计算工具，就像那个下坡行走的徒步者一样，本质上是局部的，并且容易陷入困境。确定性全局优化就是如何万无一失地找到那个最深峡谷的艺术与科学。
让我们将这个类比变得更正式一些。我们正在探索的“景观”是一个目标函数（objective function），即一个数学函数 ，它为我们系统的每一种可能构型 赋予一个单一的值（如能量或成本）。在化学中，这通常被称为势能面（Potential Energy Surface, PES），其中 代表分子中所有原子的坐标。
局部最小值是一个构型 ，在该点函数处于一个谷底。在数学上，这意味着梯度（最陡峭上升方向）为零，即 ，并且所有方向的曲率都为正（Hessian 矩阵是正定的），这意味着你确实处在一个碗的底部，无论它有多小。全局最小值 则是在整个定义域内 值最低的点，即对于所有 都有 。
基于梯度的局部搜索方法之所以会失败，是因为可能的构型空间被划分为多个吸引盆（basins of attraction）。某个特定局部最小值的吸引盆是指所有起始点的集合，从这些点出发，遵循下坡方向的算法将不可避免地最终到达该最小值。局部优化器就像在景观上释放的一颗弹珠；它只能滚入其起始所在的盆地底部。它没有能力“看到”将其与其他可能更深的盆地隔开的能量壁垒。对于任何足够复杂的现实世界问题，其景观都是非凸的，充满了天文数字般的此类盆地，这使得随机从正确的那个盆地开始的几率小到可以忽略不计。
然而，这条规则有一个绝佳的例外：凸优化（convex optimization）。凸函数在数学上等同于一个完美的、单一的碗状山谷。它没有其他恼人的山谷或凹陷让你陷入其中。对于这样的函数，任何局部最小值必然是全局最小值。如果你找到了一个底部，你就找到了那个底部。
在这种特殊情况下，我们简单的下坡行走徒步者每次都会成功，无论他们的起点在哪里。像 Karush-Kuhn-Tucker (KKT) 条件这样的数学工具可以为这些表现良好的问题提供一个点确实是全局最优的正式证明。虽然许多现实世界的问题并非天然是凸的，但这类“简单”问题构成了一个关键的理论基准，也是重新表述更复杂问题的一个目标。但对于真正崎岖不平的非凸荒野，我们需要更强大的策略。
你如何绘制一个广阔、未知的领土以找到其最低点？你不会漫无目的地闲逛，而是系统地去做。你“分而治之”。这就是分支定界（Branch-and-Bound）算法的核心哲学，它是确定性全局优化的基石。
该策略包括三个关键操作：
分支（划分）： 我们从整个搜索域开始——我们的“世界”——表示为一个单独的大盒子。然后，我们系统地将这个盒子划分为更小的子盒子。最常见的方法是简单地沿着当前盒子最长的维度将其切成两半。这个过程创建了一个嵌套区域的树，分支出来覆盖整个空间。
定界（估计）： 对于每个盒子，我们需要回答两个问题。首先，我们迄今为止找到的最佳解是什么？这被称为上界（upper bound）或“当前最优解”（incumbent），它就是我们在任何点实际评估过的最低函数值。其次，也是最巧妙的部分，函数在这个盒子内的绝对最低值可能是多少？这就是下界（lower bound）。我们不知道盒子里的最小值在哪里，但我们可以为它计算一个有保证的下限。一个常见的方法依赖于知道函数的最大“陡峭度”，即其 Lipschitz 常数 。如果我们在盒子中心评估函数值 ，我们就知道盒子内任何其他地方的函数值不会低于 减去从中心到角落可能出现的最陡峭下降。这为整个区域提供了一个可证明的下界，而无需详尽地搜索它。
剪枝（消除）： 这是奇迹发生的地方。我们维护一个所有仍需探索的活动盒子的列表。在每一步，我们查看具有最有希望（最低）下界的盒子。我们将这个盒子的下界与我们的全局上界（迄今为止找到的最佳解）进行比较。如果一整个盒子的保证下限已经高于我们在别处找到的一个点，那么在这个盒子里就没有希望找到更好的解了。我们可以简单地丢弃它——或者说从我们的搜索树中“剪除”它。
该算法通过反复选择最有希望的盒子，将其分支为子盒子，计算它们的界限，并剪除那些被证明是次优的盒子来继续进行。当所有盒子中最佳上界和最低下界之间的差距小于期望的容差 时，搜索停止。在那时，我们不仅找到了一个近乎最优的解，而且我们还有一个数学证明，证明不存在更好的解。
此外，我们可以让搜索更加智能。与其总是分割几何上最大的盒子，我们可以分割那个对我们的不确定性贡献最大的盒子——即中心点值与下界之间差距最大的那个。这种自适应划分（adaptive partitioning）将我们的计算精力集中在最需要收紧界限和加速收敛的地方。
“分而治之”的哲学并不仅限于在连续空间中寻找坐标。许多优化问题涉及做出一系列离散选择。一个经典的例子是合理的蛋白质设计，其中对于蛋白质链中的每个位置，我们必须从20种标准氨基酸中选择一种，以构建最稳定或最具活性的结构。
对于这些问题，一种强大的确定性方法是整数线性规划（ILP）。其核心思想是将问题转化为一个带有整数变量的线性方程组。我们可以用一组二元（0或1）变量——就像一排开关一样——来表示在特定位置选择一种氨基酸。目标函数（例如，蛋白质的能量）和任何约束条件（例如，“丙氨酸残基不超过五个”）然后被表示为这些二元变量的线性函数。
然后，ILP 求解器使用一种在其核心上是分支定界法复杂形式的算法。它系统地探索可能的开关设置的巨大组合空间，使用线性松弛来计算界限并剪除不可能导向最优解的整个子树。当求解器完成时，它为指定的数学模型提供一个全局最优解，并附带最优性证明。这与系统性消除的原理相同，只是巧妙地应用于离散选择的世界。
确定性方法提供了终极奖励：全局最优性的保证。但这种确定性是有代价的。对于非常困难的问题，必须探索的盒子或分支的数量可能会随着问题规模呈指数级增长。搜索可能会变得计算上难以处理，可能需要运行极长的时间。
这时，确定性方法的严谨性与随机方法的实用主义之间出现了权衡。像多起点法（multistart）这样的方法，即简单地从多个随机起始点运行局部优化，不提供最优性证明。然而，在固定的计算预算下，多起点法找到全局最小值的概率可能比一个在穷举搜索早期阶段就陷入困境的确定性方法更高。其他复杂的方法，如盆地跳跃法（basin-hopping），通过在局部最小值的景观上进行随机行走，将两者融合在一起，使用局部优化作为从一个盆地跳到另一个盆地的工具 [@problem_-id:2894237]。
方法的选择也关键取决于目标函数本身的计算成本。如果评估函数很廉价，我们可以承担多次采样的成本。但如果每次评估都极其昂贵——比如一次持续多天的量子化学模拟——我们就必须极其节约。在这种情况下，像分支定界法这样复杂算法的开销与单次函数调用的成本相比可以忽略不计。算法在最小化评估次数方面的智能变得至关重要。
最终，确定性全局优化是逻辑战胜蛮力的胜利。它认识到，我们不能指望在一个广阔而复杂的空间中幸运地偶然发现正确答案。相反，我们必须系统化。通过划分问题、界定可能性和剪除不可能的优雅过程，我们可以将无限的搜索变成一场有限、可管理且可证明的寻求真正全局最优的探索。它不仅提供了一个答案，而且提供了不存在更好答案的确定性。
在我们完成了确定性全局优化原理与机制的探索之旅后，人们可能会倾向于将其视为一种优美但或许有些脱离实际的数学机器。我们精心构建了能够提供极其强大之物的方法：一个保证。但在混乱、复杂且常常不确定的现实世界中，这样的保证在哪里能找到其用武之地呢？事实证明，答案是无处不在。对“最佳”——最低能量状态、最鲁棒的设计、最高效的路径——的追求，是贯穿科学与工程领域的线索。每当我们面对一个充满山丘和山谷的景观，当“足够好”的局部最优解的诱惑可能使我们偏离真正解时，确定性全局优化就不再仅仅是一个工具，而是一个必不可少的向导。
让我们从该方法的核心开始。想象你正试图找到一个剧烈波动的地形的绝对最低点，就像一个被瞬间冻结的波涛汹涌的大海。这个函数可能是一个复杂的音频信号或一段时间内的股票价格，通常由许多重叠的波组成，创造出令人眼花缭乱的峰谷。你如何能确信自己已经找到了最低点，而无需检查每一个点呢？这正是确定性方法的优雅之处。通过首先计算出地形最大可能的陡峭程度——一个被称为 Lipschitz 常数的属性——我们可以在已经测量的点周围画出“安全走廊”。对于任何区域，我们都可以计算出一个保证的下界，一个地形绝不可能低于的水位线。如果这个水位线已经高于我们迄今为止找到的最佳点，我们就可以自信地永远忽略整个区域，而无需涉足其中。这就是“分支定界”方法的精髓：我们智能地修剪无限的可能性之树，以数学的确定性逼近全局最优解。这种方法不仅仅是理论上的；它是在保证成功的前提下解决复杂一维优化问题的算法背后的构造性原理。
当我们进入分子的世界时，这种以确定性进行探索的能力变得真正具有变革性。设想一位计算化学家试图绘制化学反应的进程。这里的“景观”是势能面（Potential Energy Surface, PES），一个高维地形，其中山谷代表稳定的分子，而它们之间的山隘代表反应的过渡态。山隘的高度决定了使反应发生的能量需求。如果你在设计一种新的催化剂或试图理解一个生物过程，你的目标不仅仅是找到一条可能的反应路径，而是要发现所有路径。错过任何一条低能量路径都可能意味着你对反应的整个模型都是错误的。
在这里，简单的随机搜索——比如扔下一个球看它滚进哪个山谷——是不够的。这是一种在景观上“醉汉走路”式的方法，可能会找到最明显的山谷，但几乎肯定会错过更微妙但至关重要的路线。相比之下，确定性的全局探索就像一个系统的测量员。它分两个阶段工作：首先，它详尽地枚举出达到某一能量值以下的所有稳定最小值（化合物）。然后，从每一个这样的最小值出发，它系统地向所有可能的方向搜索，以找到连接它到另一个盆地的每一条逃逸路线（鞍点或过渡态）。这保证了一个完整的反应网络图。没有这张详尽的、确定性的地图，建立一个预测性动力学模型将是一种猜测行为；有了它，这就变成了一种科学行为。
这种对保证的需求有力地延伸到了工程领域，在这一领域，安全不仅仅是一个目标，更是一项强制性要求。当工程师设计桥梁、建筑或飞机机翼时，他们不能只为平常的日子设计。他们必须为最坏可能的一天设计——最大载荷、最强风力和最弱材料性能的完美风暴。这一理念在一个称为鲁棒优化的框架中被形式化，该框架通常采用“最小-最大”（min-max）形式。工程师寻求最小化结构的成本或重量，但要满足一个约束条件，即在任何合理的不确定性下，其所经历的最大应力都保持在临界安全阈值以下。
这个内部的最大化问题——找到最坏情况——是一个全局优化问题，必须为每个候选设计求解。例如，在拓扑优化中，计算机算法决定在哪里放置材料以创造一个既坚固又轻巧的结构，它必须在给定的范围内，根据所有可能的载荷大小和方向来检查其设计。乍一看，这似乎极其困难，因为有无限多种情景需要检查。但在这里，问题的结构常常能帮助我们。对于许多线性系统，最坏情况保证不会发生在不确定性范围的中间某处，而是发生在其极端的角落。一个具有无限可能性的问题可以被确定性地简化为检查少数几个定义明确的极端情景。这将保证在未知情况下安全的艰巨任务转变为一个可行的计算，使我们能够建造我们确信不会失败的东西。
这种完全相同的“最小-最大”逻辑最近在人工智能的前沿领域找到了一个关键应用。现代机器学习的一个令人不安的发现是，高度准确的AI模型可能出人意料地脆弱。一个能够以99%的置信度识别熊猫图片的神经网络，可能会因为添加了一层对人眼完全不可察觉的、精心制作的微小噪声而被欺骗，将其看作是长臂猿。这被称为“对抗性样本”。我们如何构建一个对这种欺骗具有鲁棒性的AI呢？
事实证明，答案是像我们建造一座坚固的桥梁那样来训练它。这个过程被称为对抗性训练，它被表述为一个最小-最大博弈。我们的目标是最小化模型的误差，而一个假想的对手则同时试图通过找到对输入数据的最坏可能扰动来最大化它。在训练的每一步，模型都必须解决一个内部的全局优化问题：“我能对这张图片做出的最具破坏性但又微小的改变是什么？”
在这里，发生了一些非凡的事情。解决这个内部最大化问题，即迫使模型考虑其紧邻区域内的最坏情况，对整个优化景观产生了深远的影响。鲁棒化目标函数，即在一个小邻域内损失的上确界，本质上比原始函数更“平滑”。损失景观中那些可能将学习算法困在不良局部最小值中的尖锐、狭窄的山谷，通常会被这个过程“熨平”。因此，通过在局部尺度上为最坏情况做准备，我们使得寻找一个好模型的全局问题变得更加稳定和表现良好。对鲁棒性的追求意外地帮助了对最优性的追求。
从 Lipschitz 界的抽象确定性到桥梁的具体安全性，从绘制化学反应的宇宙到锻造更可靠的人工智能，确定性全局优化提供了一个统一的原则。它是在一个充满欺骗性局部最优解的世界中，对最佳可能答案进行严格、系统和有保证的搜索。它提醒我们，在最复杂的景观中，只要有正确的地图和正确的工具，我们就能自信地航行，并抵达我们真正的目的地。