计算科学 - 隐含等式和相对内部 - 吾爱随笔录

计算科学线性规划

2021-12-01 23:29:10

对于具有中等维度的密集的不等式线性系统找到由可行点（即隐含等式）和相对内部可行点跨越的仿射子空间的最佳方法是什么在这个子空间？ $Ax\ge b$ $A$ $(Ax)i=b_i$

它不应该需要许多线性程序的解决方案。我从很久以前模糊地记得，对单个适当 LP 的解决方案进行适当的后处理就足够了，但不记得细节了。

2个回答

可能不是最有效的方法，但你可以这样做：

$Ax - s = b$

$s \geq 0$

然后最大化关于的不等式。的最大值为 0，则该不等式是隐含的等式之一。您需要删除出现的任何冗余方程。 $s_{i}$ $i=1, 2, \ldots, m$ $s_{i}$

找到方程组后，使用 LP 找到满足原始不等式的特定点，然后根据该特定解和隐含等式约束矩阵的零空间的基础来表达仿射壳。您现在可以根据与此基础相关的系数重写原始不等式系统并减少维度。
根据这个新基，通过求解另一个LP，在隐含仿射集中找到可行集的切比雪夫中心。

PS 在网上做了一点研究，发现了一个解决这个问题的方法，只需要一个 LP 的解决方案。但是，该解决方案必须是严格互补的（您无法从单纯形法中获得，但可以使用原始对偶内点法获得。）请参阅 Harvey Greenberg 1996 年的这篇论文中的定理 8 以及他引用的早期资料：

你可能想看看一本关于线性规划的书。为线性规划的顶点算法找到一个起点正是您在这里提出的问题。使用的算法通常称为线性规划中的“阶段 1”。

其它你可能感兴趣的问题