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

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

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

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

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

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

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

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

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

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

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

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

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

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

該問題關(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)星的位置以及它們到地球上人的距離可以計算出人的坐標(biāo)，其計算原理同上。實際上，我們這里提到的兩個優(yōu)化模型正是來自GPS定位問題[2]。

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