在线性可行空间内找到一个点的最快方法是什么？（由几个超平面和半空间的交集定义）。我希望能够在原始凸空间中选择一个初始点，使用一个依赖于在我有的点上，然后我需要在原始空间中选择另一个点，而不是在已经探索过的邻域中。我需要继续这样做，直到空间用尽（最终应该用尽）。基本上，我有一个凸空间，我需要循环直到同时执行以下操作：选择，查找围绕，然后 任何帮助表示赞赏。
探索线性定义空间中的可行点
计算科学
线性代数
线性规划
2021-12-14 20:13:27
2个回答
寻找单个可行点传统上由单纯形算法的阶段 1 完成。
http://en.wikipedia.org/wiki/Simplex_algorithm#Finding_an_initial_canonical_tableau
这意味着您可以通过调用任何线性规划例程来完成，只需将目标函数设置为零即可。
的球覆盖可行域要困难得多，因为排除球构成了非凸域。有一些算法可以枚举由方程和不等式给出的有界多面体的所有顶点（尽管它们的数量通常随着维度呈指数增长）。在拥有所有顶点之后，可行集仅由它们的凸组合组成，因此可以用于内部采样。但除非多面体是单纯形，否则不同的凸组合可能会给出相同的点，因此在生成最小覆盖时需要添加拒绝设施。
有一个软件叫PORTA，可以枚举出一组线性不等式和等式中所有可行的点。
http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA/
好好享受！