Global Convergence of Splitting Methods for Nonconvex Composite Optimization

By Guoyin Li, Ting Kei Pong. SIAM Journal on Optimization, 2014

446 citations recorded by the source corpus.

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 $\cal 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 $\cal 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$.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/d46669b65bbec5f0e1245dfc25397efd71b2377e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Modern regularization methods for inverse problems (2018, background): “It is important to emphasize that even for nonsmooth, nonconvex optimization there is a vast amount of recent publications, ranging from forward-backward, respectively proximaltype, schemes [8, 9, 10, 49, 50], over linearized proximal schemes [365, 47, 366, 298], to inertial methods [299, 309], prim”
Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods (2016, unknown): “One future research direction is to develop calculus rules for deducing the exponent of potential functions such as the augmented Lagrangian function Lβ(x, y, z) = f (x) + g(y) + zT (x − y) + β2 ‖x − y‖2 used in the convergence analysis of the alternating direction method of multiplier in a nonconve”
Fast optimization via inertial dynamics with closed-loop damping (2020, methodology): “where we used Proposition 1 in [48] (see also Remark 3 in [70]).”
Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization (2018, background): “We refer the readers to [33] for a similar argument.”