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

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

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

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

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

史教授基于能測距離這一要素，不斷極小化當前點到目標點的距離，從計算機角度稱為是貪心算法。

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

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

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

史教授這樣做法存有一定的風險，因為需要靠近有槍的劫匪。我們事后諸葛亮地問問，在不靠近車輛的前提下，史教授還有其他選擇嗎？（也就是說，僅由相對距離，是否能夠定位？）

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

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

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

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

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

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

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

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