Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications

Abstract

In this paper, we propose a new decomposition approach named the proximal primal dual algorithm (Prox-PDA) for smooth nonconvex linearly constrained optimization problems. The proposed approach is primal-dual based, where the primal step minimizes certain approximation of the augmented Lagrangian of the problem, and the dual step performs an approximate dual ascent. The approximation used in the primal step is able to decompose the variable blocks, making it possible to obtain simple subproblems by leveraging the problem structures. Theoretically, we show that whenever the penalty parameter in the augmented Lagrangian is larger than a given threshold, the Prox-PDA converges to the set of stationary solutions, globally and in a sublinear manner (i.e., certain measure of stationarity decreases in the rate of $\mathcal{O}(1/r)$, where $r$ is the iteration counter). Interestingly, when applying a variant of the Prox-PDA to the problem of distributed nonconvex optimization (over a connected undirected graph), the resulting algorithm coincides with the popular EXTRA algorithm [Shi et al 2014], which is only known to work in convex cases. Our analysis implies that EXTRA and its variants converge globally sublinearly to stationary solutions of certain nonconvex distributed optimization problem. There are many possible extensions of the Prox-PDA, and we present one particular extension to certain nonconvex distributed matrix factorization problem.

References in corpus (1)

• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach

Cited by in corpus (17)

• On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learning
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• A two-level distributed algorithm for nonconvex constrained optimization
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
• Dual Descent ALM and ADMM
• Algorithms for Difference-of-Convex (DC) Programs Based on Difference-of-Moreau-Envelopes Smoothing
• A Non-monotone Alternating Updating Method for A Class of Matrix Factorization Problems