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

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

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.