Back to search

Georgia Institute of Technology

Decomposition algorithms based on the nonconvex augmented Lagrangian framework

Abstract

dc:description.abstract

Many problems of recent interest arising from engineering and data sciences go beyond the framework of convex optimization and inevitably need to deal with nonconvex structures. The design of efficient optimization algorithms when non-convexity is present, either in constraints or in the objective, has always been a difficult task. Meanwhile, the sheer amount of data that need to be considered in applications nowadays bring in new computational challenges. In this thesis, we develop new convergence-guaranteed decomposition methods for several important classes of nonconvex problems. The proposed algorithms take advantage of decomposable structures embedded in the original problem. The first part of this thesis is concerned with decomposable structures in constraints. We are motivated by the observation that, for a broad class of nonlinear constrained optimization problems defined over a network, existing distributed algorithms based on the popular 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 particular, we adopt the two-level framework to solve the nonconvex AC optimal power flow (OPF) problem, which is a basic building block in electric power systems. 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. The powerful algorithmic frameworks of ALM and ADMM inspire us to further exploit their potentials for solving nonconvex optimization problems. 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 the 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. The second part of this thesis investigates a specific decomposable structure in the objective, namely, when the objective is a difference-of-convex (DC) function, i.e., a function $F = \phi-g$ where both $\phi$ and $g$ are convex functions. We first study a smoothing technique for a generic DC function $F$, where we replace both $\phi$ and $g$ 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 $F$, 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 $F$, 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 (DCA) is that we invoke proximal oracles on the negative component $g$ instead of its subgradient oracles, and consequently, the updates on $\phi$ and $g$ can be implemented in parallel.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sun, Kaizhao
Advisor dc:contributor.advisor
  • Sun, X. Andy
Committee members dc:contributor.committeemember
  • Dey , Santanu S.
  • Monteiro , Renato D.C.
  • Yin , Wotao
  • Zhou , Enlu

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/66637

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sun, Kaizhao. Decomposition algorithms based on the nonconvex augmented Lagrangian framework. Doctoral thesis, Georgia Institute of Technology, 2022. http://hdl.handle.net/1853/66637