INEXACT BOOSTED DIFFERENCE OF CONVEX ALGORITHM
Main Article Content
Abstract
In this paper, we propose the Inexact Difference of Convex Algorithm (iBDCA), an inexact variant of the Boosted Difference of Convex Functions Algorithm (BDCA), to solve an optimization problem involving the difference of two strongly convex functions, where both components of the DC function are assumed to be differentiable, and the gradient of the first component is Lipschitz continuous. The proposed algorithm consists of two main steps: first, we employ a gradient descent-based scheme to find an approximate solution to a subproblem associated with the convex component of the DC problem; second, this approximate point is then used to compute a suitable step size for the next iteration. We establish the convergence and convergence rates of the iterate and objective-value sequences to the optimal solution and optimal value, respectively, as well as the complexity of the subproblem.
Keywords
boosted difference of convex functions algorithm, convergence analysis, DC functions, inexact gradient descent methods, line search, step size
Article Details
References
Aragón-Artacho, F. J., Campoy, R., & Vuong, P. T. (2022). The boosted DC algorithm for linearly constrained DC programming. Set-Valued and Variational Analysis, 30(4), 1265-1289. https://doi.org/10.1007/s11228-022-00656-x
Aragón-Artacho, F. J., Fleming, R. M., & Vuong, P. T. (2018). Accelerating the DC algorithm for smooth functions. Mathematical programming, 169, 95-118. https://doi.org/10.1007/s10107-017-1180-1
Aragón-Artacho, F. J., Mordukhovich, B. S., & Pérez-Aros, P. (2024). Coderivative-based semi-Newton method in nonsmooth difference programming. Mathematical Programming, 1-48. https://doi.org/10.1007/s10107-024-02142-8
Fukushima, M., & Mine, H. (1981). A generalized proximal point algorithm for certain non-convex minimization problems. International Journal of Systems Science, 12(8), 989-1000. https://doi.org/10.1080/00207728108963798
Izmailov, A. F., & Solodov, M. V. (2014). Newton-type methods for optimization and variational problems . Springer, 1. https://doi.org/10.1007/978-3-319-04247-3
Khanh, P. D., Mordukhovich, B. S., & Tran, D. B. (2024). A new inexact gradient descent method with applications to nonsmooth convex optimization. Optimization Methods and Software,
1-29. https://doi.org/10.1080/10556788.2024.2322700
Lojasiewicz, S. (1965). Ensembles semi-analytiques. Lectures Notes IHES (Bures-sur-Yvette).
Tao. (1986). Algorithms for solving a class of nonconvex optimization problems. Methods of subgradients. North-Holland Mathematics Studies, 129, 249-271. https://doi.org/10.1016/S0304-0208(08)72402-2
Tao, P. D., & An, L. T. (1997). Convex analysis approach to DC programming: theory, algorithms and applications. Acta mathematica vietnamica, 22(1), 289-355.
Yin, P., Lou, Y., He, Q., & Xin, J. (2015). Minimization of 1-2 for compressed sensing. SIAM Journal on Scientific Computing, 37(1), A536-A563. https://doi.org/10.1137/140952363