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

小飛機完美避障背后是什么數(shù)學(xué)原理呢？

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

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

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

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

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

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

論文作者Amir Ali Ahmadi

非負(fù)性的保證

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

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

一旦一個多項式可以寫成平方和形式，我們就可以確定它是非負(fù)的，因為任何數(shù)的平方都大于等于0，而非負(fù)數(shù)相加一定是個非負(fù)數(shù)。據(jù)此我們可以進一步細(xì)化希爾伯特的猜想：所有非負(fù)多項式都可以被表示為有理函數(shù)的平方和。

這是個非常有用的數(shù)學(xué)定理。試想一下，如果你手里有一個復(fù)雜多項式，它可能包含10個或更多項，直接證明它的正負(fù)性是很困難的。因為有些多項式一看就是非負(fù)的，但有些卻不一定。如果多項式可以被表示為平方和，它就提供了非負(fù)性保證。

雖然從數(shù)學(xué)角度看，多項式是正是負(fù)很多時候無關(guān)緊要，但在希爾伯特提出問題的一個世紀(jì)后，這個非負(fù)性證明卻成了影響所有人的應(yīng)用問題。

論文研究參與者Georgina Hall

最好的方法

平方和和優(yōu)化問題已經(jīng)在現(xiàn)實世界相遇。優(yōu)化理論關(guān)注的是在約束條件下找出實現(xiàn)目標(biāo)的最佳方式——以自動化駕駛汽車為例，它需要規(guī)劃最佳行駛路線，并在遇到無法繞行的障礙物時及時剎車。在工程領(lǐng)域，這類場景通?？梢员惶釤挸啥囗検?，而優(yōu)化的方式就是找出方程的最小值。

事實上，對于包含多個變量的方程，找出最小值是一件非常困難的事。這不是高中數(shù)學(xué)題，我們手頭沒有直接的算法，繪制函數(shù)圖也相當(dāng)難實現(xiàn)。

所以在這種情況下，希爾伯特猜想就有了用武之地。拿華盛頓大學(xué)數(shù)學(xué)家Rekha Thomas的話說，“證明非負(fù)性是所有優(yōu)化問題的核心”。

找到最小值的一種思路是不斷問自己：在非負(fù)多項式變成負(fù)值之前，我可以減去多少？這個嘗試的過程可能會用到不同的值，比如這次減去3，方程還是非負(fù)的。那么減去4？減去5呢？在我們不斷重復(fù)這個過程時，平方和就可以被用來判斷多項式的政府情況。

一旦研究人員獲得最小值，也就是多項式的最優(yōu)解，他們就可以用一系列方法找出可以輸出這個值的所有輸入。當(dāng)然，這都是后話，整個過程的關(guān)鍵是如何找出一種可以快速計算多項式是平方和的方法。

按照希爾伯特的說法，研究人員解決這個問題需要100年。

大衛(wèi)·希爾伯特

打破僵局

從2000年起，希爾伯特的第17問開始從純數(shù)學(xué)轉(zhuǎn)向?qū)嶋H應(yīng)用。那時，一些研究人員想出過一種檢驗非負(fù)性的方法，他們把平方和問題轉(zhuǎn)換成“半正定規(guī)劃（SDP）”，這是計算機能夠處理的一類問題，它也為計算機科學(xué)和工程領(lǐng)域的研究人員打開了一條利用平方和非負(fù)性的道路。

當(dāng)然，SDP確實可以找到方程的平方和解，但它有個很大的局限，就是在復(fù)雜問題上非常慢，根本無法快速處理大家最關(guān)心的多項式。這個局限在現(xiàn)實任務(wù)中是致命的，以讓人形機器人保持站立為例，這個任務(wù)會涉及50個甚至更多變量，如果使用了SDP，可能直到最終結(jié)束，它都不一定能返回平方和的答案。

在Ahmadi和Majumdar的論文中，他們提出了一種解決半正定優(yōu)化過于緩慢的方法。他們不再求解單個SDP，而是把問題分解為一系列更簡單的“線性規(guī)劃”問題。

線性規(guī)劃是George Dantzig在20世紀(jì)40年代提出的一種運籌學(xué)方法，最初被用于計算兵力部署、人員訓(xùn)練、后勤補給等方案。發(fā)展到現(xiàn)在，它已經(jīng)成為一種易于理解且快速的常用方法。Ahmadi和Majumdar在論文中證明，通過解決大量相關(guān)的線性規(guī)劃問題，并把最終結(jié)果組合在一起，我們就可以獲得一個和SDP幾乎相同的答案。

而這篇論文的影響是，現(xiàn)在研究人員們多了一個實用的新工具，他們可以用它來測試非負(fù)性并快速找到平方和解。

我們研究了機器人和控制理論中的一些問題，證明我們的解決方案在實踐中仍然有用，而且計算速度更快。——Majumdar

論文作者Anirudha Majumdar

安全保障

放到現(xiàn)實生活中，當(dāng)我們乘坐自動駕駛汽車時，系統(tǒng)建立的多項式可以是如何避開所有路障，而環(huán)境是不斷變化的。因此，如果要實現(xiàn)安全駕駛，汽車就必須在短時間內(nèi)找出最佳路徑。這意味著計算平方和解的速度掌控著一切。

想象一個簡單的場景：一個巨型停車場，一輛自動駕駛汽車，除了遠處的警衛(wèi)室，你周圍空無一物。你的目標(biāo)是給汽車編程，讓它不要撞進警衛(wèi)室。

在這種情況下，首先我們需要在地上放一個網(wǎng)格坐標(biāo)，然后創(chuàng)建一個多項式，以坐標(biāo)位置為輸入。當(dāng)輸入汽車位置時，多項式是個負(fù)值；輸入警衛(wèi)室位置后，多項式則是正值。

現(xiàn)在，汽車和警衛(wèi)室之間存在某些坐標(biāo)點，它們讓多項式經(jīng)歷了從負(fù)到正的過程。由于汽車的位置只能為負(fù)，我們可以把這些點看成一堵堵墻。這里有個值得注意的點，如果一堵墻剛好卡在汽車和警衛(wèi)室之間，它會是最佳方案嗎？

顯然不是，我們的目標(biāo)是讓汽車無限靠近墻，而不是經(jīng)過墻所在的位置。最佳方案應(yīng)該是在不撞到警衛(wèi)室的同時，也為汽車預(yù)留了足夠的移動空間。這也是設(shè)計多項式時需要考慮的因素。

從數(shù)學(xué)角度看，我們希望最小化的值是墻到警衛(wèi)室的距離，也就是多項式如果要保持是個非負(fù)數(shù)，它最多可以減少多少。而這個過程可以用計算平方和來檢測。

然而，空空蕩蕩的停車場是一回事，真正駕駛場景又是另一回事。在現(xiàn)實環(huán)境中，汽車的傳感器會不斷識別新的、變化的障礙物——汽車、自行車、兒童。每當(dāng)出現(xiàn)新的障礙物，自動駕駛系統(tǒng)就必須精心設(shè)計更多的多項式，來盡可能規(guī)避所有碰撞。

七年前，研究人員想過用這種多項式讓自動駕駛汽車駛上“正軌”。但由于計算速度太慢，這個想法只能被作為夢想。

七年后，Ahmadi和Majumdar的新方法為快速計算提供了一種可能。如果未來自動駕駛汽車真的能實現(xiàn)安全駕駛，也能在全球普及，我們會感謝他們，感謝Google和特斯拉——以及大衛(wèi)·希爾伯特。