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.

工程师和政策制定者经常面临在不确定性下做出重要决策的问题。在进行关键基础设施，设计化学制造厂，运营国家电力电网或管理供应链的投资时，会发生这种情况。这是因为材料和能源的价格，未来的供应，工程系统的性能以及不良事件的发生通常存在明显的不确定性。该项目旨在开发改进的计算方法，以解决称为随机程序的这种决策问题的广泛使用数学模型。在这种模型中未能说明不确定性通常会导致更高次优或不可行的决策。但是，明确建模不确定性通常会产生巨大的计算问题，这远远超出了现有算法的功能。该项目的目的是开发新的数学理论和算法，以使此类问题能够通过高性能并行计算机有效地分解和解决，从而可以解决更大的问题。这将减少对当前在许多关键应用程序中降低决策的积极简化的需求。仅仅一个例子，它将有助于超越电力部门过于简单的模型，这些模型如今已广泛用于为高度的能源投资和政策决策提供信息。该项目涉及研究生和本科研究人员，包括开发该项目的Georgia技术目标K-12 STEM外展工作的研究活动，是为了开发新的分解算法来解决非convex随机计划（SPS）以保证以比现有方法更高的效率确保全球优化性。对于线性/凸问题，分解技术使解决物流和日程安排中的非常大问题的解决方案具有巨大的社会影响。但是，这些方法不适用于NonConvex SPS。当前的做法是启发分解或诉诸于尺度较低的全空间方法。当仅限于合理的时间预算时，两种方法通常都会导致高度次优或不可行的解决方案。最近，出现了一类新的分解方法，可以保证一般非凸SPS的全球最优性。不幸的是，这些技术在实践中仍然不足。在该研究计划中，开发改进算法的方法将由最新理论的独特应用来指导，该理论解释了全球优化算法在群集问题及其与低结合融合顺序的关系方面的效率。具体而言，PI的研究小组发现，现有的分解算法不满足对有效全球优化至关重要的关键收敛属性。该见解将用于设计新算法，并提高收敛性，效率和可扩展性。这项工作将产生有关非凸SPS的潜在，局限性和方法的基本知识。这些进步可能对超出随机计划以外的分解具有重大影响，并可能对优化，系统工程，运营研究和高性能计算领域产生重大影响。该奖项反映了NSF的法定任务，并已通过评估基金会的知识智能和更广泛的影响来评估诚实的支持。