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

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

某种程度上来讲 ， 我们的生活由连续的优化问题组成 。 当搜索从工作场所返家的最快路程时 ， 我们会遇到优化问题；当去商店的途中试图平衡成本（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 对此表示 ， 「目标函数以决策变量为输入 ， 并输出一个数字 。 这正是我们总是想要最小化或最大化的对象 。 」
汽车厂的因素变量是一个简单的优化问题 。 正如我们所描述的 ， 假定所有变量都不会交互作用 ， 意味着它们可以封装在一个线性函数中 。 但应看到 ， 大多数现实世界的问题更加混乱 ， 描述这些问题的数学也是如此 。

文章图片