A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems

Natashia Boland, Jeffrey Christiansen, Brian Dandurand, Andrew Eberhard, Fabricio Oliveira

Research output: Contribution to journalArticleScientificpeer-review

18 Citations (Scopus)


We contribute improvements to a Lagrangian dual solution approach applied to large-scale optimization problems whose objective functions are convex, continuously differentiable and possibly nonlinear, while the non-relaxed constraint set is compact but not necessarily convex. Such problems arise, for example, in the split-variable deterministic reformulation of stochastic mixed-integer optimization problems. We adapt the augmented Lagrangian method framework to address the presence of nonconvexity in the non-relaxed constraint set and to enable efficient parallelization. The development of our approach is most naturally compared with the development of proximal bundle methods and especially with their use of serious step conditions. However, deviations from these developments allow for an improvement in efficiency with which parallelization can be utilized. Pivotal in our modification to the augmented Lagrangian method is an integration of the simplicial decomposition method and the nonlinear block Gauss–Seidel method. An adaptation of a serious step condition associated with proximal bundle methods allows for the approximation tolerance to be automatically adjusted. Under mild conditions optimal dual convergence is proven, and we report computational results on test instances from the stochastic optimization literature. We demonstrate improvement in parallel speedup over a baseline parallel approach.

Original languageEnglish
Pages (from-to)503-536
Number of pages34
JournalMathematical Programming
Issue number1-2
Publication statusPublished - 1 May 2019
MoE publication typeA1 Journal article-refereed


  • Augmented Lagrangian method
  • Nonlinear block Gauss–Seidel method
  • Parallel computing
  • Proximal bundle method
  • Simplicial decomposition method


Dive into the research topics of 'A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems'. Together they form a unique fingerprint.

Cite this