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

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Georgia Institute of Technology
  • RMIT University

Abstract

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.

Details

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

    Research areas

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

ID: 18110742