linear-programming - 凸包极值点检测的线性规划

Question

我们如何制定一个线性规划来告诉我们任意点 x[ j ] ∈ X，其中 X = {x1, ... ,xn} ⊂ Rn 是否是 X 的凸包的极值点，即 conv( X）？

根据这个线性规划的解，我们应该能够断言“是的，x[ j ] 是一个极值点”，或者“不是”。

好吧，我的想法是这样的：

{min: 0} s.t. x[ j ] = Σi ( a[ i ] * x[ i ] ); i ∈ {1, ... ,k}, ∀ j ∈ {1, ... ,k}

如果存在这样的 a[ i ] ，则意味着 x[ j ] 是其他 x 的线性组合，这似乎违反了极值点的定义。

但是，我相信这张 LP 并没有涵盖整个背景。即，如果我们选择一个位于 conv(X) 内部（不在边缘上）并且不是其他人的线性组合的 x[ j ] 怎么办。然后该模型将导致错误的结果。在我看来，如果 选定的 x [ j ] 位于 conv(X) 的边缘，则上述模型会很好。

谢谢。

Answer 1

你很接近。一个点属于一组有限点的凸包当且仅当它可以写成这些点的凸组合。此外，只有当没有其他两个点可以写成它们的凸组合时，一个点才是极值点。

令兴趣点为 x_k。然后，以下线性程序将完成这项工作：

其中 x_{ik} 是i您要检查的点（点 k）的第 - 个坐标。请注意，该点应该是我们包含在等式右侧的点之一（即，该问题总是有至少一个解决方案是 lambda_k = 1，而所有其他 lambdas 将等于 0。

如果该点是一个极值点，那么您将得到的唯一解决方案是 lambda_k=1，其他 lambdas = 0。否则，将弹出一个不同的解决方案（具有更小的 lambda_k）。

（请注意，在您的问题描述中，点数和维度都是n），因此相应的索引（j 和 i）从1到n。

我希望这有帮助！