University of Washington
Linear programs with countably many equality constraints and non-negative variables often occur in deterministic as well as stochastic planning problems. Special cases include shortest path problems with infinite nodes and arcs, Markov decision problems with infinite states and actions, infinite Leontief systems and infinite network flow problems. Naive extensions of finite dimensional linear programming concepts fail to hold in the infinite case due to a multitude of mathematical pathologies in subspaces of $R^{\infty}$. In this talk, we discuss challenges involved in developing these extensions.
In the first part of the talk, we show that the concept of a basic sequence, which is a natural extension of linear independence, is sufficient to identify extreme points. On the other hand, it is not necessary in general. However, linear independence is necessary. We then show that when the infimum of the values of the positive variables in a feasible solution is strictly positive, the idea of a basic sequence is necessary to identify extreme points.
In the second part of the talk, we embed the primal problem and its dual into appropriate vector spaces and develop weak duality and complementary slackness results. We argue that establishing absence of a duality gap is not so straightforward. Interestingly, we prove that strong duality in finite dimensional truncations of the original primal-dual pair carries over to a no duality gap result in the limit.
Finally, we present the Shadow Simplex method to solve infinite linear programs. This iterative method is finitely implementable, converges to the optimal value in the limit, and jumps from one extreme point of the feasible region to another. This movement may not be along an extreme edge of the feasible region in general. However, we show that for the important special case of shortest path problems that are equivalent to infinite horizon deterministic dynamic programs, the Shadow Simplex method reduces to a Simplex method, where the jumps are along an extreme edge.
University of Washington