距離幾何優(yōu)化問(wèn)題：從美國(guó)計(jì)算機(jī)教授追回被搶車輛談起

不久前，新智元報(bào)道了美國(guó)某大學(xué)計(jì)算機(jī)系終身副教授一家人遭兩名劫匪搶去汽車，在不到24小時(shí)之內(nèi)，這名教授通過(guò)手機(jī)發(fā)動(dòng)應(yīng)用程序和計(jì)算機(jī)算法成功將車找回。本文首先介紹其算法從優(yōu)化角度的解釋，進(jìn)一步從優(yōu)化的角度提出更好的解決方案。

2018年12月中下旬的周末，美國(guó)某大學(xué)計(jì)算機(jī)系終身副教授，博士生導(dǎo)師史弋宇教授全家旅行途中在一座加油站遇到了兩名持槍劫匪。劫匪搶走了史教授的錢(qián)包和馬自達(dá)汽車，讓這次旅行泡湯。

在警察也束手無(wú)策的狀況下，史教授回憶起馬自達(dá)車裝有手機(jī)發(fā)動(dòng)應(yīng)用程序（Mazda Mobile Start，MMS），該程序能方便使用者利用手機(jī)遠(yuǎn)程發(fā)動(dòng)汽車引擎和給車輛上鎖和開(kāi)鎖，也能幫助使用者找到停車地點(diǎn)，但是當(dāng)時(shí)手機(jī)app界面僅顯示一個(gè)紅點(diǎn)（代表車的位置）和一個(gè)大圈（代表車的范圍），右上角有距離顯示81.8英里和相對(duì)誤差+/- 22 英尺。除此之外，沒(méi)有地圖，沒(méi)有提供GPS坐標(biāo)。這意味著可用的信息只有手機(jī)和車的直線距離。

史教授選擇了計(jì)算機(jī)算法中最直接的貪心算法，也就是沿著一個(gè)方向開(kāi)，直到距離不再明顯變?。ㄟ@說(shuō)明他們前進(jìn)的方向已經(jīng)幾乎垂直于他們和目標(biāo)之間連線），就轉(zhuǎn)到垂直方向的街道再繼續(xù)搜尋。最終，在被搶不到24小時(shí)，史教授成功把車追回。

連現(xiàn)場(chǎng)的警察都感嘆：“They shouldn’t have messed up with computer science professors!（他們不該惹上計(jì)算機(jī)教授?。?（詳情可見(jiàn)新智元文章《清華畢業(yè)計(jì)算機(jī)教授遭持槍劫車！靠“貪心算法”追回秒殺美國(guó)警察》。）

史教授基于能測(cè)距離這一要素，不斷極小化當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的距離，從計(jì)算機(jī)角度稱為是貪心算法。

從最優(yōu)化算法的角度來(lái)看，優(yōu)化的問(wèn)題是，這是一個(gè)凸二次函數(shù)，沿著一個(gè)方向開(kāi)，直到與目標(biāo)距離達(dá)到最?。▽?shí)際路況中由于不能調(diào)頭，這一點(diǎn)通過(guò)直到距離不再明顯變小來(lái)驗(yàn)證），這是最優(yōu)化中最經(jīng)典的精確線搜索方法(exact line search), 該方法有一個(gè)重要特性，在這個(gè)方向上的最優(yōu)點(diǎn)處，梯度方向和該方向正交（垂直）。

因此，史教授選擇在前一方向上最優(yōu)點(diǎn)處換沿垂直方向搜索，由于問(wèn)題是2維平面上的優(yōu)化問(wèn)題，此時(shí)的方向恰恰就是負(fù)梯度方向，下一步做的就是最速下降法。該優(yōu)化問(wèn)題是一個(gè)海色矩陣為單位陣的凸二次優(yōu)化問(wèn)題，所以，最速下降法迭代一步就可以終止到唯一的全局最優(yōu)解。

如圖所示。讀者也可以通過(guò)很簡(jiǎn)單的平面幾何來(lái)驗(yàn)證這一性質(zhì)。由于實(shí)際路況的復(fù)雜性，比如路線可能不全程是直線，方向上的最優(yōu)點(diǎn)處不能立刻拐彎，所以是一個(gè)非精確線搜索的下降算法，由于迭代中的距離嚴(yán)格單調(diào)遞減，在道路連通等適當(dāng)條件下能期待收斂到0，即找到最優(yōu)解。

史教授這樣做法存有一定的風(fēng)險(xiǎn)，因?yàn)樾枰拷袠尩慕俜?。我們事后諸葛亮地問(wèn)問(wèn)，在不靠近車輛的前提下，史教授還有其他選擇嗎？（也就是說(shuō)，僅由相對(duì)距離，是否能夠定位？）

如上圖所示，我們選擇遠(yuǎn)離目標(biāo)的不共線的三點(diǎn)A，B，C，記其GPS坐標(biāo)分別為, 從這三點(diǎn)測(cè)一下到目標(biāo)的距離,記為. 設(shè)目標(biāo)點(diǎn)的GPS坐標(biāo)為(x,y)，那么我們有如下三個(gè)方程：

將(1)分別代入(2)和(3)，化簡(jiǎn)得一個(gè)二元線性方程組

由于ABC三點(diǎn)不共線，所以上述線性方程組系數(shù)矩陣非奇異，從而方程組有唯一解，其解確定未知目標(biāo)點(diǎn)。使用該方法提供警方被搶車輛坐標(biāo)，可以避免與劫匪近距離接觸，真正做到了運(yùn)籌帷幄之中，決勝千里之外。

實(shí)際中，由于距離的測(cè)量存在誤差，這直接影響到未知解的精度。為了盡可能控制誤差的影響，通常多選一些已知的觀測(cè)點(diǎn)，設(shè)它們的坐標(biāo)為，測(cè)出距離為。這樣我們建模得到如下非線性最小二乘問(wèn)題：

該問(wèn)題關(guān)于x,y是非凸的，但是問(wèn)題可以等價(jià)轉(zhuǎn)化為：

這是一個(gè)單個(gè)二次約束的二次優(yōu)化問(wèn)題，也是廣義的信賴域子問(wèn)題，具有隱凸性質(zhì)和強(qiáng)對(duì)偶性質(zhì)[1]，其全局最優(yōu)解是能夠在多項(xiàng)式時(shí)間內(nèi)快速解得，感興趣的讀者可以參考《等式S-引理的理論與應(yīng)用》。此外，針對(duì)定位問(wèn)題還有其它一些非凸優(yōu)化模型，如

該問(wèn)題實(shí)際上稱為GPS定位問(wèn)題[2]，GPS系統(tǒng)使用至少4顆衛(wèi)星的位置以及它們到地球上人的距離可以計(jì)算出人的坐標(biāo)，其計(jì)算原理同上。實(shí)際上，我們這里提到的兩個(gè)優(yōu)化模型正是來(lái)自GPS定位問(wèn)題[2]。

該問(wèn)題的進(jìn)一步推廣是距離幾何問(wèn)題：給定若干個(gè)點(diǎn)，其中某一些點(diǎn)的位置已知，這些點(diǎn)也稱為錨點(diǎn)，另外已知一部分點(diǎn)與點(diǎn)間的距離，要求確定所有點(diǎn)的位置坐標(biāo)。該問(wèn)題在傳感性定位[3]以及蛋白質(zhì)結(jié)構(gòu)解析[4]中有重要的應(yīng)用。