×

Sequential difference-of-convex programming. (English) Zbl 1450.90033

Summary: Optimization methods for difference-of-convex programs iteratively solve convex subproblems to define iterates. Although convex, depending on the problem’s structure, these subproblems are very often challenging and require specialized solvers. This work investigates a new methodology that defines iterates as approximate critical points of significantly easier difference-of-convex subproblems approximating the original one. Since there is considerable freedom to choose such more accessible subproblems, several algorithms can be designed from the given approach. In some cases, the resulting algorithm boils down to a straightforward process with iterates given in an analytic form. In other situations, decomposable subproblems can be chosen, opening the way for parallel computing even when the original program is not decomposable. Depending on the problem’s assumptions, a possible variant of the given approach is the Josephy-Newton method applied to the system of (necessary) optimality conditions of the original difference-of-convex program. In such a setting, local convergence with superlinear and even quadratic rates can be achieved under certain conditions.

MSC:

90C26 Nonconvex programming, global optimization
49J52 Nonsmooth analysis
49J53 Set-valued and variational analysis
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Toland, JF, Duality in nonconvex optimization, J. Math. Anal. Appl., 66, 2, 399-415 (1978) · Zbl 0403.90066
[2] Hiriart-Urruty, J.B.: Generalized differentiability / duality and optimization for problems dealing with differences of convex functions. In: Ponstein, J. (ed.) Convexity and Duality in Optimization: Proceedings of the Symposium on Convexity and Duality in Optimization Held at the University of Groningen, The Netherlands June 22, 1984, pp. 37-70. Springer Berlin Heidelberg (1985)
[3] Bomze, IM; Lemaréchal, C., Necessary conditions for local optimality in difference-of-convex programming, J. Convex Anal., 17, 2, 673-680 (2010) · Zbl 1201.90199
[4] Bagirov, AM; Yearwood, J., A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, Eur. J. Oper. Res., 170, 2, 578-596 (2006) · Zbl 1085.90045
[5] Khalaf, W.; Astorino, A.; d’Alessandro, P.; Gaudioso, M., A DC optimization-based clustering technique for edge detection, Optim. Lett., 11, 3, 627-640 (2017) · Zbl 1366.90170
[6] Astorino, A.; Miglionico, G., Optimizing sensor cover energy via DC programming, Optim. Lett., 10, 2, 355-368 (2016) · Zbl 1343.90064
[7] Le Thi, HA; Le, HM; Nguyen, VV; Pham Dinh, T., A DC programming approach for feature selection in support vector machines learning, Adv. Data Anal. Classif., 2, 3, 259-278 (2008) · Zbl 1284.90057
[8] Le Thi, HA; Le, HM; Pham Dinh, T.; Van Huynh, N., Binary classification via spherical separator by DC programming and DCA, J. Global Optim., 56, 4, 1393-1407 (2013) · Zbl 1275.90093
[9] Gaudioso, M.; Giallombardo, G.; Miglionico, G.; Vocaturo, E., Classification in the multiple instance learning framework via spherical separation, Soft. Comput., 24, 7, 5071-5077 (2020)
[10] Astorino, A.; Fuduli, A.; Giallombardo, G.; Miglionico, G., SVM-based multiple instance classification via DC optimization, Algorithms, 12, 12, 249 (2019)
[11] Rakotomamonjy, A.; Flamary, R.; Gasso, G., DC proximal Newton for nonconvex optimization problems, IEEE Trans. Neural Netw. Learn. Syst., 27, 3, 636-647 (2016)
[12] Li, X.; Yang, L.; Ge, J.; Haupt, J.; Zhang, T.; Zhao, T., On quadratic convergence of DC proximal Newton algorithm in nonconvex sparse learning, Adv. Neural Inf. Process. Syst., 1, 2743-2753 (2017)
[13] de Oliveira, W.; Tcheou, MP, An inertial algorithm for DC programming, Set-Valued Var. Anal., 27, 4, 895-919 (2019) · Zbl 1434.90151
[14] Tuy, H., Convex Analysis and Global Optimization, Nonconvex Optimization and Its Applications (2016), Berlin: Springer, Berlin · Zbl 1362.90001
[15] Gaudioso, M.; Giallombardo, G.; Miglionico, G., Minimizing piecewise-concave functions over polyhedra, Math. Oper. Res., 43, 2, 580-597 (2018) · Zbl 1440.90089
[16] An, LTH; Tao, PD, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 1, 23-46 (2005) · Zbl 1116.90122
[17] Le Thi, HA; Tao, PD, DC programming and DCA: thirty years of developments, Math. Program., 169, 1, 5-68 (2018) · Zbl 1387.90197
[18] Tao, PD; Le Thi, HA, Convex analysis approach to DC programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 1, 289-355 (1997) · Zbl 0895.90152
[19] Joki, K.; Bagirov, AM; Karmitsa, N.; Mäkelä, MM, A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes, J. Global Optim., 68, 3, 501-535 (2017) · Zbl 1369.90137
[20] Joki, K.; Bagirov, AM; Karmitsa, N.; Mäkelä, MM; Taheri, S., Double bundle method for finding Clarke stationary points in nonsmooth DC programming, SIAM J. Optim., 28, 2, 1892-1919 (2018) · Zbl 1401.90170
[21] Montonen, O.; Joki, K., Bundle-based descent method for nonsmooth multiobjective DC optimization with inequality constraints, J. Global Optim., 72, 3, 403-429 (2018) · Zbl 1414.90317
[22] Gaudioso, M.; Giallombardo, G.; Miglionico, G.; Bagirov, AM, Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations, J. Global Optim., 71, 1, 37-55 (2018) · Zbl 1418.90201
[23] de Oliveira, W., Proximal bundle methods for nonsmooth DC programming, J. Global Optim., 75, 2, 523-563 (2019) · Zbl 1428.90130
[24] Izmailov, AF; Solodov, MV, Newton-type methods: a broader view, J. Optim. Theory Appl., 164, 2, 577-620 (2015) · Zbl 1310.65063
[25] van Ackooij, W.; de Oliveira, W., Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions, J. Optim. Theory Appl., 182, 1, 49-80 (2019) · Zbl 1420.49016
[26] Pang, JS; Razaviyayn, M.; Alvarado, A., Computing B-stationary points of nonsmooth DC programs, Math. Oper. Res., 42, 1, 95-118 (2017) · Zbl 1359.90106
[27] Aragón Artacho, FJ; Campoy, R.; Vuong, PT, Using positive spanning sets to achieve d-stationarity with the boosted dc algorithm, Vietnam J. Math (2020) · Zbl 1435.65091
[28] Souza, JCO; Oliveira, PR; Soubeyran, A., Global convergence of a proximal linearized algorithm for difference of convex functions, Optim. Lett., 10, 7, 1529-1539 (2016) · Zbl 1355.90073
[29] Clarke, F., Optimisation and nonsmooth analysis. Classics in applied mathematics, Soc. Ind. Appl. Math. (1990)
[30] Artacho, FJA; Fleming, RMT; Vuong, PT, Accelerating the DC algorithm for smooth functions, Math. Program., 169, 1, 95-118 (2018) · Zbl 1461.65118
[31] Hiriart-Urruty, J.; Lemaréchal, C., Convex Analysis and Minimization Algorithms II (1996), Berlin: Springer, Berlin
[32] Izmailov, AF; Solodov, MV, Newton-Type Methods for Optimization and Variational Problems (2014), Berlin: Springer, Berlin
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.