7
搜寻最优解时发现令人惊讶的限制
source link: https://www.solidot.org/story?sid=69466
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
搜寻最优解时发现令人惊讶的限制
我们的生活是一连串的优化问题。当我们寻找下班回家的最快路线或在去商店的路上试图平衡成本和质量时，甚至当我们决定如何度过睡前有限的空闲时间时，就会出现此类问题。
这些场景和许多其他场景可以表示为数学优化问题。做出最佳决策就是找到最优解。对于一个沉浸在优化中的世界，最近的两项研究成果既带来了好消息也带来了坏消息。
在 2020 年 8 月发表的一篇论文中，普林斯顿大学的 Amir Ali Ahmadi 和他以前的学生、现就读于卡内基梅隆大学的 Jeffrey Zhang 确定，对于一些二次优化问题（这类问题中成对的变量会相互作用），在计算上以具有时效性的方式即使是寻找局部最优解也是不可行的。
但是两天之后，Zhang 和 Ahmadi 发表了第二篇论文，给出了积极的结论。他们证明，快速确定三次多项式（变量之间存在三向相互作用）是否存在局部最小值并找到这个值（如果存在的话）总是可行的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK