The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions

DOI10.1137/18M123339XzbMATH Open1461.65119arXiv1812.06070OpenAlexW3013364710MaRDI QIDQ5221263FDOQ5221263

Authors: Francisco J. Aragón Artacho, Phan Tu Vuong 

Publication date: 25 March 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: The Boosted Difference of Convex functions Algorithm (BDCA) was recently proposed for minimizing smooth difference of convex (DC) functions. BDCA accelerates the convergence of the classical Difference of Convex functions Algorithm (DCA) thanks to an additional line search step. The purpose of this paper is twofold. Firstly, to show that this scheme can be generalized and successfully applied to certain types of nonsmooth DC functions, namely, those that can be expressed as the difference of a smooth function and a possibly nonsmooth one. Secondly, to show that there is complete freedom in the choice of the trial step size for the line search, which is something that can further improve its performance. We prove that any limit point of the BDCA iterative sequence is a critical point of the problem under consideration, and that the corresponding objective value is monotonically decreasing and convergent. The global convergence and convergent rate of the iterations are obtained under the Kurdyka-Lojasiewicz property. Applications and numerical experiments for two problems in data science are presented, demonstrating that BDCA outperforms DCA. Specifically, for the Minimum Sum-of-Squares Clustering problem, BDCA was on average sixteen times faster than DCA, and for the Multidimensional Scaling problem, BDCA was three times faster than DCA.

Full work available at URL: https://arxiv.org/abs/1812.06070

Recommendations

• A new boosted proximal point algorithm for minimizing nonsmooth DC functions
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions
• scientific article; zbMATH DE number 4076972
• scientific article
• Stochastic difference-of-convex-functions algorithms for nonconvex programming
• An algorithm for linearly constrained convex nondifferentiable minimization problems
• On an algorithm in nondifferential convex optimization
• A new method for nonsmooth convex optimization
• An accelerated proximal algorithm for the difference of convex programming

zbMATH Keywords

clustering problemdifference of convex functionsboosted difference of convex functions algorithmKurdyka-Łojasiewicz propertymultidimensional scaling problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10)

Cites Work

• Convex analysis approach to d. c. programming: Theory, algorithms and applications
• Title not available (Why is that?)
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• A minimization method for the sum of a convex function and a continuously differentiable function
• Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
• Clarke Subgradients of Stratifiable Functions
• A generalized proximal point algorithm for certain non-convex minimization problems
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• On gradients of functions definable in o-minimal structures
• The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Title not available (Why is that?)
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• On the convergence of an approximate proximal method for DC functions
• A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
• Numerical solution for optimization over the efficient set by d.c. optimization algorithms
• A heuristic algorithm for solving the minimum sum-of-squares clustering problems
• Transactions on Computational Collective Intelligence XIII
• Title not available (Why is that?)
• Qualitative properties of the minimum sum-of-squares clustering problem
• Title not available (Why is that?)
• Variational analysis and applications
• DC programming and DCA: thirty years of developments
• Accelerating the DC algorithm for smooth functions
• An inertial algorithm for DC programming
• A general double-proximal gradient algorithm for d.c. programming
• Title not available (Why is that?)
• Convergence analysis of difference-of-convex algorithm with subanalytic data
• Nesterov's smoothing technique and minimizing differences of convex functions for hierarchical clustering
• Convergence analysis of a proximal point algorithm for minimizing differences of functions
• A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique

Cited In (26)

• A boosted DC algorithm for non-differentiable DC components with non-monotone line search
• The ABC of DC programming
• A unified Douglas-Rachford algorithm for generalized DC programming
• An augmented subgradient method for minimizing nonsmooth DC functions
• A bundle-type method for nonsmooth DC programs
• Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems
• A refined inertial DC algorithm for DC programming
• Accelerating the DC algorithm for smooth functions
• DC semidefinite programming and cone constrained DC optimization. I: Theory
• Using positive spanning sets to achieve d-stationarity with the boosted DC algorithm
• Incremental DC optimization algorithm for large-scale clusterwise linear regression
• A variable metric and Nesterov extrapolated proximal DCA with backtracking for a composite DC program
• A new boosted proximal point algorithm for minimizing nonsmooth DC functions
• Open issues and recent advances in DC programming and DCA
• Finding robust minimizer for non-convex phase retrieval
• A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging
• Alternating DC algorithm for partial DC programming problems
• An inertial proximal point method for difference of maximal monotone vector fields in Hadamard manifolds
• The descent algorithm for solving the symmetric eigenvalue complementarity problem
• A boosted-DCA with power-sum-DC decomposition for linearly constrained polynomial programs
• A proximal alternating direction method of multipliers for DC programming with structured constraints
• Non-monotone boosted DC and Caputo fractional tailored finite point algorithm for Rician denoising and deblurring
• Title not available (Why is that?)
• Difference-of-Convex Algorithms for a Class of Sparse Group $\ell_0$ Regularized Optimization Problems
• The boosted DC algorithm for linearly constrained DC programming
• Solving \(k\)-center problems involving sets based on optimization techniques

This page was built for publication: The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5221263)