Premium
Duality in convex minimum cost flow problems on infinite networks and hypernetworks
Author(s) -
Nourollahi Sevnaz,
Ghate Archis
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21754
Subject(s) - duality gap , dual polyhedron , duality (order theory) , mathematics , strong duality , minimum cost flow problem , perturbation function , bounded function , mathematical optimization , weak duality , generalization , flow network , convex optimization , regular polygon , convex analysis , optimization problem , combinatorics , mathematical analysis , geometry
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. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 98–115 2017