Duality in convex minimum cost flow problems on infinite networks and hypernetworks

Minimum cost flow problems on infinite networks arise, for example, in infinite-horizon sequential decision problems such as production planning. Strong duality for these problems was recently established for linear costs using an infinite-dimensional Simplex algorithm. Here, we use a different approach to derive duality results for convex costs. We formulate the primal and dual problems in appropriately paired sequence spaces such that weak duality and complementary slackness can be established using finite-dimensional proof techniques. We then prove, using a planning horizon proof technique, that the absence of a duality gap between carefully constructed finite-dimensional truncations of the primal problem and their duals is preserved in the limit. We then establish that strong duality holds when optimal solutions to the finite-dimensional duals are bounded. These theoretical results are illustrated via an infinite-horizon shortest path problem. We also extend our results to infinite hypernetworks and apply this generalization to an infinite-horizon stochastic shortest path problem.