A 精细线:适合QCQP优化的最小平面线总数 (A Fine Line: Total Least-Squares Line Fitting as QCQP Optimization)

This note uses the Total Least-Squares (TLS) line-fitting problem as a canvas to explore some modern optimization tools. The contribution is meant to be tutorial in nature. The TLS problem has a lot of mathematical similarities to important problems in robotics and computer vision but is easier to visualize and understand. We demonstrate how to turn this problem into a Quadratically Constrained Quadratic Program (QCQP) so that it can be cast either as an eigenproblem or a Semi-Definite Program (SDP). We then turn to the more challenging situation where a Geman-McClure cost function and M-estimation are used to reject outlier datapoints. Using Black-Rangarajan duality, we show this can also be cast as a QCQP and solved as an SDP; however, with a lot of data the SDP can be slow and as such we show how we can construct a certificate of optimality for a faster method such as Iteratively Reweighted Least-Squares (IRLS).

翻译：本注释使用“总计最小方”的线性问题作为画布来探索一些现代优化工具。贡献在于指导性。 TLS问题与机器人和计算机视觉中的重要问题有许多数学相似之处, 但比较容易想象和理解。我们演示如何将这个问题转换成一个四重组合的二次曲线程序( QCQP ), 以便它可以作为一个二次问题或半确定性程序( SDP ) 。我们然后转向一个更具挑战性的情况, 即使用 Geman- Mclure 成本函数和 M 估计值来拒绝外部数据点。我们用黑- Rangarajan 的双重性来显示, 也可以将它作为一个 QQP 并作为一个 SDP 解答; 但是, 有了大量的数据, SDP 可以缓慢, 这样我们就可以为更快的方法建立最佳性证书, 如诸如自动重标定的最小方程式( IRLS ) 。