这是一道作业题。我被要求找到一组给定的 n 点 (2D) 的最佳拟合线的系数。系数是 a b c in: 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(第二个表达式是为了占绝对符号)。
我认为这足以定义问题。当我将条件放入求解器时，它返回 a b c 都等于 0，但实际上它不应该。我想我在这里缺少一些条件。有人可以指出给我吗？
最佳答案
您应该添加一个额外的语句:a 或 b 不应为 0。如果两个值都为 0，则您的系统有一个有效的解决方案，但不存在 a 和 b 都等于 0 的行。
编辑:改进 Rerito 的建议。任何行的 a 或 b 都不等于 0。还有行 (k*a)*x + (k*b)* y + (k*c) 和 (a) *x + (b)* y + (c) 对于任何非零 k 都是相同的。所以我会说你需要运行求解器两次 - 一次指定 a 为 1，一次指定 b 为 1，之后选择更好的解决方案。您必须运行求解器两次，因为最好的解决方案可能是 a=0 或 b=0(但不是两者)。
关于algorithm - 使用线性规划查找 "line of best fit"，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15896850/