Duality in countably infinite monotropic programs

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Finite-dimensional monotropic programs form a class of convex optimization problems that includes linear programs, convex minimum cost flow problems on networks and hypernetworks, and separable convex programs with linear constraints. Countably infinite monotropic programs arise, for example, in infinite-horizon sequential decision problems and in robust optimization. Their applications encompass (i) countably infinite linear programs such as the shortest path formulations of infinite-horizon nonstationary as well as countable-state Markov decision processes; and (ii) convex minimum cost flow problems on countably infinite networks and hypernetworks. Duality results for finite-dimensional monotropic programs are as powerful as those available for linear programs. On the contrary, applicable duality results for countably infinite monotropic programs are currently nonexistent owing to several mathematical pathologies in infinite-dimensional sequence spaces. This paper overcomes this hurdle by first embedding the dual variables in a sequence space where the Lagrangian function is well-defined and finite. Weak duality and complementary slackness are derived using finite-dimensional proof techniques. Conditions under which zero duality gaps and strong duality between a sequence of finite-dimensional primal-dual projections of the infinite-dimensional problem are preserved in the limit are established. Essentially all known duality results about countably infinite mathematical programs are recovered as special cases.

Original languageEnglish (US)
Pages (from-to)2010-2033
Number of pages24
JournalSIAM Journal on Optimization
Volume27
Issue number3
DOIs
StatePublished - 2017
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics

Keywords

  • Convex optimization
  • Duality
  • Infinite-dimensional optimization

Fingerprint

Dive into the research topics of 'Duality in countably infinite monotropic programs'. Together they form a unique fingerprint.

Cite this