Duality in Countably Infinite Monotropic Programs
研究了可数无限单调规划的对偶性，克服了无限维序列空间中的数学困难，建立了弱对偶、互补松弛以及零对偶间隙和强对偶的条件，适用于无限时域序贯决策和鲁棒优化问题。
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.