algorithm - 将两条线拟合到一组 2D 点

Question

给定一组 2D 点（图中的黑点），我需要选择两条线以某种方式表示这些点。我可能需要最小化 [到两条线的距离]^2 的平方和x，尽管如果有任何其他指标使这更容易，这也很好。

显而易见但无效的方法是在所有 2^n 分区上尝试最小平方。一种实用的方法可能是迭代改进，可能从随机分区开始。

有没有研究处理这个问题的算法？

标签： algorithmoptimizationcurve-fittingcomputational-geometry

Answer 1

我认为这可以表述为一个明确的优化问题：

 min sum(j, r1(j)^2 + r2(j)^2)                 (quadratic)
 subject to
     r1(j) = (y(j) - a0 - a1*x(j)) * δ(j)      (quadratic)
     r2(j) = (y(j) - b0 - b1*x(j)) * (1-δ(j))  (quadratic) 
     δ(j) ∈ {0,1}

我们同时将点分配给一条线和回归（最小化残差平方和）。

这是一个非凸二次约束混合整数二次规划问题。可以处理此问题的求解器包括 Gurobi、Baron、Couenne、Antigone。

我们可以重新表述一下：

 min sum(j, r(j)^2)                      (convex quadratic)
 subject to
     r(j) = y(j) - a0 - a1*x(j) + s1(j)  (one of these will be relaxed)
     r(j) = y(j) - b0 - b1*x(j) + s2(j)  (all linear)
     -U*δ(j) <= s1(j) <= U*δ(j)
     -U*(1-δ(j)) <= s2(j) <= U*(1-δ(j))
     δ(j) ∈ {0,1}
     s1(j),s2(j) ∈ [-U,U]
     U = 1000                            (reasonable bound, constant)

这使其成为直凸 MIQP模型。这将允许使用更多的求解器（例如 Cplex）并且更容易求解。其他一些配方在这里。提到的一些模型不需要我在上面的 big-M 公式中必须使用的边界。值得注意的是，这些模型提供了经过验证的最佳解决方案（对于非凸模型，这需要一个全局求解器；凸模型更容易，不需要这个）。此外，我们还可以形成 L1 目标，而不是最小二乘目标。在后一种情况下，我们最终得到一个线性 MIP 模型。

一个小测试证实了这一点：

这个问题有 50 分，在慢速笔记本电脑上使用 Cplex 的 MIQP 求解器需要 1.25 秒。这可能是一个统计问题的案例，其中 MIP/MIQP 方法可以提供一些东西。