×

zbMATH — the first resource for mathematics

DC programming and DCA for general DC programs. (English) Zbl 1322.90072
Do, Tien Van (ed.) et al., Advanced computational methods for knowledge engineering. Proceedings of the 2nd international conference on computer science, applied mathematics and applications, ICCSAMA 2014, Budapest, Hungary, May 8–9, 2014. Cham: Springer (ISBN 978-3-319-06568-7/pbk; 978-3-319-06569-4/ebook). Advances in Intelligent Systems and Computing 282, 15-35 (2014).
Summary: We present a natural extension of DC programming and DCA for modeling and solving general DC programs with DC constraints. Two resulting approaches consist in reformulating those programs as standard DC programs in order to use standard DCAs for their solutions. The first one is based on penalty techniques in DC programming, while the second linearizes concave functions in DC constraints to build convex inner approximations of the feasible set. They are proved to converge to KKT points of general DC programs under usual constraints qualifications. Both designed algorithms can be viewed as a sequence of standard DCAs with updated penalty (resp. relaxation) parameters.
For the entire collection see [Zbl 1294.68017].

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] DC Programming and DCA, http://lita.sciences.univ-metz.fr/ lethi/DCA.html · Zbl 1322.90072
[2] Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to DC programming: Theory, Algorithms and Applications. Acta Mathematica Vietnamica 22(1), 289-355 (1997) · Zbl 0895.90152
[3] Pham Dinh, T., Le Thi, H.A.: A DC Optimization algorithm for solving the trust region subproblem. SIAM J. Optim. 8(2), 476-505 (1998) · Zbl 0913.65054
[4] Le Thi, H.A., Pham Dinh, T.: Solving a class of linearly constrained indefinite quadratic problems by DC Algorithms. Journal of Global Optimization 11, 253-285 (1997) · Zbl 0905.90131
[5] Le Thi, H.A., Pham Dinh, T.: DC Programming: Theory, Algorithms and Applications. The State of the Art (28 pages). In: Proceedings of the First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos 2002), Valbonne-Sophia Antipolis, France, October 2-4 (2002)
[6] Le Thi, H.A., Pham Dinh, T., Le, D.M.: Exact penalty in DC programming. Vietnam Journal of Mathematics 27(2), 169-178 (1999) · Zbl 1006.90062
[7] Le Thi, H.A.: An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints. Mathematical Programming, Ser. A 87(3), 401-426 (2000) · Zbl 0952.90031
[8] Le Thi, H.A., Pham Dinh, T.: Large scale global molecular optimization from distance matrices by a DC optimization appoach. SIAM J. Optim. 14(1), 77-116 (2003) · Zbl 1075.90071
[9] Le Thi, H.A., Huynh, V.N., Pham Dinh, T.: DC Programming and DCA for solving general DC programs, Research Report, National Institute for Applied Sciences (2004) · Zbl 1322.90072
[10] Le Thi, H.A., Pham Dinh, T.: The DC (Difference of Convex functions) Programming and DCA revisited with DC models of real-world nonconvex optimization problems. Annals of Operations Research 133, 23-48 (2005) · Zbl 1116.90122
[11] Le Thi, H.A., Nguyen, T.P., Pham Dinh, T.: A continuous approach for solving the concave cost supply problem by combining DCA and B&B techniques. European Journal of Operational Research 183, 1001-1012 (2007) · Zbl 1135.90036
[12] Le Thi, H.A., Pham Dinh, T.: A continuous approach for the concave cost supply problem via DC Programming and DCA. Discrete Applied Mathematics 156, 325-338 (2008) · Zbl 1190.90142
[13] Pham Dinh, T., Nguyen, C.N., Le Thi, H.A.: An efficient combination of DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs. Journal of Global Optimization 48(4), 595-632 (2010) · Zbl 1226.90060
[14] Thiao, M., Pham Dinh, T., Le Thi, H.A.: A DC programming approach for Sparse Eigenvalue Problem. In: ICML 2010, pp. 1063-1070 (2010)
[15] Le Thi, H.A., Huynh, V.N., Pham Dinh, T.: Convergence Analysis of DC Algorithms for DC programming with subanalytic data, Research Report, National Institute for Applied Sciences, Rouen, France (2009)
[16] Thiao, M., Pham Dinh, T., Le Thi, H.A.: A DC programming approach for Sparse Eigenvalue Problem, Research Report, National Institute for Applied Sciences, Rouen, France (2011) · Zbl 1160.90626
[17] Le Thi, H.A., Pham Dinh, T.: Approximation and Penalization of the ℓ_0-norm in DC Programming, Research Report, National Institute for Applied Sciences, Rouen, France (2010)
[18] Le Thi, H.A., Pham Dinh, T.: DC Programming and DCA for solving nonconvex programs involving ℓ_0-norm, Research Report, National Institute for Applied Sciences, Rouen, France (2010)
[19] Le Thi, H.A., Moeini, M.: Long-Short Portfolio Optimization Under Cardinality Constraints by Difference of Convex Functions Algorithm. Journal of Optimization Theory & Applications, 27 pages (October 2012), doi:10.1007/s10957-012-0197-0 · Zbl 1300.91046
[20] Le Thi, H.A., Pham Dinh, T., Huynh, V.N.: Exact penalty and Error Bounds in DC programming. Journal of Global Optimization, Special Issue in Memory of Reiner Horst, Founder of the Journal 52(3), 509-535 (2012) · Zbl 1242.49037
[21] Le Thi, H.A., Pham Dinh, T.: Exact Penalty in Mixed Integer DC Programming, Research Report, Lorraine University, France (2011)
[22] Le Thi, H.A., Pham Dinh, T., Nguyen, D.Y.: Properties of two DC algorithms in quadratic programming. Journal of Global Optimization 49(3), 481-495 (2011) · Zbl 1213.90189
[23] Le Thi, H.A., Pham Dinh, T.: On Solving Linear Complementarity Problems by DC programming and DCA. Journal on Computational Optimization and Applications 50(3), 507-524 (2011) · Zbl 1237.90234
[24] Le Thi, H.A., Madhi, M., Pham Dinh, T., Judice, J.: Solving Eigenvalue Symmetric problem by DC programming and DCA. Journal on Computational Optimization and Applications 51(3), 1097-1117 (2012) · Zbl 1241.90153
[25] Le Thi, H.A., Nguyen, D.M., Pham Dinh, T.: Globally solving a Nonlinear UAV Task Assignment Problem by stochastic and derministic optimization approaches. Optimization Letters 6(2), 315-329 (2012) · Zbl 1258.90050
[26] Le Thi, H.A., Pham Dinh, T., Nguyen, D.Y.: Behavior of DCA sequences for solving the trust-region subproblem, Journal of Global Optimization. Journal of Global Optimization 53(2), 317-329 (2012) · Zbl 1259.65092
[27] Le Thi, H.A., Tran Duc, Q.: Solving Continuous Min Max Problem for Single Period Portfolio Selection with Discrete Constraints by DCA. Optimization 61(8) (2012) · Zbl 1252.90067
[28] Schleich, J., Le Thi, H.A., Bouvry, P.: Solving the Minimum m-Dominating Set problem by a Continuous Optimization Approach based on DC Programming and DCA. Journal of Combinatorial Optimization 24(4), 397-412 (2012) · Zbl 1261.90082
[29] Le Thi, H.A., Vaz, A.I.F., Vicente, L.N.: Optimizing radial basis functions by D.C. programming and its use in direct search for global derivative-free optimization. TOP 20(1), 190-214 (2012) · Zbl 1267.90110
[30] Le Thi, H.A., Le Hoai, M., Pham Dinh, T., Huynh, V.N.: Spherical separation by DC programming and DCA. To appear in Journal of Global Optimization, 17 pages (Online first Feabruary 2012), doi:10.1007/s10898-012-9859-6 · Zbl 1275.90093
[31] Muu, L.D., Tran Dinh, Q., Le Thi, H.A., Pham Dinh, T.: A new decomposition algorithm for globally solving mathematical programs with affine equilibrium constraints. Acta Mathematica Vietnamica 37(2), 201-218 (2012) · Zbl 1248.49042
[32] Niu, Y.S., Pham Dinh, T., Le Thi, H.A., Judice, J.: Efficient DC Programming Approaches for Asymmetric Eigenvalue Complementarity Problem. Optimization Methods and Software 28(4), 812-829 (2013) · Zbl 1307.90145
[33] Ta, A.S., Le Thi, H.A., Khadraoui, D., Pham Dinh, T.: Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial and Management Optimization 8(1), 87-102 (2012) · Zbl 1364.90219
[34] Le Thi, H.A., Pham Dinh, T., Tran Duc, Q.: A DC programming approach for a class of bilevel programming problems and its application in portfolio selection. NACO Numerical Algebra, Control and Optimization 2(1), 167-185 (2012) · Zbl 1254.90175
[35] Cheng, S.O., Le Thi, H.A.: Learning sparse classifiers with Difference of Convex functions Algorithms. Optimization Methods and Software 28(4), 830-854 (2013) · Zbl 1282.90181
[36] Anh, P.N., Le Thi, H.A.: An Armijo-type method for pseudomonotone equilibrium problems and its applications. Journal of Global Optimization 57, 803-820 (2013) · Zbl 1285.65040
[37] Le Thi, H.A., Moeini, M.: Long-Short Portfolio Optimization Under Cardinality Constraints by Difference of Convex Functions Algorithm. Journal of Optimization Theory & Applications, 26 pages (October 2012), doi:10.1007/s10957-012-0197-0 · Zbl 1300.91046
[38] Nguyen, D.M., Le Thi, H.A., Pham Dinh, T.: Solving the Multidimensional Assignment Problem by a Cross-Entropy method. Journal of Combinatorial Optimization, 16 pages (Online first October 2012), doi:10.1007/s10878-012-9554-z · Zbl 1297.90072
[39] Le Thi, H.A., Pham Dinh, T., Nguyen, D.M.: A deterministic optimization approach for planning a multisensor multizone search for a target. Computer & Operations Research 41, 231-239 (2014) · Zbl 1348.90347
[40] Anh, P.N., Le Thi, H.A.: The Subgradient Extragradient Method Extended to Equilibrium Problems, Optimization (online first December 2012), doi:10.1080/02331934.2012.745528 · Zbl 1317.65149
[41] Le Hoai, M., Le Thi, H.A., Pham Dinh, T., Huynh, V.N.: Block Clustering based on DC programming and DCA. NECO Neural Computation 25(10), 2776-2807 (2013) · Zbl 1418.62253
[42] Le Thi, H.A., Tran Duc, Q.: New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains. Journal of Global Optimization (in press) · Zbl 1304.90164
[43] Le Thi, H.A., Le Hoai, M., Pham Dinh, T.: New and efficient DCA based algorithms for Minimum Sum-of-Squares Clustering. Pattern Recognition (in press) · Zbl 1326.68225
[44] Le Thi, H.A., Pham Dinh, T., Nguyen, C.N., Le Hoai, M.: DC Programming and DCA for Binary Quadratic Programming in Diversity Data Mining. To appear in Optimization · Zbl 1177.90286
[45] Le Thi, H.A., Tran Duc, Q., Adjallah, K.H.: A Difference of Convex functions Algorithm for Optimal Scheduling and real-time assignment of preventive maintenance jobs on parallel processors. To appear in JIMO Journal of Industrial and Management Optimization · Zbl 1281.90029
[46] An, L.T.H., Quynh, T.D.: Optimizing a multi-stage production/inventory system by DC programming based approaches. Computational Optimization an Applications (in press) · Zbl 1330.90055
[47] An, L.T.H., Tao, P.D., Belghiti, T.: DCA based algorithms for Multiple Sequence Alignment (MSA). Central European Journal of Operations Research (in press) · Zbl 1339.92064
[48] Tao, P.D., An, L.T.H.: Recent advances in DC programming and DCA. To appear in Transactions on Computational Collective Intelligence, 37 pages (2013)
[49] An, L.T.H., Tao, P.D.: DC programming in Communication Systems: challenging models and methods. To appear in Vietnam Journal of Computer Science, 21 pages. Springer (invited issue)
[50] An, L.T.H., Tao, P.D.: DC programming approaches for Distance Geometry problems. In: Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.) Distance Geometry: Theory, Methods and Applications, vol. XVI, 57, 420 pages. Springer (2013) · Zbl 1271.65038
[51] Bradley, P.S., Mangasarian, O.L.: Feature selection via concave minimization and support vector machines. In: Proceedings of the Fifteenth International Conference on Machine Learning (ICML 1998), pp. 82-90 (1998)
[52] Chambolle, A., DeVore, R.A., Lee, N.Y., Lucier, B.J.: Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage. IEEE Trans. Image Process. 7, 319-335 (1998) · Zbl 0993.94507
[53] Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc. B 39, 1-38 (1977) · Zbl 0364.62022
[54] Bertsekas, D.: Nonlinear Programming. Athenta Scientific, Belmont (1995)
[55] Bogg, P.T., Tolle, J.W.: Sequential Quadratic Programming. Acta Numerica, 1-51 (1995)
[56] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[57] Tuy, H.: Convex Analysis and Global Optimization. Kluwer Academic (2000) · Zbl 0957.90082
[58] Fletcher, R., Leyfer, S.: Nonlinear programming without a penalty function. Math. Program. 91, 239-270 (2002) · Zbl 1049.90088
[59] An, L.T.H., Tao, P.D.: Large Scale Molecular Optimization From Distance Matrices by a D.C. Optimization Approach. SIAM Journal on Optimization 14(1), 77-116 (2003) · Zbl 1075.90071
[60] An, L.T.H., Tao, P.D.: The DC (Difference of Convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems. Annals of Operations Research 133, 23-46 (2005) · Zbl 1116.90122
[61] Mangasarian, O.L.: Nonlinear Programming, McGraw-Hill, New York (1969) · Zbl 0194.20201
[62] Lawrence, C.T., Tits, A.: A computationally efficient feasible sequential quadratic programming algorithm. SIAM J. Optim. 11, 1092-1118 (2001) · Zbl 1035.90105
[63] Mangasarian, O.L., Fromovitz, S.: The Fritz John necessay optimality conditions in the presence of equality constraints. J. Math. Anal. Appl. 17, 34-47 (1967) · Zbl 0149.16701
[64] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, Vol. 1. Springer, Heidelberg (2006)
[65] Nocedal, J., Wright, S.J.: Numerical Optimization, Springer, Berlin (2006) · Zbl 1104.65059
[66] Pang, J.-S.: Exact penalty functions for mathematical programs with linear complementary constraints. Optimization 42, 1-8 (1997) · Zbl 0888.90134
[67] Polak, E.: Optimization. Springer. New York (1997)
[68] Rockafellar, R.T.: Convex Analysis. Princeton University Press (1970) · Zbl 0193.18401
[69] Rockafellar, R.T.: Penalty methods and augmanted Lagrangians nonlinear programming. In: Conti, R., Ruberti, A. (eds.) 5th Conference on Optimization Techniques Part I. LNCS, vol. 3, pp. 418-425. Springer, Heidelberg (1973)
[70] Rockafellar, R.T., Wets, J.-B.: Variational Analysis. Springer, Heidelberg (1998) · Zbl 0888.49001
[71] Solodov, M.V.: On the sequential quadratically constrained quadratic programming methods. Mathematics of Oper. Research 29, 64-79 (2004) · Zbl 1082.90140
[72] Zaslavski, A.J.: A sufficient condition for exact penalty constrained optimization. SIAM J. Optim. 16, 250-262 (2005) · Zbl 1098.49030
[73] Yuille, A. · Zbl 1022.68112
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.