距离几何优化问题：从美国计算机教授追回被抢车辆谈起

tilldream

2018年12月中下旬的周末，美国某大学计算机系终身副教授，博士生导师史弋宇教授全家旅行途中在一座加油站遇到了两名持枪劫匪。劫匪抢走了史教授的钱包和马自达汽车，让这次旅行泡汤。

在警察也束手无策的状况下，史教授回忆起马自达车装有手机发动应用程序（Mazda Mobile Start，MMS），该程序能方便使用者利用手机远程发动汽车引擎和给车辆上锁和开锁，也能帮助使用者找到停车地点，但是当时手机app界面仅显示一个红点（代表车的位置）和一个大圈（代表车的范围），右上角有距离显示81.8英里和相对误差+/- 22 英尺。除此之外，没有地图，没有提供GPS坐标。这意味着可用的信息只有手机和车的直线距离。

史教授选择了计算机算法中最直接的贪心算法，也就是沿着一个方向开，直到距离不再明显变小（这说明他们前进的方向已经几乎垂直于他们和目标之间连线），就转到垂直方向的街道再继续搜寻。最终，在被抢不到24小时，史教授成功把车追回。

连现场的警察都感叹：“They shouldn’t have messed up with computer science professors!（他们不该惹上计算机教授！）” （详情可见新智元文章《清华毕业计算机教授遭持枪劫车！靠“贪心算法”追回秒杀美国警察》。）

史教授基于能测距离这一要素，不断极小化当前点到目标点的距离，从计算机角度称为是贪心算法。

从最优化算法的角度来看，优化的问题是，这是一个凸二次函数，沿着一个方向开，直到与目标距离达到最小（实际路况中由于不能调头，这一点通过直到距离不再明显变小来验证），这是最优化中最经典的精确线搜索方法(exact line search), 该方法有一个重要特性，在这个方向上的最优点处，梯度方向和该方向正交（垂直）。

因此，史教授选择在前一方向上最优点处换沿垂直方向搜索，由于问题是2维平面上的优化问题，此时的方向恰恰就是负梯度方向，下一步做的就是最速下降法。该优化问题是一个海色矩阵为单位阵的凸二次优化问题，所以，最速下降法迭代一步就可以终止到唯一的全局最优解。

如图所示。读者也可以通过很简单的平面几何来验证这一性质。由于实际路况的复杂性，比如路线可能不全程是直线，方向上的最优点处不能立刻拐弯，所以是一个非精确线搜索的下降算法，由于迭代中的距离严格单调递减，在道路连通等适当条件下能期待收敛到0，即找到最优解。

史教授这样做法存有一定的风险，因为需要靠近有枪的劫匪。我们事后诸葛亮地问问，在不靠近车辆的前提下，史教授还有其他选择吗？（也就是说，仅由相对距离，是否能够定位？）

如上图所示，我们选择远离目标的不共线的三点A，B，C，记其GPS坐标分别为, 从这三点测一下到目标的距离,记为. 设目标点的GPS坐标为(x,y)，那么我们有如下三个方程：

将(1)分别代入(2)和(3)，化简得一个二元线性方程组

由于ABC三点不共线，所以上述线性方程组系数矩阵非奇异，从而方程组有唯一解，其解确定未知目标点。使用该方法提供警方被抢车辆坐标，可以避免与劫匪近距离接触，真正做到了运筹帷幄之中，决胜千里之外。

实际中，由于距离的测量存在误差，这直接影响到未知解的精度。为了尽可能控制误差的影响，通常多选一些已知的观测点，设它们的坐标为，测出距离为。这样我们建模得到如下非线性最小二乘问题：

该问题关于x,y是非凸的，但是问题可以等价转化为：

这是一个单个二次约束的二次优化问题，也是广义的信赖域子问题，具有隐凸性质和强对偶性质[1]，其全局最优解是能够在多项式时间内快速解得，感兴趣的读者可以参考《等式S-引理的理论与应用》。此外，针对定位问题还有其它一些非凸优化模型，如

该问题实际上称为GPS定位问题[2]，GPS系统使用至少4颗卫星的位置以及它们到地球上人的距离可以计算出人的坐标，其计算原理同上。实际上，我们这里提到的两个优化模型正是来自GPS定位问题[2]。

该问题的进一步推广是距离几何问题：给定若干个点，其中某一些点的位置已知，这些点也称为锚点，另外已知一部分点与点间的距离，要求确定所有点的位置坐标。该问题在传感性定位[3]以及蛋白质结构解析[4]中有重要的应用。

参考文献：

[1] Y. Xia, S. Wang, R.L. Sheu, S-Lemma with equality and its applications. Math. Program. 156(1), 513–547, 2016

[2] A. Beck, D. Pan, On The Solution of the Gps Localization and Circle Fitting Problems, SIAM J. OPTIM. 22(1), 108–134, 2012

[3]P. Biswas,  T. Lian,  T. Wang, Y. Ye, Semidefinite programming based algorithms for sensor network localization. ACM Transactions in Sensor Networks. 2, 188–220, 2006

[4]J.J. More, Z. Wu,  Distance Geometry Optimization for Protein Structures. Journal of Global Optimization. 15: 219–223, 1999