NOVEL DECOMPOSITION ALGORITHMS FOR GUARANTEED GLOBAL OPTIMIZATION OF LARGE-SCALE NONCONVEX STOCHASTIC PROGRAMS

确保大规模非凸随机程序全局优化的新颖分解算法

• 批准号: 2232588
• 负责人: Joseph Scott
• 金额: $ 38.43万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2026-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2232588&HistoricalAwards=false
• 关键词: NOVEL; DECOMPOSITION; ALGORITHMS; GUARANTEED; GLOBAL

Engineers and policy makers are often faced with the problem of making important decisions under uncertainty. This occurs when making investments in critical infrastructure, designing chemical manufacturing plants, operating the national electric power grid, or managing a supply chain. This is because there is often significant uncertainty in the price of materials and energy, future supply and demand, the performance of engineered systems, and the occurrence of adverse events. This project aims to develop improved computational methods for solving a widely used mathematical model of such decision-making problems called stochastic programs. Failing to account for uncertainty in such models often leads to decisions that are highly suboptimal or infeasible. Yet, explicitly modeling uncertainty often creates enormous computational problems far beyond the capabilities of existing algorithms. The goal of this project is to develop new mathematical theory and algorithms that enable such problems to be effectively decomposed and solved with high-performance parallel computers, making it possible to solve much larger problems. This will reduce the need for aggressive simplifications that currently degrade decision-making in many critical applications. As just one example, it will help move beyond the overly simplistic models of the electric power sector that are widely used today to inform highly consequential energy investment and policy decisions. The project involves both graduate and undergraduate researchers and includes the development of research activities for use in K-12 STEM outreach efforts at Georgia Tech.The technical objective of this project is to develop novel decomposition algorithms for solving nonconvex stochastic programs (SPs) to guaranteed global optimality with significantly higher efficiency than existing methods. For linear/convex problems, decomposition techniques have enabled the solution of very large problems in logistics and scheduling with enormous societal impact. However, these methods are not applicable to nonconvex SPs. Current practice is to either apply decomposition heuristically or resort to full-space methods with inferior scaling. When restricted to a reasonable time budget, both approaches often lead to highly suboptimal or infeasible solutions. Recently, a new class of decomposition methods has emerged that guarantees global optimality for general nonconvex SPs. Unfortunately, these techniques are still underpowered in practice. In this research program, an approach to developing improved algorithms will be guided by a unique application of recent theory explaining the efficiency of global optimization algorithms in terms of the cluster problem and its relation to lower-bound convergence orders. Specifically, the PI’s research group has discovered that existing decomposition algorithms do not satisfy a key convergence property that is critical for efficient global optimization. This insight will be used to design new algorithms with improved convergence, efficiency, and scalability. This work will generate fundamental knowledge about the potential, limitations, and methods of decomposition for nonconvex SPs. These advances are likely to have significant implications for decomposition beyond stochastic programs and could have major impacts on the fields of optimization, systems engineering, operations research, and high-performance computing.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

工程师和政策制定者经常面临在不确定性下做出重要决策的问题。这发生在关键基础设施投资，设计化学制造厂，运营国家电网或管理供应链时。这是因为材料和能源的价格、未来的供求、工程系统的性能以及不良事件的发生往往存在很大的不确定性。该项目旨在开发改进的计算方法，用于解决被称为随机规划的此类决策问题的广泛使用的数学模型。在这种模型中，如果不考虑不确定性，往往会导致决策非常不理想或不可行。然而，显式建模的不确定性往往会产生巨大的计算问题远远超出现有算法的能力。该项目的目标是开发新的数学理论和算法，使这些问题能够有效地分解和解决高性能并行计算机，使解决更大的问题成为可能。这将减少对积极简化的需求，目前这种简化降低了许多关键应用程序的决策能力。仅举一个例子，它将有助于超越目前广泛使用的过于简单的电力部门模型，为高度重要的能源投资和政策决策提供信息。该项目涉及研究生和本科生的研究人员，包括在K-12干推广工作中使用的研究活动的发展在格鲁吉亚技术。该项目的技术目标是开发新的分解算法解决非凸随机程序（SP），以保证全局最优性显着高于现有的方法的效率。对于线性/凸问题，分解技术已经能够解决物流和调度中具有巨大社会影响的非常大的问题。然而，这些方法不适用于非凸SP。目前的做法是要么应用分解的方法，要么诉诸全空间的方法与劣质的缩放。当限制到合理的时间预算时，这两种方法往往导致高度次优或不可行的解决方案。最近，出现了一类新的分解方法，保证了一般非凸SP的全局最优性。不幸的是，这些技术在实践中仍然动力不足。在这项研究计划中，开发改进算法的方法将由最近理论的独特应用指导，解释全局优化算法在聚类问题及其与下界收敛阶的关系方面的效率。具体来说，PI的研究小组已经发现，现有的分解算法不满足一个关键的收敛性，这是有效的全局优化的关键。这种洞察力将用于设计具有改进的收敛性、效率和可扩展性的新算法。这项工作将产生的潜力，限制和非凸SP的分解方法的基础知识。这些进展可能对随机程序之外的分解产生重大影响，并可能对优化、系统工程、运筹学和高性能计算等领域产生重大影响。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。