【寻找局部最优解，普林斯顿学者：三次优化问题比二次更易于实现】汽车数学问题 。 图源：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 的工作表明并不容易 。 」