×

zbMATH — the first resource for mathematics

Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations. (English) Zbl 1418.90201
Summary: We introduce a proximal bundle method for the numerical minimization of a nonsmooth difference-of-convex (DC) function. Exploiting some classic ideas coming from cutting-plane approaches for the convex case, we iteratively build two separate piecewise-affine approximations of the component functions, grouping the corresponding information in two separate bundles. In the bundle of the first component, only information related to points close to the current iterate are maintained, while the second bundle only refers to a global model of the corresponding component function. We combine the two convex piecewise-affine approximations, and generate a DC piecewise-affine model, which can also be seen as the pointwise maximum of several concave piecewise-affine functions. Such a nonconvex model is locally approximated by means of an auxiliary quadratic program, whose solution is used to certify approximate criticality or to generate a descent search-direction, along with a predicted reduction, that is next explored in a line-search setting. To improve the approximation properties at points that are far from the current iterate a supplementary quadratic program is also introduced to generate an alternative more promising search-direction. We discuss the main convergence issues of the line-search based proximal bundle method, and provide computational results on a set of academic benchmark test problems.

MSC:
90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] An, LTH; Tao, PD, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, J. Glob. Optim., 133, 23-46, (2005) · Zbl 1116.90122
[2] Astorino, A; Fuduli, A; Gaudioso, M, DC models for spherical separation, J. Glob. Optim., 48, 657-669, (2010) · Zbl 1206.90120
[3] Bagirov, AM, A method for minimization of quasidifferentiable functions, Optim. Methods Softw., 17, 31-60, (2002) · Zbl 1040.90038
[4] Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization: Theory, Practice and Software. Springer, Berlin (2014) · Zbl 1312.90053
[5] Bagirov, AM; Taheri, S; Ugon, J, Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems, Pattern Recognit., 53, 12-24, (2016) · Zbl 1412.68200
[6] Bagirov, AM; Ugon, J, Codifferential method for minimizing nonsmooth DC functions, J. Glob. Optim., 50, 3-22, (2011) · Zbl 1242.90172
[7] Bagirov, A.M., Ugon, J.: Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms. Optim. Methods Softw. (in press). doi:10.1080/10556788.2017.1371717 · Zbl 1317.90242
[8] Demyanov, AV; Fuduli, A; Miglionico, G, A bundle modification strategy for convex minimization, Eur. J. Oper. Res., 180, 38-47, (2007) · Zbl 1114.90090
[9] Demyanov, V.F., Malozemov, V.N.: On the theory of non-linear minimax problems. Russ. Math. Surv. 26(3) (1971). http://iopscience.iop.org/0036-0279/26/3/R02 · Zbl 1079.90105
[10] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[11] 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
[12] Fuduli, A; Gaudioso, M; Giallombardo, G; Miglionico, G, A partially inexact bundle method for convex semi-infinite minmax problems, Commun. Nonlinear Sci. Numer. Simul., 21, 172-180, (2014) · Zbl 1338.90451
[13] Gaudioso, M., Giallombardo, G., Miglionico, G.: Minimizing piecewise-concave functions over polytopes. Math. Op. Res. (in press). doi:10.1287/moor.2017.0873 · Zbl 1418.90201
[14] Gaudioso, M; Gorgone, E, Gradient set splitting in nonconvex nonsmooth numerical optimization, Optim. Methods Softw., 25, 59-74, (2010) · Zbl 1190.90140
[15] Gaudioso, M; Monaco, MF, Variants to the cutting plane approach for convex nondifferentiable optimization, Optimization, 25, 65-75, (1992) · Zbl 0817.90076
[16] Hiriart-Urruty, J.B.: From Convex Optimization to Nonconvex Optimization: Necessary and Sufficient Conditions for Global Optimality, in Nonsmooth Optimization and Related Topics, pp. 219-240. Plenum, New York/London (1989) · Zbl 0735.90056
[17] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I-II. Springer, Berlin (1993) · Zbl 0795.49002
[18] Holmberg, K; Tuy, H, A production-transportation problem with stochastic demand and concave production costs, Math. Program., 85, 157-179, (1999) · Zbl 0956.90020
[19] Horst, R; Thoai, NV, DC programming: overview, J. Optim. Theory Appl., 103, 1-43, (1999) · Zbl 1073.90537
[20] Ibm Ilog Cplex Optimizer: http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/ · Zbl 0908.90243
[21] Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes. J. Global Optim. 68(3), 501-535 (2017). doi:10.1007/s10898-016-0488-3 · Zbl 1369.90137
[22] 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
[23] Pey-Chun, C; Hansen, P; Jaumard, B; Tuy, H, Solution of the multisource Weber and conditional Weber problems by DC programming, Oper. Res., 46, 548-562, (1998) · Zbl 0979.90099
[24] Souza, JCO; Oliveira, PR; Soubeyran, A, Global convergence of a proximal linearized algorithm for difference of convex functions, Optim. Lett., 10, 1529-1539, (2016) · Zbl 1355.90073
[25] Strekalovsky, A.S.: On Global Optimality Conditions for D.C. Programming Problems. Irkutsk State University, Russia (1997)
[26] Strekalovsky, AS, Global optimality conditions for nonconvex optimization, J. Glob. Optim., 12, 415-434, (1998) · Zbl 0908.90243
[27] Tuy, H.: Convex Analysis and Global Optimization. Kluwer Academic Publishers, Dordrescht (1998) · Zbl 0904.90156
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.