×

Proximal bundle methods for nonsmooth DC programming. (English) Zbl 1428.90130

Summary: We consider the problem of minimizing the difference of two nonsmooth convex functions over a simple convex set. To deal with this class of nonsmooth and nonconvex optimization problems, we propose new proximal bundle algorithms and show that the given approaches generate subsequences of iterates that converge to critical points. Trial points are obtained by solving strictly convex master programs defined by the sum of a convex cutting-plane model and a freely-chosen Bregman function. In the unconstrained case with the Bregman function being the Euclidean distance, new iterates are solutions of strictly convex quadratic programs of limited sizes. Stronger convergence results \((d\)-stationarity) can be achieved depending on (a) further assumptions on the second DC component of the objective function and (b) solving possibly more than one master program at certain iterations. The given approaches are validated by encouraging numerical results on some academic DC programs.

MSC:

90C26 Nonconvex programming, global optimization

Software:

SQPlab; PLCP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Astorino, A., Miglionico, G.: Optimizing sensor cover energy via DC programming. Optim. Lett. 10(2), 355-368 (2016) · Zbl 1343.90064
[2] Bagirov, A.M.: A method for minimization of quasidifferentiable functions. Optim. Methods Softw. 17(1), 31-60 (2002) · Zbl 1040.90038
[3] Bagirov, A.M., 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
[4] Ben-Tal, A., Nemirovski, A.: Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Program. 102, 407-456 (2005) · Zbl 1066.90079
[5] Bonnans, J., Gilbert, J., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006) · Zbl 1108.65060
[6] Clarke, F.H.: Optimisation and nonsmooth analysis. Soc. Ind. Appl. Math. (1990). https://doi.org/10.1137/1.9781611971309 · Zbl 0696.49002
[7] Cruz Neto, J.X., Oliveira, P.R., Soubeyran, A., Souza, J.C.O.: A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem. Ann. Oper. Res. (2018). https://doi.org/10.1007/s10479-018-3104-8 · Zbl 1496.90065
[8] de Oliveira, W., Solodov, M.: A doubly stabilized bundle method for nonsmooth convex optimization. Math. Program. 156(1), 125-159 (2016) · Zbl 1346.90675
[9] de Oliveira, W.: Target radius methods for nonsmooth convex optimization. Oper. Res. Lett. 45(6), 659-664 (2017) · Zbl 1409.90139
[10] de Oliveira, W., Sagastizábal, C., Lemaréchal, C.: Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Math. Program. Ser. B 148, 241-277 (2014) · Zbl 1327.90321
[11] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002) · Zbl 1049.90004
[12] Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13(1), 117-156 (2002) · Zbl 1041.90037
[13] Frangioni, A., Gorgone, E.: Generalized bundle methods for sum-functions with “easy” components: applications to multicommodity network design. Math. Program. 145(1), 133-161 (2014) · Zbl 1300.90027
[14] Fuduli, A., Gaudioso, M., Giallombardo, G.: A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization. Optim. Methods Softw. 19(1), 89-102 (2004) · Zbl 1211.90182
[15] Gaudioso, M., Giallombardo, G., Miglionico, G.: Minimizing piecewise-concave functions over polyhedra. Math. Oper. Res. 43(2), 580-597 (2018) · Zbl 1418.90201
[16] Gaudioso, M., Giallombardo, G., Miglionico, G., Bagirov, A.M.: Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations. J. Glob. Optim. 71(1), 37-55 (2018) · Zbl 1418.90201
[17] Hare, W., Sagastizábal, C.: A redistributed proximal bundle method for nonconvex optimization. SIAM J. Optim. 20(5), 2442-2473 (2010) · Zbl 1211.90183
[18] Hare, W., Sagastizábal, C., Solodov, M.: A proximal bundle method for nonsmooth nonconvex functions with inexact information. Comput. Optim. Appl. 63(1), 1-28 (2016) · Zbl 1343.90069
[19] Henrion, R.: A Critical Note on Empirical (Sample Average, Monte Carlo) Approximation of Solutions to Chance Constrained Programs (Chapter 3 in [24]). Springer, Berlin (2013) · Zbl 1267.90086
[20] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Grundlehren der mathematischen Wissenschaften, vol. 305, 2nd edn. Springer, Berlin (1996) · Zbl 0795.49001
[21] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms II. Grundlehren der mathematischen Wissenschaften, vol. 306, 2nd edn. Springer, Berlin (1996) · Zbl 0795.49002
[22] Hiriart-Urruty, J.B.: Generalized Differentiability/Duality and Optimization for Problems Dealing with Differences of Convex Functions, pp. 37-70. Springer, Berlin, Heidelberg (1985) · Zbl 0591.90073
[23] Holmberg, K., Tuy, H.: A production – transportation problem with stochastic demand and concave production costs. Math. Program. 85(1), 157-179 (1999) · Zbl 0956.90020
[24] Hömberg, D., Tröltzsch, F. (eds.): System Modeling and Optimization. IFIP Advances in Information and Communication, vol. 391. Springer, Berlin (2013) · Zbl 1262.00009
[25] Hong, L.J., Yang, Y., Zhang, L.: Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach. Oper. Res. 59(3), 617-630 (2011) · Zbl 1231.90303
[26] Joki, K., Bagirov, A., Karmitsa, N., Mäkelä, M.M., 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
[27] Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes. J. Glob. Optim. 68(3), 501-535 (2017) · Zbl 1369.90137
[28] Kelley, J.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703-712 (1960) · Zbl 0098.12104
[29] 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
[30] Kiwiel, K.C.: A proximal bundle method with approximate subgradient linearizations. SIAM J. Optim. 16(4), 1007-1023 (2006) · Zbl 1104.65055
[31] Le Thi, H.A., Tao, P.D.: DC programming in communication systems: challenging problems and methods. Vietnam J. Comput. Sci. 1(1), 15-28 (2014)
[32] Le Thi, H.A., Pham Dinh, T., Ngai, H.V.: Exact penalty and error bounds in DC programming. J. Glob. Optim. 52(3), 509-535 (2012) · Zbl 1242.49037
[33] Lemaréchal, C.: An algorithm for minimizing convex functions. Inf. Process. 1, 552-556 (1974) · Zbl 0297.65041
[34] Lemaréchal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69(1), 111-147 (1995) · Zbl 0857.90102
[35] Lewis, A.S., Overton, M.L.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141(1), 135-163 (2013) · Zbl 1280.90118
[36] Mäkelä, M.M., Miettinen, M., Lukšan, L., Vlček, J.: Comparing nonsmooth nonconvex bundle methods in solving hemivariational inequalities. J. Glob. Optim. 14(2), 117-135 (1999) · Zbl 0947.90125
[37] Noll, D., Apkarian, P.: Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods. Math. Program. 104(2), 701-727 (2005) · Zbl 1124.90034
[38] Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. 42(1), 95-118 (2017) · Zbl 1359.90106
[39] Prékopa, A.: Stochastic Programming. Kluwer, Dordrecht (1995) · Zbl 0863.90116
[40] Rockafellar, R.: Convex Analysis, 1st edn. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[41] Souza, J.C.O., Oliveira, P.R., Soubeyran, A.: Global convergence of a proximal linearized algorithm for difference of convex functions. Optim. Lett. 10(7), 1529-1539 (2016) · Zbl 1355.90073
[42] Tao, P.D., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289-355 (1997) · Zbl 0895.90152
[43] Tuy, H.: Convex Analysis and Global Optimization. Springer Optimization and Its Applications, 2nd edn. Springer, Berlin (2016) · Zbl 1362.90001
[44] van Ackooij, W.: Eventual convexity of chance constrained feasible sets. Optimization 64(5), 1263-1284 (2015) · Zbl 1321.49042
[45] van Ackooij, W., Cruz, J.B., de Oliveira, W.: A strongly convergent proximal bundle method for convex minimization in Hilbert spaces. Optimization 65(1), 145-167 (2016) · Zbl 1334.49101
[46] van Ackooij, W., Henrion, R.: Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions. SIAM J. Optim. 24(4), 1864-1889 (2014) · Zbl 1319.93080
[47] van Ackooij, W., de Oliveira, W.: Level bundle methods for constrained convex optimization with various oracles. Comput. Optim. Appl. 57(3), 555-597 (2014) · Zbl 1329.90109
[48] van Ackooij, W., Sagastizábal, C.: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J. Optim. 24(2), 733-765 (2014) · Zbl 1297.49057
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.