×

Using positive spanning sets to achieve d-stationarity with the boosted DC algorithm. (English) Zbl 1435.65091

Vietnam J. Math. 48, No. 2, 363-376 (2020); correction ibid. 48, No. 2, 377 (2020).
Summary: The Difference of Convex functions Algorithm (DCA) is widely used for minimizing the difference of two convex functions. A recently proposed accelerated version, termed BDCA for Boosted DC Algorithm, incorporates a line search step to achieve a larger decrease of the objective value at each iteration. Thanks to this step, BDCA usually converges much faster than DCA in practice. The solutions found by DCA are guaranteed to be critical points of the problem, but these may not be local minima. Although BDCA tends to improve the objective value of the solutions it finds, these are frequently just critical points as well. In this paper we combine BDCA with a simple Derivative-Free Optimization (DFO) algorithm to force the d-stationarity (lack of descent direction) at the point obtained. The potential of this approach is illustrated through some computational experiments on a Minimum-Sum-of-Squares clustering problem. Our numerical results demonstrate that the new method provides better solutions while still remains faster than DCA in the majority of test cases.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aragón, FJ; Goberna, MA; López, MA; Rodríguez, MML, Nonlinear Optimization. Springer Undergraduate Texts in Mathematics and Technology (2019), Cham: Springer, Cham
[2] Aragón Artacho, FJ; Fleming, RMT; Vuong, PT, Accelerating the DC algorithm for smooth functions, Math. Program., 169, 95-118 (2018) · Zbl 1461.65118
[3] Aragón Artacho, F.J., Vuong, P.T.: The boosted DC algorithm for nonsmooth functions. SIAM J. Optim. (2020). 10.1137/18M123339X (2019) · Zbl 1461.65119
[4] Bagirov, AM; Taheri, S.; Ugon, J., Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems, Pattern Recogn., 53, 12-24 (2016) · Zbl 1412.68200
[5] Gaudioso, M.; Giallombardo, G.; Miglionico, G.; Bagirov, AM, Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations, J. Glob. Optim., 71, 37-55 (2018) · Zbl 1418.90201
[6] Beck, A.; Hallak, N., On the convergence to stationary points of deterministic and randomized feasible descent directions methods, SIAM J. Optim., 30, 56-79 (2020) · Zbl 1434.90148
[7] Conn, AR; Scheinberg, K.; Vicente, LN, Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization, vol. 8 (2009), Philadelphia: SIAM & MPS, Philadelphia
[8] Cuong, T.H., Yao, J.C., Yen, N.D.: Qualitative properties of the minimum sum-of-squares clustering problem. arXiv:1810.02057 (2018)
[9] Le Thi, HA; Pham Dinh, T., DC programming and DCA: Thirty years of developments, Math. Program., 169, 5-68 (2018) · Zbl 1387.90197
[10] Le Thi, HA; Pham Dinh, T., The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46 (2005) · Zbl 1116.90122
[11] Ordin, B.; Bagirov, AM, A heuristic algorithm for solving the minimum sum-of-squares clustering problems, J. Glob. Optim., 61, 341-361 (2015) · Zbl 1311.90111
[12] de Oliveira, W., Proximal bundle methods for nonsmooth DC programming, J. Glob. Optim., 75, 523-563 (2019) · Zbl 1428.90130
[13] de Oliveira, W.; Tcheou, MP, An inertial algorithm for DC programming, Set-Valued Var. Anal., 27, 895-919 (2019) · Zbl 1434.90151
[14] Pham Dinh, T.; Le Thi, HA, Convex analysis approach to DC programming: Theory, algorithms and applications, Acta. Math. Vietnam., 22, 289-355 (1997) · Zbl 0895.90152
[15] Pham Dinh, T., Souad, E.B.: Algorithms for solving a class of nonconvex optimization problems: Methods of subgradients. In: Hiriart-Urruty, J. -B. (ed.) FERMAT Days 85: Mathematics for Optimization. North-Holland Mathematics Studies, vol. 129, pp 249-271. Elsevier, Amsterdam (1986) · Zbl 0638.90087
[16] Toland, JF, On subdifferential calculus and duality in non-convex optimization, Bull. Soc. Math. Fr. Mém., 60, 177-183 (1979) · Zbl 0417.90088
[17] Rockafellar, RT, Convex Analysis (1972), Princeton: Princeton University Press, Princeton
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.