Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
From MaRDI portal
Publication:6044978
augmented Lagrangian methodconvergence ratesiterates convergenceNesterov's fast gradient methodprimal-dual numerical algorithm
Action-minimizing orbits and measures for finite-dimensional Hamiltonian and Lagrangian systems; variational principles; degree-theoretic methods (37J51) Approximation methods and numerical treatment of dynamical systems (37M99) Optimality conditions for problems involving ordinary differential equations (49K15) Numerical methods involving duality (49M29) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25)
Abstract: This work aims to minimize a continuously differentiable convex function with Lipschitz continuous gradient under linear equality constraints. The proposed inertial algorithm results from the discretization of the second-order primal-dual dynamical system with asymptotically vanishing damping term addressed by Bot and Nguyen in [Bot, Nguyen, JDE, 2021], and it is formulated in terms of the Augmented Lagrangian associated with the minimization problem. The general setting we consider for the inertial parameters covers the three classical rules by Nesterov, Chambolle-Dossal and Attouch-Cabot used in the literature to formulate fast gradient methods. For these rules, we obtain in the convex regime convergence rates of order for the primal-dual gap, the feasibility measure, and the objective function value. In addition, we prove that the generated sequence of primal-dual iterates converges to a primal-dual solution in a general setting that covers the two latter rules. This is the first result which provides the convergence of the sequence of iterates generated by a fast algorithm for linearly constrained convex optimization problems without additional assumptions such as strong convexity. We also emphasize that all convergence results of this paper are compatible with the ones obtained in [Bot, Nguyen, JDE, 2021] in the continuous setting.
Recommendations
- Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence \(O\left({1/{k^2}} \right)\)
- Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
- scientific article; zbMATH DE number 2201293
Cites work
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- An accelerated linearized alternating direction method of multipliers
- Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
- Applying FISTA to optimization problems (with or) without minimizers
- Conjugate duality in convex optimization
- Convergence rates of inertial forward-backward algorithms
- Convergence rates of inertial primal-dual dynamical methods for separable convex optimization problems
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Fast alternating direction optimization methods
- Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics
- Faster Lagrangian-based methods in convex optimization
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- Introductory lectures on convex optimization. A basic course.
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Optimal primal-dual methods for a class of saddle point problems
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
Cited in
(28)- Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence \(O\left({1/{k^2}} \right)\)
- Fast primal-dual gradient method for strongly convex minimization problems with linear constraints
- Faster Lagrangian-based methods in convex optimization
- Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems
- Time rescaling of a primal-dual dynamical system with asymptotically vanishing damping
- A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem
- Fast convergence of inertial multiobjective gradient-like systems with asymptotic vanishing damping
- Accelerated primal-dual methods with adaptive parameters for composite convex optimization with linear constraints
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- O(1/k^2) convergence rates of (dual-primal) balanced augmented Lagrangian methods for linearly constrained convex programming
- Inertial accelerated augmented Lagrangian algorithms with scaling coefficients to solve exactly and inexactly linearly constrained convex optimization problems
- Fast convergence of the primal-dual dynamical system and corresponding algorithms for a nonsmooth bilinearly coupled saddle point problem
- Accelerated forward-backward algorithms with subgradient corrections
- Fast primal-dual algorithm with Tikhonov regularization for a linear equality constrained convex optimization problem
- Accelerated primal-dual methods for strongly convex objective functions in continuous and discrete time
- Exponential convergence rates of a second-order dynamic system and algorithm for a linear equality constrained optimization problem
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- Convergence rates of mixed primal-dual dynamical systems with Hessian driven damping
- Faster augmented Lagrangian method with inertial steps for solving convex optimization problems with linear constraints
- Inertial accelerated primal-dual algorithms for non-smooth convex optimization problems with linear equality constraints
- Accelerated linearized alternating direction method of multipliers with Nesterov extrapolation
- Fast convergence of primal-dual dynamical systems with implicit Hessian damping and Tikhonov regularization
- The augmented Lagrangian methods: overview and recent advances
- Primal-dual dynamics featuring Hessian-driven damping and variable mass for convex optimization problems
- On the o(1/k^2) convergence rate analysis for general inertial gradient type method
- A continuous perspective on the inertial corrected primal-dual proximal splitting
This page was built for publication: Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6044978)
