按关键词阅读：
在接下来的几十年里，研究人员跟随George的领导，开发了更快的算法，为日益复杂的现实问题找到最佳解决方案。
但在20世纪80年代，这些进步遇到了一个不可逾越的障碍。研究人员发现，解决优化问题的快速算法不可能存在。他们认为，这些问题从根本上来说太复杂了。
如果无法获得最优解决方案，还能怎么办? 近似解，或者“局部”最优解。
局部最优解可能并不代表最佳结果，但它们比任何类似解都要好。它们是做出决策的“足够好”的方式，比如每辆车要生产多少辆，不能通过对某些变量的微小调整来改进，只有大规模的重组才能导致绝对最好的结果，但对于大问题，这种计算过于密集。
鉴于这一切，自20世纪90年代初以来，研究人员一直试图确定：是否存在一种快速找到局部最优解的方法。
在Amir Ali Ahmadi和Jeffrey Zhang的第一篇论文中，他们将二次优化的挑战与所谓的最大稳定集问题进行了匹配。当然，最大稳定集问题是一个著名的并且可证明的难题。
“稳定集”（stable set）是指图表中两个节点没有直接相连的任何节点列表。最大稳定集问题要即找到图表中最大规模的稳定集。即使你只想知道是否存在一个给定大小的稳定集，但要确定这个答案，计算相当复杂。
去年6月，Ahmadi和Zhang将最大稳定集问题重新定义为搜索局部最优解的特殊情况。他们提出了一种将稳定集问题表示为二次优化问题的方法。于是，寻找一个具有一定规模的稳定集就变成了寻找这个优化问题的局部最优解的问题。
但是他们知道，依然没有一种很快速的计算方法来找到这些稳定集，这意味着，对于二次函数优化问题，局部最优解和真正最优解一样难以找到。
“直觉上，局部最优解应该更容易，但出乎意料的是，他们二人证明两种解都很难。”荷兰国家数学和计算机科学研究所（CWI）的Monique Laurent说。
三次多项式在许多实际方法中都很重要。它们为思考变量之间的三阶相互作用提供了一个数学框架。增加一种关系使得关系的清晰度提高，从而极大地改善机器学习性能，比如在文本挖掘中，大家希望算法能从大数据集中提取意义。
例如，你向计算机输入一段文本，并要求它确定这段文本的内容。计算机注意到“苹果”这个词经常出现，但是没有更多的信息，导致“苹果”这个词语仍有歧义。
可能是水果，也可能是公司，或者其他。
但如果“苹果”和“橘子”同时出现，计算机会更加确定这是水果。但还是有可能出错，因为橘子也可能是一家公司。所以这时候引入第三个词语，如“瓜”，即引入了立体关系，可能会更加确信文本谈论的是农产品。
但是，清晰度的增加也带来了复杂性。
从2019年初，Zhang就开始探索解决这个问题的不同方法，但被卡住了，直到Ahmadi建议他尝试一种叫做平方和的技术，Ahmadi以前曾用这种技术解决其他优化问题。
平方和揭示了最初输入的多项式的属性。因为实数的平方不可能为负，所以如果将一个多项式表示为平方和，证明它总是输出一个非负值。这是一种快速的检验方法。然而，这种方法在有约束的二次优化问题中不起作用，这就是为什么Ahmadi和Zhang不能在他们的二次方程中利用它。
稿源：(雷峰网)
【傻大方】网址：/c/1125a51532021.html
标题：复杂性|普林斯顿研究“最小值”：平方和的破局，二次和三次优化问题的极限( 二 )