algorithm - 使用线性规划寻找“最佳拟合线”

Question

这是一个家庭作业问题。我被要求找到给定一组 n 点（2D）的最佳拟合线的系数。系数为 abc 在：ax+by=c。假设有 n 个点，使用线性规划找到导致最小“最大绝对误差”的系数，定义为：max(|a*xi+b*yi -c|)，i 的范围为 1-n。

这是我的思考过程：

令 M 表示最大绝对误差。线性规划的目标是最小化 M。由于 M 是所有 |a*xi+b*yi-c| 中最大的，因此它必须大于它们中的每一个。所以 (a*xi+b*yi-c)<= M，并且 (a*xi+b*yi-c)>= -M，对于所有 i（第二个表达式是考虑绝对符号）。

我认为这足以定义问题。当我将条件放入求解器时，它返回的 abc 都等于 0，但实际上它不应该。我想我在这里缺少一些条件。有人可以向我指出吗？

Answer 1

您应该添加一个额外的语句，即：a 或 b 都不应该为 0。如果两个值都为 0，则您的系统有一个有效的解决方案，但没有一条线 a 和 b 都等于 0。

编辑：改进 Rerito 的建议。任何行的 a 或 b 都不等于 0。对于任何非零 k，这些行(k*a)*x + (k*b)* y + (k*c)和都是相同的。(a)*x + (b)* y + (c)所以我会说你需要运行求解器两次——一次在指定 a 为 1 时，一次在指定 b 为 1 时，然后选择更好的解决方案。您必须运行求解器两次，因为最好的解决方案可能具有a=0或b=0（但不是两者）。