Boosted scaled subgradient method for DC programming

• DOI: 10.48550/arxiv.2103.10757
• Publication Date: 2021-01-01
• Authors: Ferreira, Orizon P.; Santos, Elianders...; Souza, João Carlo...
• Keywords: Optimization and Control (math.OC); 0211 other engineering and technologies; FOS: Mathematics; 65K05, 65K10, 90C26, 47N10; 02 engineering and technology; Mathematics - Optimization and Control

The purpose of this paper is to present a boosted scaled subgradient-type method (BSSM) to minimize the difference of two convex functions (DC functions), where the first function is differentiable and the second one is possibly non-smooth. Although the objective function is in general non-smooth, under mild assumptions, the structure of the problem allows to prove that the negative scaled generalized subgradient at the current iterate is a descent direction from an auxiliary point. Therefore, instead of applying the Armijo linear search and computing the next iterate from the current iterate, both the linear search and the new iterate are computed from that auxiliary point along the direction of the negative scaled generalized subgradient. As a consequence, it is shown that the proposed method has similar asymptotic convergence properties and iteration-complexity bounds as the usual descent methods to minimize differentiable convex functions employing Armijo linear search. Finally, for a suitable scale matrix the quadratic subproblems of BSSM have a closed formula, and hence, the method has a better computational performance than classical DC algorithms which must solve a convex (not necessarily quadratic) subproblem.