将两条线拟合到一组2D点
给定一组 2D 点（图片中的黑点），我需要选择两条线来以某种方式表示这些点。我可能需要最小化 [距离x到两条线中较近者的距离]^2的平方和，尽管如果有任何其他指标可以使这更容易，这也很好。
明显但无效的方法是在所有 2^n 个分区上尝试最小平方。一种实用的方法可能是迭代改进，可能从随机分区开始。
有没有关于处理这个问题的算法的研究？
回答
我认为这可以表述为一个显式优化问题：
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 方法可以提供一些东西。