## The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems.(English)Zbl 1116.90122

Summary: The DC programming and its DC algorithm (DCA) address the problem of minimizing a function $$f=g-h$$ (with $$g,h$$ being lower semicontinuous proper convex functions on $$\mathbb R^n$$) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the large scale setting. The computational efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs (when either $$g$$ or $$h$$ is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported.

### MSC:

 90C90 Applications of mathematical programming 90C26 Nonconvex programming, global optimization
Full Text:

### References:

 [1] An, Le Thi Hoai. (1994). ”Analyse numérique des algorithmes de l’optimisation DC. Approches locale et globale. Codes et simulations numériques en grande dimension. Applications.” Thèse de Doctorat de l’Université de Rouen. [2] An, Le Thi Hoai. (1997). ”Contribution à l’optimisation non convexe et l’optimisation globale: Théorie, algorithmes et applications.” Habilitation à Diriger des Recherches, Université de Rouen. [3] An, Le Thi Hoai. (2000). ”An Efficient Algorithm for Globally Minimizing a Quadratic Function under Convex Quadratic Constraints.” Math. Programming Ser. A 87(3), 401–426. · Zbl 0952.90031 [4] An, Le Thi Hoai. (2003). ”Solving Large Scale Molecular Distance Geometry Problem by a Smoothing Technique via the Gaussian Transform an DC Programming.” J. Global Optim. 27, 375–397. · Zbl 1064.90036 [5] An, Le Thi Hoai and Pham Dinh Tao. (1997). ”Solving a Class of Linearly Constrained Indefinite Quadratic Problems by DC Algorithms.” J. Global Optim. 11, 253–285. · Zbl 0905.90131 [6] An, Le Thi Hoai, Pham Dinh Tao, and Le Dung Muu. (1996). ”Numerical Solution for Optimization over the Efficient Set by DC Optimization Algorithm.” Oper. Res. Lett. 19, 117–128. · Zbl 0871.90074 [7] An, Le Thi Hoai and Pham Dinh Tao. (1998). ”A Branch-and-Bound Method via DC Optimization Algorithm and Ellipsoidal Techniques for Box Constrained Nonconvex Quadratic Programming Problems.” J. Global Optim. 13, 171–206. · Zbl 0912.90233 [8] An, Le Thi Hoai, Pham Dinh Tao, and Le Dung Muu. (1998). ”A Combined DC Optimization – Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems.” J. Combin. Optim. 2(1), 9–28. · Zbl 0904.90134 [9] An, Le Thi Hoai, Pham Dinh Tao, and Le Dung Muu. (1999). ”Exact Penalty in DC Programming.” Vietnam J. Math. 27(2), 169–178. · Zbl 1006.90062 [10] An, Le Thi Hoai and Pham Dinh Tao. (1999). ”DCA Revisited and DC Models of Real World Nonconvex Optimization Problems.” Technical Report, LMI, Insa-Rouen. · Zbl 1116.90122 [11] An, Le Thi Hoai and Pham Dinh Tao. (2000a). ”DC Programming Approach for Large-Scale Molecular Optimization via the General Distance Geometry Problem.” In Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches. Nonconvex Optimization and Its Applications, Vol. 40. Kluwer Academic, pp. 301–339. · Zbl 0968.92023 [12] An, Le Thi Hoai and Pham Dinh Tao. (2000b). ”Large Scale Molecular Conformation via the Exact Distance Geometry Problem.” In Optimization. Lecture Notes in Economics and Mathematical Systems, Vol. 481. Heidelberg: Springer, pp. 260–277. · Zbl 0982.90037 [13] An, Le Thi Hoai and Pham Dinh Tao. (2001a). ”A Continuous Approach for Large-Scale Linearly Constrained Quadratic Zero-One Programming.” Optim. 50(1,2), 93–120. · Zbl 1039.90050 [14] An, Le Thi Hoai and Pham Dinh Tao. (2001b). ”DC Optimization Approaches via Markov Models for Restoration of Signals (1-D) and (2-D).” In Advances in Convex Analysis and Global Optimization. Nonconvex Optimization and Its Applications, Vol. 54. Kluwer Academic, pp. 300–317. · Zbl 1049.90065 [15] An, Le Thi Hoai and Pham Dinh Tao. (2001c). ”DC Programming Approach and Solution Algorithm to the Multidimensional Scaling Problem.” In From Local to Global Optimization. Nonconvex Optimization and Its Applications, Vol. 53. Kluwer Academic, pp. 231–276. · Zbl 1007.90057 [16] An, Le Thi Hoai and Pham Dinh Tao. (2002a). ”DC Programming Approach for Multicommodity Network Optimization Problems with Step Increasing Cost Functions.” J. Global Optim. 22(1–4), 204–233. Special Issue, dedicated to Professor R. Horst on the occasion of his 60th birthday. · Zbl 1045.90074 [17] An, Le Thi Hoai and Pham Dinh Tao. (2002b). ”DC Programming. Theory, Algorithms, Applications: The State of the Art.” In First International Workshop on Global Constrained Optimization and Constraint Satisfaction. Valbonne-Sophia Antipolis, France, October 2–4, 2002. Research Report, 28 pages. Laboratory of Modeling, Optimization & Operations Research, Insa-Rouen, France (2002). · Zbl 1045.90074 [18] An, Le Thi Hoai and Pham Dinh Tao. (2003a). ”Large Scale Global Molecular Optimization from Exact Distance Matrices by a DC Optimization Approach.” SIAM J. Optim. 14(1), 77–114. · Zbl 1075.90071 [19] An, Le Thi Hoai and Pham Dinh Tao. (2003b). ”A New Algorithm for Solving Large Scale Molecular Distance Geometry Problems, Applied Optimization.” In Hight Performance Algorithms and Software for Nonlinear Optimization. Kluwer Academic, pp. 276–296. · Zbl 1112.90367 [20] An, Le Thi Hoai, Pham Dinh Tao, and Nguyen Van Thoai. (2002). ”Combination between Local and Global Methods for Solving an Optimization Problem over the Efficient Set.” European J. Oper. Res. 142, 257–270. · Zbl 1082.90563 [21] An, Le Thi Hoai, Pham Dinh Tao, and Le Dung Muu. (2003a). ”Simplicially Constrained DC Optimization over the Efficient Set and Weakly Efficient Sets.” J. Optim. Theory Appl. 117(3), 503–531. · Zbl 1044.90071 [22] An, Le Thi Hoai, Pham Dinh Tao, and Le Dung Muu. (2003b). ”A DC Optimization Approach to Mathematical Programming Problems with Linear Equilibrium Constraints.” Submitted. · Zbl 0904.90134 [23] An, Le Thi Hoai, Pham Dinh Tao, and Dinh Nho Hao. (2002). ”Towards Tikhonov Regularization of Nonlinear Ill-Posed Problems: A DC Programming Approach.” C.R. Acad. Sci. Paris Ser. I 335, 1073–1078. · Zbl 1018.65072 [24] An, Le Thi Hoai, Pham Dinh Tao, and Dinh Nho Hao. (2003). ”Solving Inverse Problems for an Elliptic Equations by D.C. (Difference of Convex Functions) Programming.” J. Global Optim. 25(4), 407–423. · Zbl 1046.90063 [25] An, Le Thi Hoai, Pham Dinh Tao, and Dinh Nho Hao. (2004a). ”On the Ill-Posedness of the Trust Region Subproblem.” J. Inverse Ill-Posed Problems, to appear. · Zbl 1049.90091 [26] An, Le Thi Hoai, Pham Dinh Tao, and Dinh Nho Hao. (2004b). ”DC Programming Approach to Tikhonov Regularization for Nonlinear Ill-Posed Problems.” Submitted. · Zbl 1018.65072 [27] Conn, A.R., N.I.M. Gould, and P.L. Toint. (2000). Trust Region Methods. MPS–SIAM Series on Optimization. · Zbl 0958.65071 [28] Hiriat Urruty, J.B. (1989). ”Conditions nécessaires et suffisantes d’optimalité globule en optimisation de différences de deux fonctions convexes.” C.R. Acad. Sci. Paris Ser. I 309, 459–462. [29] Hiriat Urruty, J.B. and C. Lemarechal. (1993). Convex Analysis and Minimization Algorithms. Berlin: Springer. [30] Horst, R., P.M. Pardalos, and Nguyen Van Thoai. (1995). Introduction to Global Optimization. Kluwer Academic. · Zbl 0836.90134 [31] Horst, R. and Nguyen Van Thoai. (1999). ”DC Programming: Overview.” J. Optim. Theory Appl. 2103(1), 1–43. · Zbl 1073.90537 [32] Horst, R. and Hoang Tuy. (1996). Global Optimization (Deterministic Approaches), 3rd ed. Springer. · Zbl 0867.90105 [33] Konno, H., Phan Thien Thach and Hoang Tuy. (1999). Optimization on Low Rank Nonconvex Structures. Kluwer Academic. · Zbl 0879.90171 [34] Laurent, P.J. (1972). Approximation et optimisation. Paris: Hermann. · Zbl 0238.90058 [35] Mahey, P. and Pham Dinh Tao. (1993). ”Partial Regularization of the Sum of Two Maximal Monotone Operators.” Math. Modell. Numer. Anal. (M 2 AN) 27, 375–395. · Zbl 0778.65042 [36] Mahey, P. and Pham Dinh Tao. (1995). ”Proximal Decomposition of the Graph of Maximal Monotone Operator.” SIAM J. Optim. 5, 454–468. · Zbl 0834.90105 [37] More, J.J. and Z. Wu. (1997). ”Global Continuation for Distance Geometry Problems.” SIAM J. Optim. 8, 814–836. · Zbl 0891.90168 [38] More, J.J. and Z. Wu. (1996). ”Distance Geometry Optimization for Protein Structures.” Preprint MCS-P628-1296, Argonne National Laboratory, Argonne, IL. [39] Moreau, J.J. (1965). ”Proximité et dualité dans un espace Hilbertien.” Bull. Soc. Math. France 93, 273–299. · Zbl 0136.12101 [40] Pardalos, P.M. and J.B. Rosen. (1987). Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Sciences, Vol. 268. Springer. · Zbl 0638.90064 [41] Pschenichny, B.N. (1971). Contrôle optimal et jeux differentiels. Rocquencourt: Cahiers de l’IRIA. [42] Rockafellar, R.T. (1970). Convex Analysis. Princeton: Princeton University. · Zbl 0193.18401 [43] Rockafellar, R.T. (1976). ”Monotone Operators and the Proximal Point Algorithm.” SIAM J. Control Optim. 14, 877–898. · Zbl 0358.90053 [44] Tao, Pham Dinh. (1975). ”Elements homoduaux relatifs à un couple de normes ({$$\phi$$},{$$\psi$$}). Applications au calcul de S {$$\phi$$}{$$\psi$$}(A).” Technical Report, Grenoble. [45] Tao, Pham Dinh. (1976). ”Calcul du maximum d’une forme quadratique définie positive sur la boule unité de la norme du max.” Technical Report, Grenoble. [46] Tao, Pham Dinh. (1981). ”Contribution à la théorie de normes et ses applications à l’analyse numérique.” Thèse de Doctorat d’Etat Es Science, Université Joseph Fourier, Grenoble. [47] Tao, Pham Dinh. (1984). ”Convergence of Subgradient Method for Computing the Bound Norm of Matrices.” Linear Algebra Appl. 62, 163–182. · Zbl 0563.65029 [48] Tao, Pham Dinh. (1985). ”Algorithmes de calcul d’une forme quadratique sur la boule unité de la norme maximum.” Numer. Math. 45, 377–440. · Zbl 0531.65022 [49] Tao, Pham Dinh. (1986). Algorithms for Solving a Class of Non Convex Optimization Problems. Methods of Subgradients. Fermat Days 85. Mathematics for Optimization, Elsevier Science Publishers, B.V. North-Holland. · Zbl 0638.90087 [50] Tao, Pham Dinh. (1988). ”Duality in D.C. (Difference of Convex Functions) Optimization. Subgradient Methods.” In Trends in Mathematical Optimization, International Series of Numerical Mathematics, Vol. 84. Birkhäuser, pp. 277–293. · Zbl 0634.49009 [51] Tao, Pham Dinh and Le Thi Hoai An. (1994). ”Stabilité de la dualité lagrangienne en optimisation DC (différence de deux fonctions convexes).” C.R. Acad. Sci. Paris Sér. I 318, 379–384. [52] Tao, Pham Dinh and Le Thi Hoai An. (1995). ”Lagrangian Stability and Global Optimality in Nonconvex Quadratic Minimization over Euclidean Balls and Spheres.” J. Convex Anal. 2, 263–276. · Zbl 0848.49022 [53] Tao, Pham Dinh and Le Thi Hoai An. (1998). ”DC Optimization Algorithms for Solving the Trust Region Subproblem.” SIAM J. Optim. 8, 476–505. · Zbl 0913.65054 [54] Tao, Pham Dinh and Le Thi Hoai An. (1997). ”Convex Analysis Approach to DC Programming: Theory, Algorithms and Applications.” Acta Math. Vietnamica 22(1), 287–355. [55] Thach, Phan Thien. (1993a). ”DC Sets, D.C. Functions and Nonlinear Equations.” Math. Programming 58, 415–428. · Zbl 0793.90054 [56] Thach, Phan Thien. (1993b). ”Global Optimality Criteria and Duality with Zero Gap in Nonconvex Optimization Problems.” SIAM J. Math. Anal. 24, 1537–1556. · Zbl 0793.90057 [57] Thach, Phan Thien. (1994). ”A Nonconvex Duality with Zero Gap and Applications.” SIAM J. Optim. 4, 44–64. · Zbl 0999.49503 [58] Thach, Phan Thien. (1996). ”On the Degree and Separability of Nonconvexity and Applications to Optimization Problems.” Math. Programming 77, 23–47. · Zbl 0891.90137 [59] Toland, J.F. (1978). ”Duality in Nonconvex Optimization.” J. Math. Anal. Appl. 66, 399–415. · Zbl 0403.90066 [60] Toland, J.F. (1979). ”On Subdifferential Calculus and Duality in Nonconvex Optimization.” Bull. Soc. Math. France, Mémoire 60, 177–183. · Zbl 0417.90088 [61] Tuy, Hoang. (1964). ”Concave Programming under Linear Constraints.” Translated Soviet Mathematics 5, 1437–1440. · Zbl 0132.40103 [62] Tuy, Hoang. (1998). Convex Analysis and Global Optimization. Kluwer Academic. · Zbl 0904.90156 [63] Tuy, Hoang. (2000). ”Monotonic Optimization: Problems and Solution Approaches.” SIAM J. Optim. 2, 464–494. · Zbl 1010.90059 [64] Wu, Z. (1996). ”The Effective Energy Transformation Scheme as a Special Continuation Approach to Global Optimization with Application to Molecular Conformation.” SIAM J. Optim. 6, 748–768. · Zbl 0868.90116
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.