寻找局部最优解，普林斯顿学者发现：三次优化问题比二次更易于实现

是否可以和如何快速找到二次和三次优化问题的局部最优解，普林斯顿大学教授 Amir Ali Ahmadi 及其前博士生 Jeffrey Zhang 的两篇论文给出了他们的答案。

选自QuantaMagazine，作者：Max G. Levy，编译：杜伟。

某种程度上来讲，我们的生活由连续的优化问题组成。当搜索从工作场所返家的最快路程时，我们会遇到优化问题；当去商店的途中试图平衡成本（cost and quality）质量时，我们会遇到优化问题；当决定入睡前如何度过有限空闲时间时，我们会遇到优化问题。

这些以及其他更多类似场景都可以用数学优化问题来表示。做出最佳决策则意味着需要找到这些问题的最优解。然而，对于专注于优化问题的领域研究人员来说，去年的两项研究同时带来了好消息和坏消息。

2020 年 8 月 12 日，普林斯顿大学运筹学与金融工程系教授 Amir Ali Ahmadi 及其前博士生（现为卡内基梅隆大学数学科学客座教授） Jeffrey Zhang 在论文《On the complexity of finding a local minimizer of a quadratic function over a polytope》中发现，对于某些二次优化问题（这类问题中的成对变量可以交互作用），在计算上以一种具有时效性的方式找到局部最优解从计算上也是不可行的。

论文地址：https://arxiv.org/abs/2008.05558

两天后，两人又发表了另一篇论文《Complexity aspects of local minima and related notions》，证实了总是可以快速确定一个三次多项式（变量之间存在三向交互）是否存在局部最小值。如果有，则可以找到它。

论文地址：https://arxiv.org/abs/2008.06148

Ahmadi 表示，「我从未想过三次多项式会出现这么神奇的事情，使得它们的局部最小值这么容易就找到了。」总之，这两项研究的结果成为计算复杂性研究中的重要信号，证明了某些问题易于解决，另一些则必须很难解决。不仅如此，对于对从金融到自动化系统等多领域中优化问题感兴趣的研究者来说，这些结果还为他们提供了新的理论支撑。

Amir Ali Ahmadi（左），Jeffrey Zhang（右）

生活中的数学

想象一下，你负责的一家汽车厂仅生产两种型号的车——便宜车（Cheapo）和高级车（Deluxe）。后者卖的比前者多，因此花了更多钱来制作，并在生产线上花费的时间也更长。问题来了，你要如何分配便宜车和高级车的生产量呢？

这种二选一的困境转变成了一个多项式优化问题。

为了实现这一转变，你需要将此问题分割为三种不同的因素。这些因素都是有待优化的可量化变量，在汽车厂场景中，分别为你必须生产的汽车数量、预算和产能等约束条件以及所谓的目标函数，也即「每个变量如何促使你接近或远离自身目标」的总和。

Ahmadi 对此表示，「目标函数以决策变量为输入，并输出一个数字。这正是我们总是想要最小化或最大化的对象。」

汽车厂的因素变量是一个简单的优化问题。正如我们所描述的，假定所有变量都不会交互作用，意味着它们可以封装在一个线性函数中。但应看到，大多数现实世界的问题更加混乱，描述这些问题的数学也是如此。

汽车数学问题。图源：Max Levy

举例而言，如果你想要准确地找出洛杉矶到旧金山这条航线的最优枢纽。从交通或成本的角度来讲，每个机场都有自己的内在价值（线性贡献）。但是，二次项会影响如何选择以特定方式彼此交互作用的机场：如果洛杉矶以外交通非常繁忙的话，则建立一个离旧金山近的枢纽则获益更多。

当然，问题可能比上述更加复杂，变量之间的三向交互作用需要更复杂的三次多项式。

函数复杂性的每一步都允许对范围更广的问题进行建模。但是，复杂性的实现需要代价，无法获得保证，因此依然要计算最优解。

优化问题

现代优化理论在二战期间得以发展，彼时美国数学家 George Dantzig 为找出线性优化问题的解设计了一个流程。他的开创性工作帮助美国国防部从采购飞机到海外物资供应等诸多方面做出了明确决策。

线性规划之父 George Dantzig。

接下来几十年里，研究人员追寻他的脚步，在找出日益复杂的问题的最优解方面开发出了更快的算法。

但是，在 1980 年代，这方面的进展迎来了不可逾越的障碍。研究人员证实，解决优化问题的快速算法可能不存在。他们发现，优化问题从根本上来说太复杂，无法获得最优解。因此，如果无法获得最优解，则可以搜索近似解或者所谓的局部最优解。

局部最优解或许无法表示最佳结果，但它们胜过任何类似的解决方案。局部最优解是足够好的做决策方式，比如上述汽车厂场景中便宜车和高级车各生产多少，这无法通过一些变量的微小调整来改进。只有大的「重新洗牌」才能收获绝对最佳的成果，但对大规模问题来说，这种重新洗牌的方式在计算上投入太大。

基于此，1990 年代初期以来，研究人员试图确定是否存在找到局部最优解的快速方法。在二次和三次方程式中，Ahmadi 和 Zhang 终于找到了答案。

对于二次方程式，这是一个坏消息

当研究人员想要确定一个问题在计算上是否难以解决时，他们往往将该问题等同于复杂性已知的一些其他问题。如果你知道问题 A 难以解决，并证明解决问题 B 就能解决 A，则可以先解决问题 B。Zhang 表示，「这意味着我遇到的问题 B 一定不容易解决。」

在他们的第一篇论文中，Ahmadi 和 Zhang 将二次优化（其中成对的变量交互作用）的挑战与最大稳定集问题（maximum stable set problem）相匹配，后者是一个（被证明）难以解决的著名问题。他们使用一种平方和（sum of squares）来探索何时可以找到三次函数的局部最优解。

本质上来讲，「稳定集」是一个图中（没有两个节点直接连接）的任意节点列表，最大稳定集问题要求找到图的最大此类集。即使你只想知道是否存在某个给定大小的稳定集，确定答案在计算上也很复杂。

去年 6 月，Ahmadi 和 Zhang 将最大稳定集问题重新定义为寻找局部最优解的一个特例。他们提出了一种将稳定集问题表示为二次优化问题的方法，因此找到一个特定大小的稳定集就变成了寻找这个优化问题的局部最优解。

但考虑到他们二人已经知道不存在快速找到这些稳定集的方法，因此也就没有快速的方法来解决这个问题。这意味着对于这类稳定集问题，找到局部最优解与真正最优解一样难。

荷兰国家数学和计算机科学研究所的 Monique Laurent 表示，「直觉上，二次优化应该更容易。令人意外的是，Ahmadi 和 Zhang 的工作表明并不容易。」

对于三次方程式，这是一个好消息

Ahmadi 和 Zhang 的工作表明：总是能找到一些二次优化问题的局部最优解的高效算法并不存在。同时，他们想知道是否可以找到三次优化问题的局部最优解，这类优化问题带有「不包含任何约束的简化条件」。

三次多项式在许多实践方面都很重要，它们为思考变量之间的三阶交互作用提供了一个数学框架。此外，明确性（clarity ）的提升可以极大地改进文本挖掘等工具，其中你希望算法可以从大数据集中提取含义。

举例而言，假设你将一段文本输入计算机并要求它确定文本的内容。计算机观察到「Apple」这个单词频繁出现，但在没有更多信息的情况下，文本主题仍然模棱两可。加州理工学院的 Bren 教授 Anima Anandkumar 表示，「这可能是水果，也可能是苹果公司。」

此外，同时出现「Apple」和「Orange」两个单词会让你更有信心确定文本主题，但仍然可能是错的，因为 Orange 也可能是一家公司。如果又出现了类似「melon」（甜瓜）的第三个单词，则意味着引入了三次关系，可能会让你最终确定文本的主题是农产品（produce）。

但是，明确性的增加也使得复杂性增加，这就是为何 Zhang 最开始对三次优化问题不抱希望的原因。他表示，「当探索三次局部最小值的问题时，实际上我认为它是棘手的。」

从 2019 年初开始，Zhang 就探索了解决这个问题的不同方法。不过，他被困住了，直到 Ahmadi 建议他尝试使用平方和来解决。Ahmadi 就曾使用平方和解决其他优化问题。

研究的意义

Ahmadi 和 Zhang 的突破来自于他们发现可以通过使用平方和检验（sum-of-squares test）找到某些多项式的最低点，进而搜索三次函数的局部最优解。

在像 x^3 + 1 这样的三次多项式图中，一端总是趋向于负无穷大。所以，三次方永远不可能在任何地方都是非负的，也永远不可能总是平方和。

但是，Ahmadi 和 Zhang 想出了一种方法，专门关注图中曲线向上的部分。这正是他们应用平方和检验的地方。Zhang 对此表示，「对于三次曲线，我们总是可以将函数拖到自己想要的位置。」

他们的研究结果解决了「寻找三次函数局部最优解的难度」的重要理论问题。目前，他们正试图通过改进一种广泛使用的算法来提高它的实用价值，以便可以处理二次和三次关系。

对此，Laurent 表示，「如果他们成功完成这项工作，想必会非常有用。」

原文链接：https://www.quantamagazine.org/surprising-limits-discovered-in-quest-for-optimal-solutions-20211101/