Variable Metric Forward-Backward Algorithm for Composite Minimization Problems
From MaRDI portal
composite minimization problemforward-backward algorithminverse problemsmajorize-minimize methodnonconvex optimizationnonsmooth optimizationproximity operatorreweighting algorithm
Decomposition methods (49M27) Numerical optimization and variational techniques (65K10) Computing methodologies for image processing (68U10) Approximation algorithms (68W25) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)
Abstract: We present a forward-backward-based algorithm to minimize a sum of a differentiable function and a nonsmooth function, both being possibly nonconvex. The main contribution of this work is to consider the challenging case where the nonsmooth function corresponds to a sum of non-convex functions, resulting from composition between a strictly increasing, concave, differentiable function and a convex nonsmooth function. The proposed variable metric Composite Function Forward-Backward algorithm (C2FB) circumvents the explicit, and often challenging, computation of the proximity operator of the composite functions through a majorize-minimize approach. Precisely, each composite function is majorized using a linear approximation of the differentiable function, which allows one to apply the proximity step only to the sum of the nonsmooth functions. We prove the convergence of the algorithm iterates to a critical point of the objective function leveraging the Kurdyka-L ojasiewicz inequality. The convergence is guaranteed even if the proximity operators are computed inexactly, considering relative errors. We show that the proposed approach is a generalization of reweighting methods, with convergence guarantees. In particular, applied to the log-sum function, our algorithm reduces to a generalized version of the celebrated reweighted method. Finally, we show through simulations on an image processing problem that the proposed C2FB algorithm necessitates less iterations to converge and leads to better critical points compared with traditional reweighting methods and classic forward-backward algorithms.
Recommendations
- Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
- Forward-backward-based descent methods for composite variational inequalities
- The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions
- Variable Metric Method for Minimization
- Variable Metric Function Minimization
- A Variable Metric Extension of the Forward–Backward–Forward Algorithm for Monotone Operators
- scientific article; zbMATH DE number 3852805
- A variable metric method for nonsmooth convex constrained optimization
- Variable metrid method for minimization of partially separable nonsmooth functions
Cites work
- A block coordinate variable metric forward-backward algorithm
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Gauss-Newton method for convex composite optimization
- A model algorithm for composite nondifferentiable optimization problems
- A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
- A primal-dual hybrid gradient method for nonlinear operators with applications to MRI
- A proximal method for composite minimization
- A wavelet tour of signal processing. The sparse way.
- Accelerated and inexact forward-backward algorithms
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Clarke Subgradients of Stratifiable Functions
- Composite optimization by nonconvex majorization-minimization
- Compressive sampling
- Convergence of an Inexact Algorithm for Composite Nonsmooth Optimization
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence Rates in Forward--Backward Splitting
- Convex Analysis
- Descent methods for composite nondifferentiable optimization problems
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Factoring wavelet transforms into lifting steps
- First order algorithms in variational image processing
- First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
- scientific article; zbMATH DE number 439380 (Why is no real title available?)
- scientific article; zbMATH DE number 3868525 (Why is no real title available?)
- scientific article; zbMATH DE number 563657 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints
- Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
- Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
- Non-smooth non-convex Bregman minimization: unification and new algorithms
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision
- On the convergence of a linesearch based proximal-gradient method for nonconvex optimization
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- On the convergence properties of the EM algorithm
- On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
- On the global convergence of trust region algorithms for unconstrained minimization
- On the superlinear convergence of a trust region algorithm for nonsmooth optimization
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximité et dualité dans un espace hilbertien
- Proximity for sums of composite functions
- Relaxed Gauss-Newton methods with applications to electrical impedance tomography
- Signal Recovery by Proximal Forward-Backward Splitting
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
- Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
- Variable metric forward-backward splitting with applications to monotone inclusions in duality
- Variational Analysis
Cited in
(14)- A generalized forward-backward splitting operator: degenerate analysis and applications
- A variable metric forward-backward method with extrapolation
- A Variable Metric Extension of the Forward–Backward–Forward Algorithm for Monotone Operators
- Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function
- The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions
- On an iteratively reweighted linesearch based algorithm for nonconvex composite optimization
- Stochastic variable metric proximal gradient with variance reduction for non-convex composite optimization
- Analysis of a variable metric block coordinate method under proximal errors
- A two-metric variable scaled forward-backward algorithm for \(\ell_0\) optimization problem and its applications
- Quasi-Newton type proximal gradient method for nonconvex nonsmooth composite optimization problems
- The variable metric three-operator algorithms for solving monotone inclusions
- A variational approach for joint image recovery and feature extraction based on spatially varying generalised Gaussian models
- A stochastic use of the Kurdyka-Łojasiewicz property: investigation of optimization algorithms behaviours in a non-convex differentiable framework
- A block coordinate variable metric forward-backward algorithm
This page was built for publication: Variable Metric Forward-Backward Algorithm for Composite Minimization Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989931)
