如何将凸曲线拟合到数据点集？

Question

我有一组数据点(x1，y1) (x2，y2) (x3，y3)等。数据的特点是，大多数情况下连续点之间的斜率都在增加。但也有一些例外。我将数据加载到的软件期望曲线是凸的，换句话说，斜率应该始终上升。因此，我需要一个结果集，其中的数据点(x1，y1)，(x2，y2)等将删除“异常”数据点，并用适当的数据点替换它们，以使斜率始终增加。

我原本打算编写一个程序（使用C#）来完成这个任务，但我想在这里发布一下，看看是否有标准问题和已经存在的解决方案。

- Satfactor

---

哦，点的数量总是超过3个吗？（4个或更多？）如果斜率相等（线性），会怎样？编辑：如果有超过3个点，是否需要检查所有连续的点？ - Chris Sinclair

大约有32个数据点。是的，所有点都需要检查。相等的斜率也是例外。因此，在我之前的评论中，P4 也可能需要被移除，并且 P3 和 P4 都可能需要被替换。这些例外很少见。即在这32个数据点中可能只有2或3个。 - Satfactor

“fit”是什么意思？你所谓的凸性，即斜率始终增加是不正确的。椭圆是凸的，但其梯度会发生变化。为了得到你上面描述的内容，你可以使用带有正二次系数的二次最小二乘逼近来拟合。这个函数具有不断增加的梯度和凸性。请参阅此链接以获取凸函数定义http://en.wikipedia.org/wiki/Convex_function。 - mathematician1975

mathematician1975，感谢您提出凸函数的定义。如果我进行最小二乘逼近（我已经尝试过使用样本集合），它会影响到所有的数据点。考虑到我的数据集中只有1或2个例外情况，我不想改变其他数值。我认为我可能只需要对"异常点"进行一些纠正。 - Satfactor

不，它们实际上是用于交易成本建模的交易数据。 (X,Y) = 股票数量/成本。但我输入数据的优化器有一定的限制。 - Satfactor

Answer 1

解决问题取决于目标。您可以限制自己只更改点的Y坐标，同时保持X不变。然后，一个合理的目标可能是最小化每个点的新Y值Y'和旧值Y之间绝对差异ABS(Y'-Y)的总和。（我不知道这是否适用于您的问题，但对我来说听起来并不太不合理。）

然后，该问题可以建模为线性规划问题，请参见：

http://en.wikipedia.org/wiki/Linear_programming

在这种情况下，有标准库可以找到最优解。

- willem