Countably Infinite Monotropic Programs

可数无限单向程序

• 批准号: 1561918
• 负责人: Archis Ghate
• 金额: $ 32.51万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-03-01 至 2020-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1561918&HistoricalAwards=false
• 关键词: Countably; Infinite; Monotropic; Programs

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.

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