A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
From MaRDI portal
Publication:2425176
DOI10.1007/S10107-018-1327-8zbMATH Open1415.90121arXiv1710.05778OpenAlexW2963373709WikidataQ129265374 ScholiaQ129265374MaRDI QIDQ2425176FDOQ2425176
Authors: Tianxiang Liu, Ting Kei Pong, Akiko Takeda 
Publication date: 26 June 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a smooth function and a finite number of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises naturally in various applications when different regularizers are introduced for inducing simultaneous structures in the solutions. Solving these problems, however, can be challenging because of the coupled nonsmooth functions: the corresponding proximal mapping can be hard to compute so that standard first-order methods such as the proximal gradient algorithm cannot be applied efficiently. In this paper, we propose a successive difference-of-convex approximation method for solving this kind of problems. In this algorithm, we approximate the nonsmooth functions by their Moreau envelopes in each iteration. Making use of the simple observation that Moreau envelopes of nonnegative proper closed functions are continuous {em difference-of-convex} functions, we can then approximately minimize the approximation function by first-order methods with suitable majorization techniques. These first-order methods can be implemented efficiently thanks to the fact that the proximal mapping of {em each} nonsmooth function is easy to compute. Under suitable assumptions, we prove that the sequence generated by our method is bounded and any accumulation point is a stationary point of the objective. We also discuss how our method can be applied to concrete applications such as nonconvex fused regularized optimization problems and simultaneously structured matrix optimization problems, and illustrate the performance numerically for these two specific applications.
Full work available at URL: https://arxiv.org/abs/1710.05778
Recommendations
- Stochastic proximal difference-of-convex algorithm with SPIDER for a class of nonconvex nonsmooth regularized problems
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- Nonconvex nonsmooth optimization via convex-nonconvex majorization-minimization
- Nonmonotone enhanced proximal DC algorithms for a class of structured nonsmooth DC programming
- Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions
Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)
Cites Work
- Templates for convex cone problems with applications to sparse signal recovery
- Title not available (Why is that?)
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Variational Analysis
- Convex analysis and monotone operator theory in Hilbert spaces
- The solution path of the generalized lasso
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Smooth minimization of non-smooth functions
- Exact matrix completion via convex optimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Convex Analysis
- Computing a nearest correlation matrix with factor structure
- Sparse Reconstruction by Separable Approximation
- Sparse Approximation via Penalty Decomposition Methods
- Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization
- Structured low-rank approximation and its applications
- Sparse and stable Markowitz portfolios
- Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms
- Fast Moreau envelope computation I: Numerical algorithms
- Shorter Notes: Differentiability of the Metric Projection in Finite- Dimensional Euclidean Space
- Global convergence of splitting methods for nonconvex composite optimization
- DC formulations and algorithms for sparse optimization problems
- Penalty decomposition methods for rank minimization
- Difference-of-convex learning: directional stationarity, optimality, and sparsity
Cited In (23)
- Convergence rate analysis of an extrapolated proximal difference-of-convex algorithm
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- Title not available (Why is that?)
- Convergence of a Class of Nonmonotone Descent Methods for Kurdyka–Łojasiewicz Optimization Problems
- Decomposition methods for computing directional stationary solutions of a class of nonsmooth nonconvex optimization problems
- Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations
- Sparsity constrained optimization problems via disjunctive programming
- Sparse solutions of a class of constrained optimization problems
- A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection
- Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions
- Proximal gradient method with extrapolation and line search for a class of non-convex and non-smooth problems
- A refined convergence analysis of \(\mathrm{pDCA}_{e}\) with applications to simultaneous sparse recovery and outlier detection
- Penalty and augmented Lagrangian methods for constrained DC programming
- Title not available (Why is that?)
- Non-convex split Feasibility problems: models, algorithms and theory
- Nonconvex and nonsmooth sparse optimization via adaptively iterative reweighted methods
- Stochastic proximal difference-of-convex algorithm with SPIDER for a class of nonconvex nonsmooth regularized problems
- Alternating DC algorithm for partial DC programming problems
- A hybrid penalty method for a class of optimization problems with multiple rank constraints
- Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- Error bound and isocost imply linear convergence of DCA-based algorithms to D-stationarity
- The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions
Uses Software
This page was built for publication: A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425176)
