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

DOI10.1137/22M1503129arXiv2110.12502OpenAlexW4390747415MaRDI QIDQ6136662FDOQ6136662

Authors: Weiwei Kong, Renato D. C. Monteiro 

Publication date: 17 January 2024

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

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.

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

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

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)

Cites Work

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

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)