关于积极跨越集的说明外文翻译资料

英语原文共 3 页，剩余内容已隐藏，支付完成后下载完整资料

关于积极跨越集的说明

史蒂芬·威廉

1.引言.考虑确定性问题

（0）

其中是中的一些有限集合。这个问题在各种算法的实现中发挥作用。我们通过解决单个线性问题来解释如何回答这个问题。

公式（0）可以更简洁地表达为

（1）

其中A表示列向量为的矩阵. 我们从最基础的层面来解释向量不等式.由于意味着对每一个j都有. 我们确定(1)式的有效性的程序如下。

（1）式确定或拒绝的方法。

0. 选择一个带有正向的向量，并定义

1.如果,则（1）保留，否则，进行第二步。

2.解决如下线性问题

最小化t超过所有的

使得

，,. (2)

如果最优值为零，则(1)式成立.否则最优值为1，式(1)为失败.

在下一节中，我们展示了为什么这个程序可行. 我们也注意到当时，增强集合满足

(3)

我们可以自由使用第一个线性规划课程涵盖的标准结果; 这个材料的优秀参考文献是Chcatal [1]的介绍性文本和Schrijver [2]的更高级的文本.

虽然这里提出的想法并不新鲜，但是这个问题的重要性使得这个解决方案更为人所知. 在教科书或课程中很少提到这个问题，笔者遇到了用不必要的复杂手段来处理这个任务的从业者.

2. 验证程序. 我们从观察开始，(1)式可以以许多等效的方式重新设计。在本节中，和如第1节的方法的步骤0中所定义.

引文1.以下是等价的：

(a)对于所有的，有一个解;

(b)对于所有的，有一个解;

(c)对于所有的，有一个解;

(d)对于所有的，有一个解;

(e)对于所有的，有一个解;

(f)对于所有的，有一个解;

(g)对于一些的，有一个解;

(h)有一个解.

证明：很明显，这些公式都是各自的推论。我们看到(h)式暗示(a)式。对一些,并考虑,假设。然后对于所有的t，我们有.鉴于，t足够大。

读者应该观察到，引文1中的（a）是（1）的简单重述。另外，（a）和（b）的等价性表明放松（1）右侧的正向限制不影响问题。

引理1证明了在第1节的方法中得出的几个结论。

推论2 如果,那么（1）式成立。如果，那么（3）式成立；在这种情况下，如果（2）中的最优值为零，则（1）成立。

证明:这些都来自于引理1中的(h)式. 通过取，当时，方程式（1）成立。当并且（2）中的最优值为零时，使用线性程序（2）的最优解x。（3）中的第二个等式在时成立，因为

在矩阵的引理1中表示(h)式。

最后，请注意，（3）中的第一个等式总是成立，因为通过包含该跨度的成员，线性跨度不变。

（1）在引理1中的表征也导致我们的主要结果

定理3 线性程序（2）具有最优解。 此外，以下是等价的：

(a)(2)中的最优值小于1;

(b) (2)中的最优值为0;

(c)方程(1)成立。

证明： 观察到满足（2）中的约束条件，并且目标值被下限为零. 根据线性规划理论，保证了对（2）的最优解的存在; 如果（a）成立，则存在,使得

定义收益率

，

这意味着（b）;相反的，结论是显而易见的。另一方面，（b）对应于引理1的陈述（f）。

定理3证明了在第1节的方法中提出的剩余索赔; （2）中的非零最优值必须实际上是一致的，在这种情况下（1）不成立。这也可以通过线性规划二元性来证明。随着获得线性程序（2）的解决方案，大多数方法构建了双线性程序的最优解。

最大化超过所有的

受制于

,. (4)

此外，二元理论保证（2）和（4）中的最优值是一致的。当这个共同值是非零时，（4）的任何最优解都提供了证据证明（1）不成立。

推论4 假设（2）和（4）中的最优值是非零，并且对于（4）是最优的。 那么y将与的正跨度强烈地分开，在的意义上，

证明：定理3确保实际的最优值,所以

另一方面，如果,其中,那么

,因为,,力

总而言之，（1）的有效性可以通过求解单线性程序来确定。当（1）成立时，该程序的解决方案证明了这一点;否则，双重程序的解决方案证明（1）失败。此外，我们已经表明，对于任何给定的向量，也积极地跨越其线性跨度，或者存在一些非零向量，使得正跨度.

参考：

1. Vasek Chvatal，Linear Programming，Freeman，New York，1983

2.Alexander Schrijver ,Theory of Linear and Integer Programming, John Wiley and Sons, Chicester,1986

迈阿密大学数学与统计系，牛津，OH 45056

wrightse@muohio.edu

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[26503]，资料为PDF文档或Word文档，PDF文档可免费转换为Word