Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming

DOI10.1137/22M1503129MaRDI QIDQ6136662zbMATH OpenOpenAlexFDO

Authors Weiwei Kong, Renato D. C. Monteiro

Publication date 17 January 2024

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.12502

zbMATH Keywords

iteration complexityproximal ADMMaugmented Lagrangian functionnonseparable nonconvex composite optimizationunder-relaxed update

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: This paper proposes and analyzes a dampened proximal alternating direction method of multipliers (DP.ADMM) for solving linearly-constrained nonconvex optimization problems where the smooth part of the objective function is nonseparable. Each iteration of DP.ADMM consists of: (i) a sequence of partial proximal augmented Lagrangian (AL) updates, (ii) an under-relaxed Lagrange multiplier update, and (iii) a novel test to check whether the penalty parameter of the AL function should be updated. Under a basic Slater condition and some requirements related to the dampening factor and under-relaxation parameter, it is shown that DP.ADMM obtains a first-order stationary point of the constrained problem in $calO(varepsilo{n}^{-3})$ iterations for a given numerical tolerance $varepsilon>0$. One of the main novelties of the paper is that convergence of the method is obtained without requiring any rank assumptions on the constraint matrices.

Recommendations

• Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints
• A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
• A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
• An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems

Cites work

• scientific article; zbMATH DE number 3574917 (Why is no real title available?)
• scientific article; zbMATH DE number 679861 (Why is no real title available?)
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A family of projective splitting methods for the sum of two maximal monotone operators
• A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
• An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems
• An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems
• An augmented Lagrangian decomposition method for block diagonal linear programming problems
• An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
• An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
• An inertial proximal alternating direction method of multipliers for nonconvex optimization
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• General Projective Splitting Methods for Sums of Maximal Monotone Operators
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
• Nonlinear programming
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Operator-Splitting Methods for Monotone Affine Variational Inequalities, with a Parallel Application to Optimal Control
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent

Cited in

(1)

• Dual descent augmented Lagrangian method and alternating direction method of multipliers

This page was built for publication: Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136662)