对于三次方程式 ， 这是一个好消息
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/