一百年前，伟大的数学家戴维·希尔伯特（David Hilbert）从纯数学领域提出了一个研究问题。 优化理论的最新发展将希尔伯特的工作带到了机器人世界
在机器人可以运行，汽车可以自行驾驶之前很久，数学家就认为这是一个简单的数学问题。 最终，他们将其整理并放在一边-无法知道他们的数学好奇心会在遥远的未来机器中显现出来。
未来已经来临。 普林斯顿大学
的 Amir Ali Ahmadi和
Aniruda Majumara进行了
新的研究，纯数学的经典问题已准备就绪，可以为自动无人机和自动驾驶汽车不会撞到树上或滑入驶入的车道提供铁证。
与Ahmadi合作完成这项工作的普林斯顿大学研究生
Georgina Hall说：“系统具有100％可证明的全面保证，可以避免碰撞。”
普林斯顿大学教授Amir Ali Ahmadi保修是在一个意想不到的地方进行的，即一个称为“
平方和 ”的数学问题。 它是由伟大的数学家戴维·希尔伯特（David Hilbert）于1900年提出的。 他询问某些方程式是否始终可以表示为两个独立项的总和，每个项均平方。
几十年后，数学家回答了希尔伯特的问题。 然后，将近90年后，计算机科学家和工程师发现了这种数学特性-以平方和表示方程的可表达性-帮助解决了他们想解决的许多实际问题。
“我的工作中使用了19世纪的许多经典数学，以及非常现代的计算数学，” Ahmadi说。
但是，一旦研究人员意识到平方和可以帮助回答许多类型的问题，他们就会遇到使用这种方法的问题。 这项新工作消除了最大的此类问题之一，迫使旧的数学问题解决了我们这个时代最重要的技术问题。
积极保证
一定数量是平方和意味着什么？ 取数字13。这是两个平方2
2和3
2的总和。 数字34是3
2和5
2的总和。
希尔伯特的问题不是数字，而是他在20世纪初提出的23个
问题中的第17个
问题 ，它涉及多项式，例如5x
2 + 16x +13。这样的多项式有时也可以表示为平方和。 例如，可以将5x
2 + 16x + 13重写为（x + 2）
2 +（2x + 3）
2 。
当一个表达式是平方和时，您就会知道它始终是正数（所有[实数]平方都给出正数或零，而正数之和为正）。 希尔伯特想知道这是否相反：所有非负多项式都可以表示为有理函数的平方和。 1927年，数学家Emil Artin证明了希尔伯特的假设是正确的。
这种关系非常有用。 如果为您提供了一个复杂的多项式，其中将数十个变量提高到最高程度，则很难立即确定它是否始终为负数。 “一些多项式显然是非负的，其他多项式不是。 很难测试它们的非负性，” Ahmadi说。
但是，只要您证明该多项式可以用平方和表示，那么非负性就是这种情况的结果。 麻省理工学院的计算机科学家兼工程师
Pablo Parrilo说：“平方和给您美丽的阳性证明。”他参与了将平方和问题引入应用程序世界。
知道一个特定的多项式总是非负的，这似乎很简单。 但是在希尔伯特提出问题一百年后，多项式的非负性才成为解决影响我们所有人的实际问题的答案。
最好的方法
平方和与优化领域的现实世界相吻合。
优化理论全神贯注于在约束内寻找最佳方法，例如，根据路况和沿途需要停靠的地方，找到上班的最佳途径。 这样的场景通常可以简化为多项式。 在这种情况下，可以通过找到多项式采用的最小值来解决或“优化”方案。
寻找具有多个变量的多项式的最小值是一项艰巨的任务。 教科书中没有简单的算法可以计算复杂多项式的最小值；此外，很难在图形上构造它们。
乔治娜·霍尔由于多项式的最小值难以直接计算，因此研究人员通过其他方法对此值进行了假设。 这就是非负性发挥作用的地方，也是多项式是否为平方和的问题。 华盛顿大学的数学家Reha Thomas说：“确保非负性是所有优化问题的本质。”
找到最小值的一种方法是提出一个问题：可以从非负多项式中减去哪个最大值，以使它在某些时候不会变为负数？ 要回答这个问题，有必要检查各种值-是否可以减去3使其不会变为负数？ 和4？ 和5？ 重复该过程，在每个步骤中，您都需要知道多项式是否保持非负值。 通过将其表示为平方和的可能性可以验证这一点。
艾哈迈迪说：“需要问的问题是：多项式是非负的吗？”问题是，变量众多，这个问题很难回答。 “因此，我们使用平方和代替非负性。”
一旦研究人员意识到最小值（多项式的最优值），他们便可以使用其他方法来确定导致该值的输入参数。 但是，为了使非负性有助于解决优化问题，您需要想出一种方法来快速计算是否用平方和表示多项式。 为了使研究人员能够做到这一点，从希尔伯特提出问题的那一刻起花了100年。
解决问题
希尔伯特（Hilbert）的第17个问题在2000年左右从纯粹的数学世界转移到了应用平面。 那时，几位研究人员提出了一种算法，用于检查多项式是否可以用平方和表示。 他们通过“
半定义编程 ”解决了方形问题，从而使计算机达到了这一目标。 这使来自计算机科学和工程学等领域的研究人员可以利用非负性的可能性将他们的搜索引导到解决问题的最佳方法。
阿尼鲁达·马朱达（Aniruda Majumdar）但是半定程序设计有一个很大的局限性：它在大型任务上运行缓慢，并且无法处理研究人员特别感兴趣的一些最复杂的多项式。 半定义编程可用于将这样的多项式分解为平方和，这些多项式由不超过12个变量的乘方幂不超过6构成。多项式描述了复杂的工程问题，例如，确保机器人会站稳脚跟。输入50个变量，甚至更多。 程序可以咀嚼这样的多项式直到时间结束，但仍然不会给出平方和。
在去年6月在线发表的
一篇论文中 ，Ahmadi和Majumdar解释了如何解决半定义编程的缓慢工作。 他们展示了如何使用解决方案来做到这一点，而不是尝试通过一个缓慢的程序来求平方和的分解。
较简单的任务序列，计算起来会更快。
这种任务称为“线性”任务，它们于1940年代开发，用于解决与军事问题有关的优化问题。 现在已经很好地理解了行程序，并可以快速解决。 在一份新论文中，Ahmadi和Majumdar表明可以解决许多连接的线性程序（或者在某些情况下，解决另一种类型的问题，即二阶锥程序）的问题，并将结果组合起来几乎可以得出答案。 ，这可以为半定义编程提供程序。 因此，工程师拥有了一种新的实用工具，可用于检查非负性并快速找到平方和的分解。
Majumdar说：“我们研究了机器人技术和控制理论的几个问题，并证明了所得解决方案的质量对实际使用非常有用，而且计算速度也快得多。”
安全证明
如果您使用的是机器人，那么决定速度就是一切。 在这种情况下，多项式可以用作围绕您不想撞到的障碍物的数学障碍物（如果可以足够快地计算出来的话）。
想象一个简单的例子：大型停车场中的自动驾驶汽车。 除了远端的安全亭外，停车场什么都没有。 您的任务是对机器进行编程，以使其永远不会崩溃到该摊位中。
在这种情况下，您可以将网格拉入停车场。 然后制作一个将网格上的点作为输入的多项式。 确保机器位置处的多项式的值为负，并且护卫室位置处的多项式为正。
在您的汽车和展位之间的一些点上，多项式将从负数变为正数。 由于您的汽车只能位于多项式为负的位置，因此这些点将起到隔离墙的作用。
“如果您从某个地方开始，那么机器人将不会越过障碍物所在的线。 这为您提供避免碰撞的正式证据，”艾哈迈迪说。
当然，如果此墙位于机器和展位之间路径的中间，将会很不方便。 必须建立一个多项式，以使墙尽可能紧密地围绕障碍物。 此选项将保护展位，并为汽车提供很大的移动空间。
实际上，必须最小化该值-墙和盒子之间的距离-因此您需要移动多项式的图，并查看它可以移动多远，直到它从负到正为止。 这是通过检查多项式是否仍为平方和来实现的。
几乎空着的停车场是一回事。 但是在控制机器的现实场景中，其传感器会不断检测新的移动障碍物-汽车，自行车，儿童。 每次出现新障碍物或已知障碍物移动时，机器都需要构建新的复杂多项式来包围这些障碍物。 这是对必须即时执行的平方数的大量检查。
七年前，另一对研究人员已经想象到，这种用于多项式处理的技术可能能够用于分离机器人和那些不应该掉落的地方。 但是在那时，计算机的强大功能使这个想法成为了梦想。
Ahmadi和Majumdar的新方法开辟了进行此类即时计算的新方法。 因此，如果以及何时机器人能够安全地在世界范围内移动，我们要感谢Google和Tesla-以及Hilbert。