Countably Infinite Monotropic Programs

在经济学、库存控制、供应链管理、资产出售、设备更换、产能扩张和动态资源分配等领域的无限视界规划应用中，可数无限单调规划形成了一大类凸优化问题。现有的关于这些问题最优解结构的理论知识非常稀少。解决这些问题的有效算法也不存在。这个项目将发展一个数学上严格的理论和计算框架来处理可数无限的单性程序。这最终将帮助政府、非营利组织和私人机构做出更有远见的决策，从而使美国经济和社会受益。PI将为他的本科生提供研究机会，并将研究成果纳入他的研究生课程。因此，该项目将有助于教育数学和工程方面的学生。有限维单调规划包括线性规划、带线性约束的可分离凸规划以及作为特殊情况的凸最小代价网络流问题。Minty和Rockafellar的经典著作揭示了它们的几何性质和解析性质之间的重要联系。有限维单调规划的对偶性结果与线性规划的对偶性结果一样有力。这些，反过来，导致了有效的解决算法。然而，由于无限维序列空间中的一些数学病态，这些结果的可数无限扩展被证明是难以捉摸的。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.