如何在scipy的linprog中配置凸包成员问题的约束条件

问题转化与约束构建 #

你的问题本质是凸包成员判定：判断点p是否能表示为给定n个点的正系数凸组合（系数和≤1且每个系数>0）。我们可以将其转化为线性规划可行性问题，用scipy.optimize.linprog求解，约束转化如下：

1. 目标函数

由于仅需判断可行性，无需优化特定目标，设目标函数为全0向量：c = np.zeros(n)，让linprog专注寻找满足约束的解。

2. 约束条件拆解

• 等式约束（点积相等）：
  对每个维度m，需满足 $\sum_{k=1}^n a_k \cdot x_{k,m} = p_m$。将点云整理为矩阵X（形状为(n, m)，每行是一个m维点），则等式约束的矩阵形式为：
  A_eq = X.T（转置后形状为(m, n)，每一行对应一个维度的等式），b_eq = p（目标点的m维向量）。

• 不等式约束1（系数和≤1）：
  约束 $\sum_{k=1}^n a_k ≤ 1$，对应：
  A_ub = np.array([[1]*n])（1行n列的全1矩阵），b_ub = np.array([1])。

• 不等式约束2（系数>0）：
  数值优化中无法严格处理a_k > 0，通常用极小正数近似，设每个系数的下界为1e-9（可根据精度调整），上界无限制：
  bounds = [(1e-9, None) for _ in range(n)]

代码实现示例 #

import numpy as np
from scipy.optimize import linprog

# 示例数据：3个2维点，目标点p
X = np.array([[0, 0], [1, 0], [0, 1]])  # n=3, m=2
p = np.array([0.2, 0.3])

n = X.shape[0]
m = X.shape[1]

# 构建linprog参数
c = np.zeros(n)
A_ub = np.array([[1]*n])
b_ub = np.array([1])
A_eq = X.T
b_eq = p
bounds = [(1e-9, None) for _ in range(n)]

# 求解线性规划
result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')

# 判断可行性
if result.status == 0:
    print("可行：点p属于给定点云的凸包内部/边界（满足正系数凸组合条件）")
    print("找到的系数：", result.x)
else:
    print("不可行：点p不在给定点云的凸包内，或无法用正系数凸组合表示")

额外专业建议 #

用linprog是通用线性规划解法，但凸包成员判定有更高效的专用实现：scipy.spatial.ConvexHull的contains_points方法，底层调用Qhull库，速度更快且更贴合问题场景。示例：

from scipy.spatial import ConvexHull

hull = ConvexHull(X)
is_inside = hull.contains_points([p])[0]
# 注意：contains_points判断的是点是否在凸包内部/边界（系数和=1且系数≥0），若需要严格正系数，需额外验证边界情况

如果要求严格正系数（a_k > 0），需排除点p恰好是凸包顶点或在凸包边/面上的情况（此时会有系数为0），可结合上述两种方法：先用contains_points判断是否在凸包内，再用linprog验证是否存在全正系数的解。

内容的提问来源于stack exchange，提问作者Michael Bay