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

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

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

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

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

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

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

然而，盡管研究人員意識到了平方和的作用，但具體把它部署進(jìn)實(shí)施方案又完全是另一回事。而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ù)，他希望證明某些多項(xiàng)式可以被表示為有理函數(shù)的平方和，比如5x2+16x+13=(x+2)2+(2x+3)2。

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

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

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

論文研究參與者Georgina Hall

最好的方法

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

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

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

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

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

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

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

打破僵局

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

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

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

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

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

我們研究了機(jī)器人和控制理論中的一些問題，證明我們的解決方案在實(shí)踐中仍然有用，而且計(jì)算速度更快?！狹ajumdar

論文作者Anirudha Majumdar

安全保障

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

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

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

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

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

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

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

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

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