Optimization Online


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

N. Boland(natashia.boland***at***gmail.com )
J. Christiansen(s3507717***at***student.rmit.edu.au)
B. Dandurand(brian.dandurand***at***rmit.edu.au)
A. Eberhard(andy.eberhard***at***rmit.edu.au)
F. Oliveira(fabricio.oliveira***at***rmit.edu.au)

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. The dual solution approach needs to address the nonconvexity of the non-relaxed constraint set while being efficiently implementable in parallel. We adapt the augmented Lagrangian method framework to address the presence of nonconvexity in the non-relaxed constraint set and the need for 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 the use of an integration of approaches based on the simplicial decomposition method (SDM) and the nonlinear block Gauss-Seidel (GS) 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.

Keywords: augmented Lagrangian method, proximal bundle method, nonlinear block Gauss-Seidel method, simplicial decomposition method, parallel computing

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 11/20/2016
Entry Accepted: 11/21/2016
Entry Last Modified: 11/20/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society