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

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

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.