math - 评估凸组合的权重

Question

我正在使用 scipy.spatial.ConvexHull API 来评估一组点的凸包，并且效果很好。鉴于以下代码：

p1 = points[11]
hull = ConvexHull(points)
vertices = [points[i] for i in hull.vertices] 

如何评估vertices等于的凸组合的系数（权重） p1？

非常感谢你，摩西

Answer 1

注意：如果顶点的数量大于d+1，其中d是维度，那么组合将不是唯一的。在答案的其余部分，我假设d=2为简单起见。

输入：

• 顶点v0 = (x0, y0), v1 = (x1, y1), ..., vn = (xn, yn)；
• 一个点p1 = (x,y)；

输出：

• 一个组合a0, a1, ..., an；

这样：

• x = a0 * x0 + a1 * x1 + ... + an * xn;
• y = a0 * y0 + a1 * y1 + ... + an * yn;
• 1 = a0 + a1 + ... + an;
• 我, ai >= 0.

这是一个未知数中的三个线性方程组(a0, a1, ..., an)，以及 n+1 个线性方程组。我们可以使用scipy 的线性规划模块 scipy.optimize.linprog来解决这个系统

示例解决方案：

import random                      # generate points
import scipy.spatial as scispa     # ConvexHull
import scipy.optimize as sciopt    # linprog
from scipy.sparse import identity  # identity matrix

points = [(random.randrange(0,100), random.randrange(0,100)) for _ in range(20)]
p1 = points[11]
hull = scispa.ConvexHull(points)
vertices = [points[i] for i in hull.vertices]

c = [1 for _ in vertices]
A = [[x for x,y in vertices], [y for x,y in vertices], [1 for _ in vertices]]
b = [p1[0], p1[1], 1]
s = sciopt.linprog(c, A_eq = A, b_eq = b)

>>> s.x
array([0.13393774, 0.06470577, 0.07367599, 0.09523271, 0.18924727,
       0.26909487, 0.17410566])
>>> p1
(36, 57)
>>> [sum(a*xi for a,(xi,_) in zip(s.x, vertices)), sum(a*yi for a,(_,yi) in zip(s.x, vertices))]
[36.00000000719907, 57.00000000671608]

重要提示：我通过警告开始这个答案，如果平面中有超过 3 个顶点，或者维度 d 中的顶点超过 d+1 个，那么我们的方程组将有超过 1 个解。上面的代码只返回一个解决方案，这意味着做出了任意选择。您可以控制这种任意选择：scipy.optimize.linprog是一种优化工具；这里是最小化c我们作为参数给出的向量和解向量的点积s.x。这里我将所有的系数都设置c为1，意思是linprog会找到一个解，使解中的系数总和最小；尝试提供不同的向量c，你会得到不同的解决方案。