枢纽|普林斯顿研究“最小值”：平方和的破局，二次和三次优化问题的极限( 二 )

枢纽航空公司在组织航班的时候，希望航班波的强度和密度越大越好，这样就可以提高单位时间内的中转效率，与此带来的单位时间内航班量过大，中转人数过多的高峰处理量，给机场和航空公司带来了巨大的运营压力和成本压力。也就是说，航空公司在枢纽机场的处理能力接近峰值后，会出现快速衰退，导致操作成本快速提高和服务质量急剧下降。
当然，还有很多问题可能比这更复杂。变量之间的三阶交互作用需要用到更复杂的函数。每一步函数复杂性都要为更广泛的问题建模，但是这种复杂性是有代价的，它可能计算不出最优解。

退而求其次，找出最佳“故障”

现代优化理论发展于第二次世界大战期间（1939年至1945），当时一位名叫 George Dantzig的科学家设计了一个寻找线性优化问题解的程序，被应用到美国国防部采购飞机和海外运送物资的战时实践上。
在接下来的几十年里，研究人员跟随George的领导，开发了更快的算法，为日益复杂的现实问题找到最佳解决方案。
但在20世纪80年代，这些进步遇到了一个不可逾越的障碍。研究人员发现，解决优化问题的快速算法不可能存在。他们认为，这些问题从根本上来说太复杂了。
如果无法获得最优解决方案，还能怎么办? 近似解，或者“局部”最优解。
局部最优解可能并不代表最佳结果，但它们比任何类似解都要好。它们是做出决策的“足够好”的方式，比如每辆车要生产多少辆，不能通过对某些变量的微小调整来改进，只有大规模的重组才能导致绝对最好的结果，但对于大问题，这种计算过于密集。
鉴于这一切，自20世纪90年代初以来，研究人员一直试图确定：是否存在一种快速找到局部最优解的方法。

二次方程的坏消息

当研究人员想要确定一个问题在计算上是否难以解决时，他们通常会将其等同于一些已知复杂性的问题。比如如果知道A问题很难解决，可以证明，解决问题B将为解决A提供一种方法。
在Amir Ali Ahmadi和Jeffrey Zhang的第一篇论文中，他们将二次优化的挑战与所谓的最大稳定集问题进行了匹配。当然，最大稳定集问题是一个著名的并且可证明的难题。
“稳定集”（stable set）是指图表中两个节点没有直接相连的任何节点列表。最大稳定集问题要即找到图表中最大规模的稳定集。即使你只想知道是否存在一个给定大小的稳定集，但要确定这个答案，计算相当复杂。
去年6月，Ahmadi和Zhang将最大稳定集问题重新定义为搜索局部最优解的特殊情况。他们提出了一种将稳定集问题表示为二次优化问题的方法。于是，寻找一个具有一定规模的稳定集就变成了寻找这个优化问题的局部最优解的问题。
但是他们知道，依然没有一种很快速的计算方法来找到这些稳定集，这意味着，对于二次函数优化问题，局部最优解和真正最优解一样难以找到。
“直觉上，局部最优解应该更容易，但出乎意料的是，他们二人证明两种解都很难。”荷兰国家数学和计算机科学研究所（CWI）的Monique Laurent说。

三次方程的好消息

Ahmadi和Zhang排除了总能找到某些二次优化问题局部最优解的有效算法的存在。与此同时，他们想知道：在不包含约束条件的简化条件下能够解决三次优化问题么?