編者按：一個世紀以前，偉大的數學家大衛·希爾伯特在第二屆國際數學家大會上作了題為《數學問題》的演講，其中提到了23道重要數學問題。時至今日，伴隨優化理論的最新進展，希爾伯特的第17問已經進入了一個名為自動駕駛汽車的嶄新世界。

小飛機完美避障背后是什么數學原理呢？

在機器人和汽車學會自動駕駛的很久以前，數學家們就已經開始思考一個基礎數學問題。他們弄明白了，然后把它放在一邊，開始證明新的問題……沒有人曾預料到，這個他們曾經好奇的對象，最后會應用在未來的機器中。

而現在，未來近在眼前。2017年，普林斯頓大學助理教授Amir Ali Ahmadi和Anirudha Majumdar在arXiv上發表了他們的新成果。他們把一個經典數學問題作為鐵腕證據，證明無人機和自動駕駛汽車不會撞到樹上，或是撞上迎面而來的其他交通工具。

這篇論文的名字是DSOS和SDSOS優化：基于平方和和半正定優化的更多可行替代方案。是的，汽車避障技術背后的數學原理似乎有些令人匪夷所思——一個被稱為“平方和”的數學問題。1900年，希爾伯特在大會上提問：對于某些類型的方程式，它們是否總是可以被寫成兩個有理函數的平方和。即：

實系數有理函數f(x1,…，xn)對任意數組(x1,…，xn)都恒大于或等于0，確定f是否都能寫成有理函數的平方和？

為了解決這個問題，數學家們苦心研究了二十幾年，直到1927年Emil Artin最終拿出了證明成果。之后，差不多是問題提出的90年后，計算機科學家和工程師把這個歷史塵封的問題再度挖了出來——非負多項式的平方和表示，認為它是解決許多現實問題一大利器。

然而，盡管研究人員意識到了平方和的作用，但具體把它部署進實施方案又完全是另一回事。而Ahmadi和Majumdar的新成果消除了諸多困難中最大的挑戰之一——將一個經典數學問題直接用于解決當今最重要的技術難題。

論文作者Amir Ali Ahmadi

非負性的保證

平方和是什么？對于從小接受中國數學教育的讀者，這個概念應該是信手拈來。比如數字13，把它轉成平方和形式就是13=22+32，同理，34=32+52。

希爾伯特提出的問題無關具體有理數，他希望證明某些多項式可以被表示為有理函數的平方和，比如5x2+16x+13=(x+2)2+(2x+3)2。

一旦一個多項式可以寫成平方和形式，我們就可以確定它是非負的，因為任何數的平方都大于等于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和特斯拉——以及大衛·希爾伯特。