时间戳

首页 > 解决方案 > 如何在 Python 中快速得到一个线性程序的可行解？

python - 如何在 Python 中快速得到一个线性程序的可行解？

问题描述

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

我scipy.spatial.HalfspaceIntersection用来做这个。下图显示了生成的交叉点：rviz 截图

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

你看，当前的Python实现scipy.spatial.HalfspaceIntersection需要一个interior_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作为参数传递？据我所知，半空间的交集是消除给定一组不等式的冗余不等式。为什么这需要一个可行点？

标签： pythonnumpyscipycomputational-geometrylinear-programming

解决方案

您可以指定一个恒定的成本函数，例如 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。因此，由于您的要求是该点“明显位于半空间定义的区域内”，因此我建议使用以下任一方法：

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

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

推荐阅读