Global convergence of splitting methods for nonconvex composite optimization

Abstract

We consider the problem of minimizing the sum of a smooth function $h$ with a bounded Hessian, and a nonsmooth function. We assume that the latter function is a composition of a proper closed function $P$ and a surjective linear map $\mathcal{M}$, with the proximal mappings of $\tau P$, $\tau >0$, simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: alternating direction method of multipliers and proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that, if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions $h$ and $P$ are semi-algebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the ${\ell }_{1/2}$ regularization. Finally, when $\mathcal{M}$ is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex $h$.

To appear in SIOPT

Cited by in corpus (25)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results
• ${\ell }_0$-Motivated Low-Rank Sparse Subspace Clustering
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Efficient Nonlinear Precoding for Massive MU-MIMO Downlink Systems with 1-Bit DACs
• Data-driven sparse sensor placement based on A-optimal design of experiment with ADMM
• Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
• Data-Driven Sensor Selection Method Based on Proximal Optimization for High-Dimensional Data With Correlated Measurement Noise
• QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs
• A General Truncated Regularization Framework for Contrast-Preserving Variational Signal and Image Restoration: Motivation and Implementation
• Minimizing L1 over L2 norms on the gradient
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• A Framework of Inertial Alternating Direction Method of Multipliers for Non-Convex Non-Smooth Optimization
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Direction-of-Arrival Estimation for Constant Modulus Signals Using a Structured Matrix Recovery Technique
• Inertial nonconvex alternating minimizations for the image deblurring
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• Low-complexity method for hybrid MPC with local guarantees
• Globally Variance-Constrained Sparse Representation and Its Application in Image Set Coding
• Bregman Proximal Linearized ADMM for Minimizing Separable Sums Coupled by a Difference of Functions
• Distributed nonconvex optimization for control of water networks with time-coupling constraints
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• On Convergence of Heuristics Based on Douglas-Rachford Splitting and ADMM to Minimize Convex Functions over Nonconvex Sets
• Local saddle structure in relaxed averaged alternating reflections Algorithms on phase retrieval
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness