Thesis Title: Decomposition Algorithms based on the Nonconvex Augmented Lagrangian Framework

Advisor: 

Dr. Xu Andy Sun, Operations Research and Statistics, Sloan School of Management, MIT

Thesis Committee:

Dr. Santanu S. Dey, School of Industrial and Systems Engineering, Georgia Tech 

Dr. Renato D.C. Monteiro, School of Industrial and Systems Engineering, Georgia Tech 

Dr. Wotao Yin, Decision Intelligence Lab, Damo Academy, Alibaba Group US

Dr. Enlu Zhou, School of Industrial and Systems Engineering, Georgia Tech 

Date and Time: Thursday, April 14th, 2022, 8:00 PM (EST)

Meeting Link: https://mit.zoom.us/j/94439139936

Meeting ID: 944 3913 9936 

Abstract:

In this thesis, we develop new decomposition algorithms for several important classes of constrained nonconvex problems. The proposed algorithms take advantage of decomposable structures embedded in the original problem through the augmented Lagrangian framework. Chapters 2-4 are concerned with such structures in constraints, while Chapter 5 investigates a special separable structure in the objective.  

Chapter 2 is motivated by the observation that for a broad class of nonlinear constrained optimization problems defined over a network, distributed algorithms based on the alternating direction method of multipliers (ADMM) fail to converge due to certain formulation limitations. To overcome the difficulty, we propose a two-level framework, where the inner level utilizes a structured three-block ADMM to facilitate parallel computations and the outer level applies the classic augmented Lagrange method (ALM) to ensure convergence. We establish global convergence with iteration complexity estimates as well as local convergence results for this new scheme and demonstrate its performance on various nonconvex applications.

In Chapter 3, we adopt the two-level framework to solve the AC optimal power flow (OPF) problem, which is a basic building block in electric power systems. The two-level framework tailored to AC OPF provides a new distributed algorithm with global convergence guarantees and iteration complexity estimates. We present extensive numerical experiments on some largest open-sourced power networks (up to 30,000 buses) to demonstrate the speed, robustness, and scalability of the proposed algorithm. 

In Chapter 4, we investigate a new class of dual updates termed scaled dual descent (SDD) within the augmented Lagrangian framework. We propose SDD-ADMM, which combines SDD with ADMM, to solve nonlinear equality-constrained multi-block problems. SDD-ADMM improves previous state-of-the-art works of ALM and ADMM in several nontrivial perspectives, including new treatment of nonlinear constraints, less restrictions on problem data, and better iteration complexity results. Moreover, SDD-ADMM admits flexible Gauss-Seidel and Jacobi updates on blocks of variables, making the method particularly suitable for distributed computation. 

In Chapter 5, we first study a smoothing technique for a generic difference-of-convex (DC) function, where we replace both convex components by their respective Moreau envelopes. The resulting smooth approximation, termed difference of Moreau Envelopes (DME), is shown to be Lipschitz differentiable, capture stationary, local, and global solutions of the original DC function, and enjoy some growth conditions for broad classes of DC functions. In addition, the DME smoothing provides a powerful tool for algorithmic development: first-order updates on the DME deliver a stationary solution of the original DC function, and we can further combine the DME smoothing with ALM to solve constrained DC programs. An interesting feature that distinguishes DME-based algorithms from existing DC algorithms is that we invoke proximal oracles on the negative component instead of its subgradient oracles, and consequently, the updates on the two convex components can be implemented in parallel.

Best regards, 

Kaizhao Sun