Source-linked AI summary
An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions
Radu Ioan Bot, Ernö Robert Csetnek, Szilárd László
TL;DR
The paper tackles minimization of a smooth plus nonsmooth objective when both components may be nonconvex. It proposes an inertial forward-backward algorithm and proves convergence to critical points under a KL condition on an appropriate regularization, illustrating the analysis with optimization and image-restoration experiments.
Problem
Forward-backward methods are less understood in the full nonconvex setting, where the proximal point operator may be multivalued.
Method
The paper introduces an inertial forward-backward algorithm and analyzes it using sufficient decrease, subgradient bounds, and KL properties.
Results
The iterates converge to critical points when an appropriate regularization satisfies the KL property, with experiments on local-optimum detection and noisy blurred-image restoration.
Takeaways & Limitations
Inertial effects can detect optimal solutions not found by non-inertial versions, while the framework also addresses nonconvex image restoration.
Takeaways & Limitations
The stated convergence results require either coercivity or a bounded generated sequence when the objective is bounded below.
Abstract
from arXiv · showhide
We propose a forward-backward proximal-type algorithm with inertial/memory effects for minimizing the sum of a nonsmooth function with a smooth one in the nonconvex setting. The sequence of iterates generated by the algorithm converges to a critical point of the objective function provided an appropriate regularization of the objective satisfies the Kurdyka-Łojasiewicz inequality, which is for instance fulfilled for semi-algebraic functions. We illustrate the theoretical results by considering two numerical experiments: the first one concerns the ability of recovering the local optimal solutions of nonconvex optimization problems, while the second one refers to the restoration of a noisy blurred image.
1 Introduction
The paper addresses the less-understood full nonconvex setting by introducing an inertial forward-backward algorithm and analyzing its convergence under a KL-based condition. Two experiments examine inertial methods for detecting local optima and restoring noisy blurred images.
- The introduction situates proximal-gradient splitting as a framework that applies gradient steps to smooth terms and proximal steps to nonsmooth terms.
- Inertial schemes define each new iterate using the previous two iterates and originate from second-order differential inclusions.
- The paper extends inertial forward-backward methods to objectives whose nonsmooth and smooth components may both be nonconvex.Earlier work allowed a nonconvex smooth part but assumed the nonsmooth part was convex.
- Convergence is guaranteed when an appropriate regularization of the objective satisfies the Kurdyka-Lojasiewicz property.The proof combines sufficient decrease, a subgradient lower bound for iterate gaps, and KL analytic properties.
- The numerical experiments test local-optimum recovery that non-inertial methods miss and restoration of a noisy blurred image using nonconvex terms.
2 Preliminaries
The preliminaries establish the KL framework, limiting subdifferential tools, and sequence lemmas used to prove convergence. They also connect KL functions to broad analytic classes, including semi-algebraic functions.
- The limiting subdifferential is defined through limits of Fréchet subgradients along sequences whose points and function values converge.
- For convex functions, the Fréchet and limiting subdifferentials coincide with the convex subdifferential.
- The Fermat rule states that a local minimizer has zero in its limiting subdifferential, while sums with smooth functions obey a subdifferential sum rule.
- The KL property is defined for proper lower-semicontinuous functions through a desingularizing function satisfying a gradient-subgradient inequality near a point.
- KL functions include semi-algebraic, real sub-analytic, semiconvex, uniformly convex, and suitable convex functions.
- The analysis uses uniformized KL properties on compact sets, subdifferential closedness, and sequence convergence lemmas.
3 A forward-backward algorithm
The paper introduces an inertial forward-backward scheme for fully nonconvex objectives and establishes convergence under coercivity, boundedness, and KL-type assumptions. Its iterates approach critical points, with full convergence when the regularized objective is a KL function such as a semi-algebraic function.
- Algorithm: The proposed algorithm minimizes a nonsmooth f plus smooth g in the fully nonconvex setting using inertial and memory effects.It is formulated through a Bregman-distance-based iterative scheme with gradient, inertial, and proximal terms.
- Algorithm: The iteration is well-defined when f is proper, lower semicontinuous, bounded below and the Bregman distance is coercive in its first argument.Alternatively, coercivity of each iteration’s minimized objective can replace boundedness of f.
- Relations to existing methods: The scheme contains known methods as special cases, including inertial proximal-point iterations when g = 0 and classical forward-backward forms in the convex setting.Setting the inertial parameter to zero recovers non-inertial variants discussed in the paper.
- Convergence analysis: Under the stated parameter conditions, a Lyapunov-type sequence is decreasing and the objective values (f + g)(x_n) converge.The descent inequality combines objective values with squared successive-step terms.
- Convergence analysis: If f + g is coercive, every cluster point of the generated sequence is a critical point of f + g.Coercivity also yields bounded iterates, enabling subsequential convergence and criticality of cluster points.
- KL convergence: When the regularized objective is a KL function, the iterates have finite total step length and converge to a critical point.The paper states the result for semi-algebraic f + g as a direct corollary; boundedness below plus bounded iterates can replace coercivity.
4 Numerical experiments
The experiments assess inertial methods on nonconvex minimization and noisy blurred-image restoration. They compare inertial and non-inertial variants across optimization settings and reconstruction conditions.
- 4.1 Detecting minimizers of nonconvex optimization problems: The first experiment examines whether inertial or memory effects recover optimal solutions missed by non-inertial methods.The study uses a nonconvex nonsmooth function and compares trajectories from four starting points.
- 4.1 Detecting minimizers of nonconvex optimization problems: Figure 2 compares 100-iteration trajectories from four starting points using non-inertial β = 0 and inertial β = 1.99 or β = 2.99.The first, second, and third columns correspond to these parameter choices, respectively.
- 4.1 Detecting minimizers of nonconvex optimization problems: The test problem has two optimal solutions, (0, 1/2) and (0, −1/2), obtained from its first-order optimality conditions.The objective combines the nonconvex function f(x1, x2) = |x1| − |x2| with a smooth term whose gradient has Lipschitz constant L∇g = 9/4.
- 4.2 Restoration of noisy blurred images: The image experiment restores a 256 × 256 boat image from Gaussian-blurred and noisy observations using a nonconvex misfit and nonconvex regularization.The blur operator has size 9 × 9 and standard deviation 4, while the added zero-mean white Gaussian noise has standard deviation 10^-6.
- 4.2 Restoration of noisy blurred images: After 300 iterations, very small inertial parameters produce ISNR values competitive with, and slightly better than, the non-inertial version.The comparison uses β = 0 for the non-inertial algorithm and evaluates ISNR for different constant β values.
- 4.2 Restoration of noisy blurred images: Figure 3 presents the original and blurred noisy images in the first row and reconstructed images after 300 iterations in the second row.The reconstructions compare the non-inertial version with the inertial version using β = 10^-7.