A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems
From MaRDI portal
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.
This article presents an improved solution method for large-scale optimization problems with a convex objective but a non-convex constraint set, using a Lagrangian dual solution method. The authors begin with an introduction to the problem and the notation used in the paper, followed by an overview of the relevant literature on augmented Lagrangian methods, proximal bundle methods and their parallelization as well as their variants. The third and fourth sections present the main result of the article where the new algorithm is described in detail and several properties are proven. The article concludes with a section containing the results of a detailed computational experimentation and suggestions for future work.
Recommendations
- Augmented Lagrangian method for large-scale linear programming problems
- An adaptive augmented Lagrangian method for large-scale constrained optimization
- A partial parallel splitting augmented Lagrangian method for solving constrained matrix optimization problems
- Parallel implementation of augmented Lagrangian method within L-shaped method for stochastic linear programs
- Augmented Lagrangian method with alternating constraints for nonlinear optimization problems
- An augmented Lagrangian method for non-Lipschitz nonconvex programming
- An alternating augmented Lagrangian method for constrained nonconvex optimization
- On the complexity of an augmented Lagrangian method for nonconvex optimization
- An inexact parallel splitting augmented Lagrangian method for large system of linear equations
- An augmented Lagrangian affine scaling method for nonlinear programming
Cites work
- A diagonal quadratic approximation method for large scale linear programs
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A new inexact alternating directions method for monotone variational inequalities
- A parallel bundle framework for asynchronous subspace optimization of nonsmooth convex functions
- A practical general approximation criterion for methods of multipliers based on Bregman distances
- A practical relative error criterion for augmented Lagrangians
- A proximal bundle method for nonsmooth nonconvex functions with inexact information
- A proximal-based deomposition method for compositions method for convex minimization problems
- An augmented Lagrangian method for distributed optimization
- An extension of the frank and Wolfe method of feasible directions
- Approximations in proximal bundle methods and decomposition of convex programs
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Bounds on the motion of objects ejected from an orbiting body
- Combining progressive hedging with a Frank-Wolfe method to compute Lagrangian dual bounds in stochastic mixed-integer programming
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convex Analysis
- Convex optimization algorithms
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Dual decomposition in stochastic integer programming
- Grouped coordinate minimization using Newton's method for inexact minimization in one vector coordinate
- scientific article; zbMATH DE number 6378171 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 46303 (Why is no real title available?)
- scientific article; zbMATH DE number 3559294 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1086732 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- scientific article; zbMATH DE number 3309655 (Why is no real title available?)
- Inexact block coordinate descent methods with application to non-negative matrix factorization
- Introduction to stochastic programming.
- Minimizing Certain Convex Functions
- Monotone Operators and the Proximal Point Algorithm
- Multiplier and gradient methods
- Nonlinear optimization.
- Object-oriented software for quadratic programming
- Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs
- On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization
- On parallelizing dual decomposition in stochastic integer programming
- On the choice of explicit stabilizing terms in column generation
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Proximal Decomposition on the Graph of a Maximal Monotone Operator
- Proximal Decomposition Via Alternating Linearization
- Separable approximations and decomposition methods for the augmented Lagrangian
- Simplicial decomposition in nonlinear programming algorithms
- Strengthened benders cuts for stochastic integer programs with continuous recourse
- Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
Cited in
(14)- A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
- Parallel subgradient algorithm with block dual decomposition for large-scale optimization
- Revisiting augmented Lagrangian duals
- Scalable branching on dual decomposition of stochastic mixed-integer programming problems
- The p-Lagrangian relaxation for separable nonconvex MIQCQP problems
- Parallel and distributed successive convex approximation methods for big-data optimization
- A matrix-free augmented Lagrangian algorithm with application to large-scale structural design optimization
- Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming
- Lagrange dual bound computation for stochastic service network design
- A partial parallel splitting augmented Lagrangian method for solving constrained matrix optimization problems
- A study of progressive hedging for stochastic integer programming
- Decomposition methods for global solution of mixed-integer linear programs
- An exact penalty function optimization method and its application in stress constrained topology optimization and scenario based reliability design problems
- A novel dual-decomposition method for non-convex two-stage stochastic mixed-integer quadratically constrained quadratic problems
This page was built for publication: A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414914)
