×

zbMATH — the first resource for mathematics

A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes. (English) Zbl 1369.90137
Summary: In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an \(\varepsilon \)-critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.

MSC:
90C26 Nonconvex programming, global optimization
49J52 Nonsmooth analysis
65K05 Numerical mathematical programming methods
Software:
MPBNGC; PBNCGC; QSM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] An, LTH; Ngai, HV; Tao, PD, Exact penalty and error bounds in DC programming, J. Glob. Optim., 52, 509-535, (2012) · Zbl 1242.49037
[2] An, LTH; Tao, PD, Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms, J. Glob. Optim., 11, 253-285, (1997) · Zbl 0905.90131
[3] 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
[4] Astorino, A; Fuduli, A; Gaudioso, M, DC models for spherical separation, J. Glob. Optim., 48, 657-669, (2010) · Zbl 1206.90120
[5] Astorino, A; Fuduli, A; Gaudioso, M, Margin maximization in spherical separation, Comput. Optim. Appl., 53, 301-322, (2012) · Zbl 1258.90066
[6] Bagirov, AM, A method for minimizing of quasidifferentiable functions, Optim. Methods Softw., 17, 31-60, (2002) · Zbl 1040.90038
[7] Bagirov, AM; Ganjehlou, AN, A quasisecant method for minimizing nonsmooth functions, Optim. Methods Softw., 25, 3-18, (2010) · Zbl 1202.65072
[8] Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization: Theory. Practice and Software. Springer, Cham (2014) · Zbl 1312.90053
[9] Bagirov, AM; Ugon, J, Codifferential method for minimizing nonsmooth DC functions, J. Glob. Optim., 50, 3-22, (2011) · Zbl 1242.90172
[10] Bagirov, AM; Yearwood, J, A new nonsmooth optimisation algorithm for minimum sum-of-squares clustering problems, Eur. J. Oper. Res., 170, 578-596, (2006) · Zbl 1085.90045
[11] Bihain, A, Optimization of upper semidifferentiable functions, J. Optim. Theory Appl., 44, 545-568, (1984) · Zbl 0534.90069
[12] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[13] Demyanov, V.F., Rubinov, A.M.: Constructive Nonsmooth Analysis (Approximation and Optimization), vol. 7. Peter Lang, Frankfurt am Main (1995) · Zbl 0887.49014
[14] Ferrer, A, Representation of a polynomial function as a difference of convex polynomials with an application, Lecture Notes in Economics and Mathematical Systems, 502, 189-207, (2001) · Zbl 0986.90037
[15] Ferrer, A; Martnez-Legaz, JE, Improving the efficiency of DC global optimization methods by improving the DC representation of the objective function, J. Glob. Optim., 43, 513-531, (2009) · Zbl 1172.90463
[16] 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
[17] 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
[18] Fuduli, A., Gaudioso, M., Nurminski, E.A.: A splitting bundle approach for non-smooth non-convex minimization. Optimization 64(5), 1131-1151 (2015) · Zbl 1311.90108
[19] Hartman, P, On functions representable as a difference of convex functions, Pac. J. Math., 9, 707-713, (1959) · Zbl 0093.06401
[20] Hiriart-Urruty, JB, Generalized differentiability, duality and optimization for problems dealing with differences of convex functions, Lecture Notes in Economics and Mathematical Systems, 256, 37-70, (1985) · Zbl 0591.90073
[21] Hiriart-Urruty, J.B.: From convex optimization to nonconvex optimization. Part I: Necessary and sufficient conditions for global optimality. Nonsmooth Optimization and Related Topics, Ettore Majorana International Sciences Series 43. Plenum Press (1988) · Zbl 1211.90182
[22] Holmberg, K; Tuy, H, A production-transportation problem with stochastic demand and concave production costs, Math. Prog., 85, 157-179, (1999) · Zbl 0956.90020
[23] Horst, R; Thoai, NV, DC programming: overview, J. Optim. Theory Appl., 103, 1-43, (1999) · Zbl 1073.90537
[24] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 1st edn. Springer, Heilderberg (1990) · Zbl 0704.90057
[25] Hou, L; Sun, W, On the global convergence of a nonmonotone proximal bundle method for convex nonsmooth minimization, Optim. Methods Softw., 23, 227-235, (2008) · Zbl 1211.90294
[26] Kiwiel, KC, An aggregate subgradient method for nonsmooth convex minimization, Math. Prog., 27, 320-341, (1983) · Zbl 0525.90074
[27] Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics, vol. 1133. Springer, Berlin (1985) · Zbl 0561.90059
[28] Kiwiel, KC, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Prog., 46, 105-122, (1990) · Zbl 0697.90060
[29] Kiwiel, KC, Restricted step and Levenberg-Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization, SIAM J. Optim., 6, 227-249, (1996) · Zbl 0846.65028
[30] Lukšan, L, Dual method for solving a special problem of quadratic programming as a subproblem at linearly constrained nonlinear minmax approximation, Kybernetika, 20, 445-457, (1984) · Zbl 0552.90074
[31] Lukšan, L; Spedicato, E, Variable metric methods for unconstrained optimization and nonlinear least squares, J. Comput. Appl. Math., 124, 61-95, (2000) · Zbl 0985.65066
[32] Mäkelä, MM, Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw., 17, 1-29, (2002) · Zbl 1050.90027
[33] Mäkelä, M.M.: Multiobjective proximal bundle method for nonconvex nonsmooth optimization: Fortran subroutine MPBNGC 2.0. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing B 13/2003, University of Jyväskylä, Jyväskylä (2003) · Zbl 1242.49037
[34] Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., Singapore (1992) · Zbl 0757.49017
[35] Pey-Chun, C; Hansen, P; Jaumard, B; Tuy, H, Solution of the multisource Weber and conditional Weber problems by d.c. programming, Oper. Res., 46, 548-562, (1998) · Zbl 0979.90099
[36] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[37] 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
[38] Sun, WY; Sampaio, RJB; Candido, MAB, Proximal point algorithm for minimization of DC functions, J. Comput. Math., 21, 451-462, (2003) · Zbl 1107.90427
[39] Tao, PD; An, LTH, Convex analysis approach to DC programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 289-355, (1997) · Zbl 0895.90152
[40] Toland, J.F.: On subdifferential calculus and duality in nonconvex optimization. Bull. Soc. Math. France, Mémoire 60, 173-180 (1979)
[41] Tuy, H.: Convex Analysis and Global Optimization, 1st edn. Kluwer, 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.