某种程度上来讲，我们的生活由连续的优化成绩组成。当搜索从工作场所返家的最快路程时，我们会遇到优化成绩；当去商店的途中试图平衡成本（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.06148Ahmadi 表明，「我从未想过三次多项式会出现这么神奇的事情，使得它们的全部最小值这么容易就找到了。」总之，这两项研讨的结果成为估计简单性研讨中的重要信号，证明了某些成绩易于处理，另一些则必须很难处理。不仅如此，对于对从金融到自动化系统等多领域中优化成绩感兴趣的研讨者来说，这些结果还为他们提供了新的理论支撑。
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/
原创文章，作者：机器之心，如若转载，请注明出处：https://www.iaiol.com/news/28972
