rss|MIT博士生杨珩：从L1到L5，自动驾驶的“拦路虎”可能是一个数学问题( 三 ) 系统|扬声器|彭博社|汽车|苹果

Wahba 问题，又称为“旋转搜索”，旨在找到最佳旋转以在给定的对应关系下对齐两组向量观察，是许多计算机视觉和机器人应用中的基本研究（比如可以用作卫星的定位）。在 ICCV 2019 中，杨珩针对大量向量观测值为异常值（outliers）的情况，提出了第一个多项式时间可证明的最优方法来解决 Wahba 问题。
在这篇工作中，除了使用 TLS 成本来制定 Wahba 问题，他们还开发了凸半定规划（SDP）松弛来解决非凸问题。他们提出可认证算法 QUASAR （基于 QUAternion 的半定松弛法，用于鲁棒对齐），即使在面临大量噪声与异常值的情况下（比如多余95%的异常值），他们的松弛也很“紧”，算出可证明的全局最优解（即松弛是精确的），优于鲁棒的局部优化算法 RANSAC。
“非凸”转“凸”，是杨珩提出的算法能够在大部分输入数据中求得全局最优解的关键点。凭借这一主导思想以及后续的一系列工作，杨珩获得 ICRA 2020 的机器视觉最佳论文奖，还入围了 RSS 2021 最佳论文奖最终名单。
如前所述，TLS是一个非凸优化问题，基本框架如下：

文章插图

非凸问题几乎是无法快速求得全局最优解的，但是，我们可以通过凸松弛方法，将非凸问题转为凸问题。这个过程就相当于以退为进：当你面对一道难题（如非凸问题）、不知所措时，你可以先把它转化成一个较为简单的问题（如凸问题），然后去求解这个简单的问题。解完简单的问题后，你会知道简单的问题 B 与原问题 A 是否等价。
更有意思的是，在解出简单问题 B 之前，你并不知道简单问题 B 是否与难问题 A 是否等价。但当你解完 B 后，你会检验该解是否满足原问题的某些条件、从而推测问题 B 与问题 A 是否等价。如果满足，那么凸问题被解，实际上也就意味着原来的非凸问题已经解决。
「有点“事后诸葛亮”的感觉。」杨珩形容。从理论上讲，一般性的凸问题也是NP-hard问题，目前在多项式时间内是不可求解的，但极个别凸问题，比如SDP的优点是：可以在多项式时间内求出全局最优解。在这个凸问题中，所有局部最优都是全局最优。
在“非凸”转“凸”的过程中，杨珩的灵感也源自一个非常著名的数学“松弛”理论：2001年，法国数学家 Jean B. Lasserre 在数学顶刊《SIAM Journal on Optimization》上发表了一篇著名的文章，叫“Global optimization with polynomials and the problem of moments”（引用量已超过2600），里面提到：
非凸问题永远不可能等价于凸问题，但如果满足一定条件，我们就可以用一个足够大的凸问题来逼近/解决一个非凸问题。不过，我们并不明确该非凸问题有多大，它可能是无限大。
这是一个十分优美的理论。假设非凸问题是迷雾中的一座小岛，那么凸问题就是一片不断在寻找岛屿边界的汪洋，摸索，定义，直至几乎全部包围，不断接近真实的全貌。
但也不难推测，在这个“松弛”的过程中，研究会面临两个难点：
1）如何用一个足够小的凸问题来解决非凸问题？比方说，原来的非凸问题可能只有100个参数要求解，但你要解的凸问题可能有100万个参数。也就是说，你需要解一个非常大的凸问题，才能解原来的非凸问题。
2）杨珩观察到，虽然只要解决一个包含100万参数的凸问题、就能解原来只有100个参数的凸问题，但目前在数学上，没有一个求解器可以解决这么大的凸问题。在杨珩的研究中，他所用于求解非凸问题的凸问题是“半正定规划”问题（Semidefinite Programming, SDP），属于凸问题里最难的一类。
从理论上讲，要解决原来的非凸问题 TLS，转换的凸问题可能要无限大，不止100万个参数，也可能是1000万、1亿、10亿甚至上百亿。针对第一个难点，杨珩及团队用真实计算显示：转化的凸问题（即SDP问题）不需要无限大，只需要一个最小的凸问题（参数量为100万)，即可解决原来的非凸问题。