×

Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions. (English) Zbl 1420.49016

Authors’ abstract: We propose an optimization technique for computing stationary points of a broad class of nonsmooth and nonconvex programming problems. The proposed approach (approximately) decomposes the objective function as the difference of two convex functions and performs inexact optimization of the resulting (convex) subproblems. We prove global convergence of our method in the sense that, for an arbitrary starting point, every accumulation point of the sequence of iterates is a Clarke-stationary solution. The given approach is validated by encouraging numerical results on several nonsmooth and nonconvex distributionally robust optimization problems.

MSC:

49J52 Nonsmooth analysis
49J53 Set-valued and variational analysis
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming

Software:

GRANSO; PNEW
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Hartman, P., On functions representable as a difference of convex functions, Pac. J. Math., 9, 167-198, (1959) · Zbl 0093.06401
[2] Rockafellar, R., Wets, R.J.B.: Variational Analysis, Grundlehren der mathematischen Wissenschaften, vol. 317, 3rd edn. Springer, Berlin (2009)
[3] Pflug, GC; Pohl, M., A review on ambiguity in stochastic portfolio optimization, Set Valued Var. Anal., (2017) · Zbl 1416.90026
[4] Esfahani, PM; Kuhn, D., Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations, Math. Program., 171, 115-166, (2018) · Zbl 1433.90095
[5] Curtis, FE; Mitchell, T.; Overton, ML, A BFGS-SQP method for nonsmooth, nonconvex, constrained optimization and its evaluation using relative minimization profiles, Optim. Methods Softw., 32, 148-181, (2017) · Zbl 1364.90359
[6] Ginchev, I.; Gintcheva, D., Characterization and recognition of D.C. functions, J. Glob. Optim., 57, 633-647, (2012) · Zbl 1284.26014
[7] Toa, PD; Souad, EB; Hoffmann, KH (ed.); Zowe, J. (ed.); Hiriart-Urruty, J. (ed.); Lemarechal, C. (ed.), Duality in D.C. (difference of convex functions) optimization. Subgradient methods, No. 84, 277-293, (1988), Basel
[8] de Oliveira, W., Tcheou, M.: An inertial algorithm for DC programming. Set Valued Var. Anal. (2018). https://doi.org/10.1007/s11228-018-0497-0
[9] Toa, PD, Exact penalty in D.C. programming, Vietnam J. Math., 27, 169-178, (1999)
[10] Tao, PD; Thi, HA, Convex analysis approach to DC programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 289-355, (1997) · Zbl 0895.90152
[11] Pang, JS; Razaviyayn, M.; Alvarado, A., Computing B-stationary points of nonsmooth DC programs, Math. Oper. Res., 42, 95-118, (2017) · Zbl 1359.90106
[12] Strekalovsky, AS, On local search in D.C. optimization problems, Appl. Math. Comput., 255, 73-83, (2015) · Zbl 1338.90327
[13] Strekalovsky, AS; Minarchenko, IM, A local search method for optimisation problem with D.C. inequality constraints, Appl. Math. Model., 1, 229-244, (2018)
[14] Joki, K.; Bagirov, AM; Karmitsa, N.; Mäkelä, MM, A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes, J. Glob. Optim., 68, 501-535, (2017) · Zbl 1369.90137
[15] 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
[16] Oliveira, W., Proximal bundle methods for nonsmooth DC programming, J. Glob. Optim., (2019)
[17] Thi, HA; Tao, PD, DC programming in communication systems: challenging problems and methods, Vietnam J. Comput. Sci., 1, 15-28, (2014)
[18] Hare, W.; Sagastizábal, C., Computing proximal points of nonconvex functions, Math. Program., 116, 221-258, (2009) · Zbl 1168.90010
[19] Hare, W.; Sagastizábal, C., A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20, 2442-2473, (2010) · Zbl 1211.90183
[20] Hare, W.; Sagastizábal, C.; Solodov, M., A proximal bundle method for nonconvex functions with inexact oracles, Comput. Optim. Appl., 63, 1-28, (2016) · Zbl 1343.90069
[21] Karmitsa, N.; Gaudioso, M.; Joki, K., Diagonal bundle method with convex and concave updates for large-scale nonconvex and nonsmooth optimization, Optim. Methods Softw., (2017) · Zbl 1407.65063
[22] Dao, MN; Gwinner, J.; Noll, D.; Ovcharova, N., Nonconvex bundle method with application to a delamination problem, Comput. Optim. Appl., 65, 173-203, (2016) · Zbl 1353.90157
[23] Fuduli, A.; Gaudioso, M.; Giallombardo, G., Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim., 14, 743-756, (2004) · Zbl 1079.90105
[24] Fuduli, A.; Gaudioso, M.; Giallombardo, G., A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optim. Methods Softw., 19, 89-102, (2004) · Zbl 1211.90182
[25] Haarala, N.; Miettinen, K.; Mäkelä, MM, Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Math. Program., 109, 181-205, (2007) · Zbl 1278.90451
[26] Kiwiel, KC, A linearization algorithm for nonsmooth minimization, Math. Oper. Res., 10, 185-194, (1985) · Zbl 0565.90063
[27] Kiwiel, K., Restricted step and Levenberg-Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization, SIAM J. Optim., 6, 227-249, (1996) · Zbl 0846.65028
[28] Lukšan, L.; Vlček, J., A bundle-newton method for nonsmooth unconstrained minimization, Math. Program., 83, 373-391, (1998) · Zbl 0920.90132
[29] Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., River Edge (1992) · Zbl 0757.49017
[30] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2, 121-152, (1992) · Zbl 0761.90090
[31] Vlček, J.; Lukšan, L., Globally convergent variable metric method for nonconvex nondifferentiable unconstrained optimization, J. Optim. Theory Appl., 111, 407-430, (2001) · Zbl 1029.90060
[32] Mifflin, R., A modification and extension of Lemaréchal’s algorithm for nonsmooth optimization, Math. Program. Study, 17, 77-90, (1982) · Zbl 0476.65047
[33] Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New variants of bundle methods, Math. Program., 69, 111-147, (1995) · Zbl 0857.90102
[34] Ackooij, W.; Oliveira, W., Level bundle methods for constrained convex optimization with various oracles, Comput. Optim. Appl., 57, 555-597, (2014) · Zbl 1329.90109
[35] Noll, D.; Bailey, DH (ed.); Bauschke, HH (ed.); Borwein, P. (ed.); Garvan, F. (ed.); Théra, M. (ed.); Vanderwerff, J. (ed.); Wolkowicz, H. (ed.), Bundle method for non-convex minimization with inexact subgradients and function values, No. 50, 555-592, (2013), Berlin
[36] Luc, DT; Ngai, H.; Théra, M.; Ioffe, A. (ed.); Reich, S. (ed.); Shafrir, I. (ed.), On \(\epsilon \)-monotonicity and \(\epsilon \)-convexity, No. 410, 82-100, (2000), London
[37] Daniildis, A.; Georgiev, P., Approximate convexity and submonotonicity, J. Math. Anal. Appl., 291, 117-144, (2004)
[38] Apkarian, P.; Noll, D.; Prot, O., A proximity control algorithm to minimize nonsmooth and nonconvex semi-infinite maximum eigenvalue functions, J. Convex Anal., 16, 641-666, (2009) · Zbl 1182.49012
[39] Clarke, F., Optimisation and nonsmooth analysis. Classics in applied mathematics, Soc. Ind. Appl. Math., (1987)
[40] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I. Basic Theory. Grundlehren der mathematischen Wissenschaften, vol. 330. Springer, Heidelberg (2006)
[41] Borwein, JM; Preiss, D., A smooth variational principle with applications to subdifferentiability and differentiability of convex functions, Trans. Am. Math. Soc., 303, 517-527, (1987) · Zbl 0632.49008
[42] Borwein, J.M., Zhu, Q.J.: Techniques of Variational Analysis, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 20. Springer, New York (2005)
[43] Kruger, AY, On Fréchet subdifferentials, J. Math. Sci., 116, 3325-3358, (2003) · Zbl 1039.49021
[44] Kelley, JE, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 703-712, (1960) · Zbl 0098.12104
[45] Frangioni, A.: Standard Bundle Methods: Untrusted Models and Duality. Technical Report del Dipartimento di Informatica, TR. University of Pisa, Pisa, IT (submitted)
[46] Oliveira, W., Target radius methods for nonsmooth convex optimization, Oper. Res. Lett., 45, 659-664, (2017) · Zbl 1409.90139
[47] Bello-Cruz, JY; Oliveira, W., Level bundle-like algorithms for convex optimization, J. Glob. Optim., 59, 787-809, (2014) · Zbl 1330.90073
[48] Ferrier, C.: Bornes duales de problèmes d’optimisation polynomiaux. Ph.D. thesis, Université Paul Sabatier, Toulouse (1997)
[49] Ferrier, C., Computation of the distance to semi-algebraic sets, ESAIM Control Optim. Calc. Var., 5, 139-156, (2000) · Zbl 1054.14534
[50] Beltran, F.; Oliveira, W.; Finardi, EC, Application of scenario tree reduction via quadratic process to medium-term hydrothermal scheduling problem, IEEE Trans. Power Syst., 32, 4351-4361, (2017)
[51] Trivedi, PK; Zimmer, DM, Copula modeling: an introduction for practitioners, Found. Trends Econ., 1, 1-111, (2007) · Zbl 1195.91130
[52] Nelsen, R.B.: An Introduction to Copulas. Springer Series in Statistics, 2nd edn. Springer, New York (2006) · Zbl 1152.62030
[53] McNeil, A.; Nešlehová, J., Multivariate archimedian copulas, d-monotone functions and \(l_1\) norm symmetric distributions, Ann. Stat., 37, 3059-3097, (2009) · Zbl 1173.62044
[54] Ackooij, W.; Oliveira, W., Convexity and optimization with copulæ structured probabilistic constraints, Optim. J. Math. Program. Oper. Res., 65, 1349-1376, (2016) · Zbl 1345.49042
[55] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
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.