Countably Infinite Monotropic Programs

University Of Washington, Seattle WA

Investigators

Abstract

Countably infinite monotropic programs form a large class of convex optimization problems that arise in infinite-horizon planning applications in economics, inventory control, supply chain management, asset selling, equipment replacement, capacity expansion, and dynamic resource allocation. Existing theoretical knowledge about the structure of optimal solutions to these problems is very sparse. Efficient algorithms for their solution are also non-existent. This project will develop a mathematically rigorous theoretical and computational framework to tackle countably infinite monotropic programs. This will ultimately help governments, non-profit organizations, and private institutions make better farsighted decisions, and thus benefit the US economy and society. The PI will provide research opportunities to students from his undergraduate classes and incorporate research findings into his graduate classes. The project will thus contribute to educating students in mathematics and engineering. Finite-dimensional monotropic programs include linear programs, separable convex programs with linear constrains, and convex minimum cost network flow problems as special cases. Classic works of Minty and Rockafellar have revealed important connections between their geometric and analytical properties. Duality results for finite-dimensional monotropic programs are as powerful as those available for linear programs. These, in turn, have led to efficient solution algorithms. However, countably infinite extensions of such results have proven elusive owing to several mathematical pathologies in infinite-dimensional sequence spaces. The PI plans to overcome these hurdles by exploiting insights from his recent theoretical and algorithmic work on countably infinite linear programs. Specifically, the project will first provide three hypotheses for choosing primal and dual variable spaces so that weak duality and complementary slackness for countably infinite monotropic programs can be established via finite-dimensional proof techniques. It will then derive boundedness conditions under which strong duality in finite-dimensional approximations of countably infinite monotropic programs is preserved in the limit. The PI will also develop implementable approximations of infinite-dimensional extensions of classic finite-dimensional solution procedures such as descent algorithms, relaxation methods, and auction algorithms. These approximations will be adaptively designed to include a sufficient number of variables in reduced-cost and other calculations so as to guarantee monotone convergence to optimality. The resulting algorithms will be compared against a planning horizon benchmark that simply solves a sequence of larger and larger finite-dimensional approximations. This research will draw from and contribute to fundamental results in functional and convex analysis, and in infinite-dimensional linear algebra and combinatorics. It will also pave the way for future work on more general infinite-dimensional convex programs.