如何在 Python 中快速获得线性程序的可行解决方案？

Question

目标：计算两个凸多面体的交集。

我正在使用scipy.spatial.HalfspaceIntersection它。下图显示了生成的交叉点：

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

您会看到，当前的Python实现scipy.spatial.HalfspaceIntersection需要将 aninterior_point作为参数传递。

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

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

SciPy的优化模块scipy.optimize.linprog实现了两个通用线性规划 (LP)求解器：simplex和internal-point。但是，它们似乎需要成本函数。[ 1 ]

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

问题：

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

2. 如果是，我如何在没有成本函数的情况下使用单纯形或内点 ？

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

Answer 1

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

\n\n

这是一个例子：

\n\n

%pylab\nfrom scipy.optimize import linprog\nA = array([[1] + 9 * [0], 9 * [0] + [1]])\nb = array([1, 1])\n

\n\n

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

\n\n

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

\n\n

输出：

\n\n

CPU times: user 5 \xc2\xb5s, sys: 1 \xc2\xb5s, total: 6 \xc2\xb5s\nWall time: 11 \xc2\xb5s\n

\n\n

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

\n\n

结果res.x是正确的：

\n\n

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

\n\n

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

\n\n

\n
• 或者，传递method=\'interior-point\'到linprog.
\n
• 或者，计算不同的顶点并利用多面体是凸的：\n\n
  \n
  1. 向恒定目标函数添加一些噪声（例如，通过np.random.randn）
  \n
  2. 通过改变噪声种子 ( ) 来求解噪声增强 LP 的多个实例np.random.seed。
  \n
  3. 最后，使用解的平均值作为最终的内部点“明显位于该区域内”。
  \n
\n

\n\n

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

\n