Circumventing the Slater conundrum in countably infinite linear programs
Circumventing the Slater conundrum in countably infinite linear programs
复制标题
在可数无限线性程序中规避斯莱特难题
DOI：
10.1016/j.ejor.2015.04.026
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Ghate
中科院分区：
文献类型：
--
作者：
A. Ghate
可数无限线性规划的对偶性结果很少。允许一个内点的子空间，这是零对偶间隙的充分条件，产生一个对偶，其中的约束不能用原始约束矩阵的普通转置来表示。允许具有这种转置的对偶的子空间不允许内部点。这个难题困扰了研究人员几十年，最近被称为斯莱特难题。我们找到了一个绕过这个障碍的方法，我们提出了一对具有三个性质的原始-对偶空间：原始和对偶目标函数中的级数收敛;原始约束矩阵的行和列定义的级数收敛;原始约束矩阵定义的双序列的特定迭代级数中的和的顺序可以互换，使得对偶由普通转置定义。弱对偶性和互补松弛性则是直接的。而不是使用内点条件，以建立一个零对偶差距，我们呼吁规划地平线的方法。当一系列的原始和对偶约束是连续的，我们证明了强对偶持有的原始和对偶CILP的有限维截断的最优解序列有一个聚点。我们通过反例表明，这样的聚点存在的要求不能放松。我们的结果说明使用几个例子，并适用于可数状态马尔可夫决策过程和鲁棒优化的问题。
Duality results on countably infinite linear programs are scarce. Subspaces that admit an interior point, which is a sufficient condition for a zero duality gap, yield a dual where the constraints cannot be expressed using the ordinary transpose of the primal constraint matrix. Subspaces that permit a dual with this transpose do not admit an interior point. This difficulty has stumped researchers for a few decades; it has recently been called the Slater conundrum. We find a way around this hurdle.We propose a pair of primal-dual spaces with three properties: the series in the primal and dual objective functions converge; the series defined by the rows and columns of the primal constraint matrix converge; and the order of sums in a particular iterated series of a double sequence defined by the primal constraint matrix can be interchanged so that the dual is defined by the ordinary transpose. Weak duality and complementary slackness are then immediate. Instead of using interior point conditions to establish a zero duality gap, we call upon the planning horizon method. When the series in the primal and dual constraints are continuous, we prove that strong duality holds if a sequence of optimal solutions to finite-dimensional truncations of the primal and dual CILPs has an accumulation point. We show by counterexample that the requirement that such an accumulation point exist cannot be relaxed. Our results are illustrated using several examples, and are applied to countable-state Markov decision processes and to a problem in robust optimization.