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

Question

目标：计算两个凸多胞形的交集。

我正在使用scipy.spatial.HalfspaceIntersection to do this. The following image shows the resultant intersection:

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

你看，scipy.spatial.HalfspaceIntersection 的当前 Python 实现需要将 interior_point 作为参数传递。

interior_point : ndarray of floats, shape (ndim,)
Point clearly inside the region defined by halfspaces. Also called a feasible point, it can be obtained by linear programming.

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

SciPy's optimization module scipy.optimize.linprog implements two general Linear Programming (LP) solvers: simplex, and interior-point. However, they seem to require a cost function. [1]

因为我想花费尽可能少的处理时间来计算这个可行点，所以我想知道我如何运行这些 LP 方法中的任何一个没有成本函数，即只有运行直到解决方案达到可行状态。

问题：

scipy.optimize.linprog是计算这个可行内点的正确方法吗？
如果是，我如何使用 simplex 或 interior-point without成本函数？
为什么 scipy.spatial.HalfspaceIntersection 要求首先将 interior point 作为参数传递？据我所知，半空间的交集是删除一组给定不等式的冗余不等式。为什么需要可行点？

Answer 1

您可以指定一个常数成本函数，例如 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)

输出：

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 背后的实现。因此，由于您的要求是点是"clearly inside the region defined by halfspaces"，我建议以下之一：

或者， 将 method='interior-point' 传递给 linprog。
或者，计算不同的顶点并利用多面体是凸的：
1. 向常量 objective 函数添加一些噪声（例如，通过 np.random.randn）
2. 通过改变噪声种子 (np.random.seed) 解决噪声增强 LP 的多个实例。
3. 最后，使用解的均值作为最终的内点"clearly inside the region".

由于不清楚，您的内点边缘需要多大，我希望第二种方法（噪声增强 LP）更稳健。

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

How to quickly get a feasible solution to a linear program in Python?

python

numpy

scipy

computational-geometry

linear-programming