Countably Infinite Monotropic Programs

可数无限单调规划形成了一大类凸优化问题，这些问题出现在无限长期规划的经济、库存控制、供应链管理、资产出售、设备更换、能力扩展和动态资源分配等应用中。现有的关于这些问题的最优解结构的理论知识非常稀少。解决这些问题的有效算法也是不存在的。这个项目将开发一个数学上严格的理论和计算框架来处理可数不清的无限单调规划。这最终将有助于政府、非营利组织和私人机构做出更有远见的决策，从而使美国经济和社会受益。PI将为他的本科生班级的学生提供研究机会，并将研究成果纳入他的研究生班级。有限维单调规划包括线性规划、线性约束可分凸规划和凸最小费用网络流问题作为特例。Minty和Rockafella的经典作品揭示了它们的几何性质和分析性质之间的重要联系。有限维单调规划的对偶结果与线性规划的对偶结果一样强大。这些反过来又导致了高效的求解算法。然而，由于无限维序列空间中的几种数学病理，这种结果的无限扩展已被证明是难以捉摸的。PI计划通过利用他最近在可数无限线性规划的理论和算法工作中的见解来克服这些障碍。具体地说，该项目将首先提供选择原始变量空间和对偶变量空间的三个假设，以便通过有限维证明技术建立可数无限单调规划的弱对偶和互补松弛。然后，它将得到有界性条件，在这些条件下，可数无限单调规划的有限维近似的强对偶保持在极限中。PI还将开发经典有限维解程序的无限维扩展的可实现近似，例如下降算法、松弛方法和拍卖算法。这些近似将被适应性地设计为在降低成本和其他计算中包括足够数量的变量，以保证单调收敛到最优。所产生的算法将与计划范围基准进行比较，该基准仅求解一系列越来越大的有限维近似。这项研究将借鉴泛函和凸分析以及无限维线性代数和组合学的基本结果，并对其做出贡献。这也为以后更一般的无限维凸规划的研究铺平了道路。

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.