当古典数学问题被拉入现代世界：希尔伯特23问与机器学习算法

来源：Quanta Magazine

编译：Bot

编者按：一个世纪以前，伟大的数学家大卫·希尔伯特在第二届国际数学家大会上作了题为《数学问题》的演讲，其中提到了23道重要数学问题。时至今日，伴随优化理论的最新进展，希尔伯特的第17问已经进入了一个名为自动驾驶汽车的崭新世界。

小飞机完美避障背后是什么数学原理呢？

在机器人和汽车学会自动驾驶的很久以前，数学家们就已经开始思考一个基础数学问题。他们弄明白了，然后把它放在一边，开始证明新的问题……没有人曾预料到，这个他们曾经好奇的对象，最后会应用在未来的机器中。

而现在，未来近在眼前。2017年，普林斯顿大学助理教授Amir Ali Ahmadi和Anirudha Majumdar在arXiv上发表了他们的新成果。他们把一个经典数学问题作为铁腕证据，证明无人机和自动驾驶汽车不会撞到树上，或是撞上迎面而来的其他交通工具。

这篇论文的名字是DSOS和SDSOS优化：基于平方和和半正定优化的更多可行替代方案。是的，汽车避障技术背后的数学原理似乎有些令人匪夷所思——一个被称为“平方和”的数学问题。1900年，希尔伯特在大会上提问：对于某些类型的方程式，它们是否总是可以被写成两个有理函数的平方和。即：

实系数有理函数f(x₁,…，x_n)对任意数组(x₁,…，x_n)都恒大于或等于0，确定f是否都能写成有理函数的平方和？

为了解决这个问题，数学家们苦心研究了二十几年，直到1927年Emil Artin最终拿出了证明成果。之后，差不多是问题提出的90年后，计算机科学家和工程师把这个历史尘封的问题再度挖了出来——非负多项式的平方和表示，认为它是解决许多现实问题一大利器。

然而，尽管研究人员意识到了平方和的作用，但具体把它部署进实施方案又完全是另一回事。而Ahmadi和Majumdar的新成果消除了诸多困难中最大的挑战之一——将一个经典数学问题直接用于解决当今最重要的技术难题。

论文作者Amir Ali Ahmadi

非负性的保证

平方和是什么？对于从小接受中国数学教育的读者，这个概念应该是信手拈来。比如数字13，把它转成平方和形式就是13=2²+3²，同理，34=3²+5²。

希尔伯特提出的问题无关具体有理数，他希望证明某些多项式可以被表示为有理函数的平方和，比如5x²+16x+13=(x+2)²+(2x+3)²。

一旦一个多项式可以写成平方和形式，我们就可以确定它是非负的，因为任何数的平方都大于等于0，而非负数相加一定是个非负数。据此我们可以进一步细化希尔伯特的猜想：所有非负多项式都可以被表示为有理函数的平方和。

这是个非常有用的数学定理。试想一下，如果你手里有一个复杂多项式，它可能包含10个或更多项，直接证明它的正负性是很困难的。因为有些多项式一看就是非负的，但有些却不一定。如果多项式可以被表示为平方和，它就提供了非负性保证。

虽然从数学角度看，多项式是正是负很多时候无关紧要，但在希尔伯特提出问题的一个世纪后，这个非负性证明却成了影响所有人的应用问题。

论文研究参与者Georgina Hall

最好的方法

平方和和优化问题已经在现实世界相遇。优化理论关注的是在约束条件下找出实现目标的最佳方式——以自动化驾驶汽车为例，它需要规划最佳行驶路线，并在遇到无法绕行的障碍物时及时刹车。在工程领域，这类场景通常可以被提炼成多项式，而优化的方式就是找出方程的最小值。

事实上，对于包含多个变量的方程，找出最小值是一件非常困难的事。这不是高中数学题，我们手头没有直接的算法，绘制函数图也相当难实现。

所以在这种情况下，希尔伯特猜想就有了用武之地。拿华盛顿大学数学家Rekha Thomas的话说，“证明非负性是所有优化问题的核心”。

找到最小值的一种思路是不断问自己：在非负多项式变成负值之前，我可以减去多少？这个尝试的过程可能会用到不同的值，比如这次减去3，方程还是非负的。那么减去4？减去5呢？在我们不断重复这个过程时，平方和就可以被用来判断多项式的政府情况。

一旦研究人员获得最小值，也就是多项式的最优解，他们就可以用一系列方法找出可以输出这个值的所有输入。当然，这都是后话，整个过程的关键是如何找出一种可以快速计算多项式是平方和的方法。

按照希尔伯特的说法，研究人员解决这个问题需要100年。

大卫·希尔伯特

打破僵局

从2000年起，希尔伯特的第17问开始从纯数学转向实际应用。那时，一些研究人员想出过一种检验非负性的方法，他们把平方和问题转换成“半正定规划（SDP）”，这是计算机能够处理的一类问题，它也为计算机科学和工程领域的研究人员打开了一条利用平方和非负性的道路。

当然，SDP确实可以找到方程的平方和解，但它有个很大的局限，就是在复杂问题上非常慢，根本无法快速处理大家最关心的多项式。这个局限在现实任务中是致命的，以让人形机器人保持站立为例，这个任务会涉及50个甚至更多变量，如果使用了SDP，可能直到最终结束，它都不一定能返回平方和的答案。

在Ahmadi和Majumdar的论文中，他们提出了一种解决半正定优化过于缓慢的方法。他们不再求解单个SDP，而是把问题分解为一系列更简单的“线性规划”问题。

线性规划是George Dantzig在20世纪40年代提出的一种运筹学方法，最初被用于计算兵力部署、人员训练、后勤补给等方案。发展到现在，它已经成为一种易于理解且快速的常用方法。Ahmadi和Majumdar在论文中证明，通过解决大量相关的线性规划问题，并把最终结果组合在一起，我们就可以获得一个和SDP几乎相同的答案。

而这篇论文的影响是，现在研究人员们多了一个实用的新工具，他们可以用它来测试非负性并快速找到平方和解。

我们研究了机器人和控制理论中的一些问题，证明我们的解决方案在实践中仍然有用，而且计算速度更快。——Majumdar

论文作者Anirudha Majumdar

安全保障

放到现实生活中，当我们乘坐自动驾驶汽车时，系统建立的多项式可以是如何避开所有路障，而环境是不断变化的。因此，如果要实现安全驾驶，汽车就必须在短时间内找出最佳路径。这意味着计算平方和解的速度掌控着一切。

想象一个简单的场景：一个巨型停车场，一辆自动驾驶汽车，除了远处的警卫室，你周围空无一物。你的目标是给汽车编程，让它不要撞进警卫室。

在这种情况下，首先我们需要在地上放一个网格坐标，然后创建一个多项式，以坐标位置为输入。当输入汽车位置时，多项式是个负值；输入警卫室位置后，多项式则是正值。

现在，汽车和警卫室之间存在某些坐标点，它们让多项式经历了从负到正的过程。由于汽车的位置只能为负，我们可以把这些点看成一堵堵墙。这里有个值得注意的点，如果一堵墙刚好卡在汽车和警卫室之间，它会是最佳方案吗？

显然不是，我们的目标是让汽车无限靠近墙，而不是经过墙所在的位置。最佳方案应该是在不撞到警卫室的同时，也为汽车预留了足够的移动空间。这也是设计多项式时需要考虑的因素。

从数学角度看，我们希望最小化的值是墙到警卫室的距离，也就是多项式如果要保持是个非负数，它最多可以减少多少。而这个过程可以用计算平方和来检测。

然而，空空荡荡的停车场是一回事，真正驾驶场景又是另一回事。在现实环境中，汽车的传感器会不断识别新的、变化的障碍物——汽车、自行车、儿童。每当出现新的障碍物，自动驾驶系统就必须精心设计更多的多项式，来尽可能规避所有碰撞。

七年前，研究人员想过用这种多项式让自动驾驶汽车驶上“正轨”。但由于计算速度太慢，这个想法只能被作为梦想。

七年后，Ahmadi和Majumdar的新方法为快速计算提供了一种可能。如果未来自动驾驶汽车真的能实现安全驾驶，也能在全球普及，我们会感谢他们，感谢Google和特斯拉——以及大卫·希尔伯特。

【1】原文地址：www.quantamagazine.org/a-classical-math-problem-gets-pulled-into-the-modern-world-20180523/

【2】论文地址：arxiv.org/pdf/1706.02586.pdf