如何在Python中快速得到线性规划的可行解？

Goal:计算两个凸多胞形的交集。

I am using scipy.spatial.HalfspaceIntersection https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html to do this. The following image shows the resultant intersection:

我的问题：确定初始可行点。

你看，现在的Python实施scipy.spatial.HalfspaceIntersection https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html#scipy.spatial.HalfspaceIntersection需要一个interior_point作为参数传递。

interior_point : ndarray of floats, shape (ndim,)
清楚地指向由半空间定义的区域内。也称为可行点，可以通过线性规划获得。

现在，我正在手动提供可行点，因为我只是起草一个原型来进行实验HalfspaceIntersection。 但现在我已经到了不想手动指定它的地步。

SciPy https://www.scipy.org/的优化模块scipy.optimize.linprog https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html实现两个通用的线性规划（LP）求解器：simplex, and 内点。然而，它们似乎需要成本函数。 [1 https://docs.scipy.org/doc/scipy/reference/optimize.html#linear-programming]

由于我想花费尽可能少的处理时间来计算这个可行点，所以我想知道如何运行这些 LP 方法without成本函数，即仅运行直到解决方案达到feasible status.

问题：

1. Is scipy.optimize.linprog计算这个可行内点的正确方法是什么？

2. 如果是，我该如何使用simplex or 内点 without成本函数？

3. 为什么scipy.spatial.HalfspaceIntersection require an interior point首先作为参数传递？据我所知，半空间的交集是消除给定的一组不等式的冗余不等式。为什么需要一个可行点？

您可以指定一个常数成本函数，例如 0。

这是一个例子：

%pylab
from scipy.optimize import linprog
A = array([[1] + 9 * [0], 9 * [0] + [1]])
b = array([1, 1])

测量这种方法的性能表明它非常有效：

%time
res = linprog(c=zeros(A.shape[1]), A_eq=A, b_eq=b)

Output:

CPU times: user 5 µs, sys: 1 µs, total: 6 µs
Wall time: 11 µs

此外，根据res.nit，我们只经过 2 次迭代就完成了。

结果res.x是正确的：

array([ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.])

请注意，单纯形算法旨在查找由线性约束定义的多面体的顶点。据我了解，基于内部点的方法没有这样的偏好，尽管我不熟悉 scipy 背后的实现linprog。因此，既然你的要求是，重点是“显然位于半空间定义的区域内”，我建议采用以下任一方法：

• Either, pass method='interior-point' to linprog.
• Or, compute different vertices and exploit that the polyhedron is convex:
  1. 向恒定目标函数添加一些噪声（例如，通过np.random.randn)
  2. 通过改变噪声种子来求解噪声增强 LP 的多个实例 (np.random.seed).
  3. 最后，使用解的平均值作为最终的内点“显然在该区域内”.

由于尚不清楚内点的余量需要有多大，因此我希望第二种方法（噪声增强 LP）更加稳健。