Abstract
In the present paper, we are concerned with conditions ensuring the exact penalty for nonconvex programming. Firstly, we consider problems with concave objective and constraints. Secondly, we establish various results on error bounds for systems of DC inequalities and exact penalty, with/without error bounds, in DC programming. They permit to recast several class of difficult nonconvex programs into suitable DC programs to be tackled by the efficient DCA.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
DC Programming and DCA: http://lita.sciences.univ-metz.fr/~lethi/
Le Thi H. A., Pham Dinh T., Muu L.D.: Exact penalty in DC programming. Vietnam J. Math. 27, 169–178 (1999)
Le Thi H. A., Pham Dinh T.: Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J. Glob. Optim. 11, 253–285 (1997)
Le Thi H. A., Pham Dinh T.: A branch-and-bound method via DC optimization and ellipsoidal technique for box constrained nonconvex quadratic programming problems. J. Glob. Optim. 13, 171–206 (1998)
Le Thi H. A., Pham Dinh T.: A continuous approach for large scale linearly constrained quadratic zero-one programming. Optimization 50, 93–120 (2001)
Le Thi H. A.: An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints. Math. Program. Ser. A 87(3), 401–426 (2000)
Le Thi H. A., Pham Dinh T.: A continuous approach for large-scale constrained quadratic zero-one programming. Optimization 45(3), 1–28 (2001)
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’ 02). Valbonne-Sophia Antipolis, France, October 2–4 (2002)
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)
Le Thi H. A., Pham Dinh T., Muu L.D.: Simplicially constrained DC optimization over the efficient and weakly efficient sets. J. Optim. Theory Applications 117(3), 503–531 (2003)
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. Ann. Oper. Res. 133, 23–48 (2005)
Le Thi H. A., Minh L.H., Pham Dinh T.: Optimization based DC programming and DCA for hierarchical clustering. Eur. J. Oper. Res. 183, 1067–1085 (2007)
Le Thi H. A., Pham Dinh T.: A continuous approach for the concave cost supply problem via DC programming and DCA. Discret. Appl. Math. 156, 325–338 (2008)
Pham Dinh T., Le Thi H. A., Akoa F.: Combining DCA and interior point techniques for large-scale nonconvex quadratic programming optimization. Methods Softw. 23(4), 609–629 (2008)
Le Thi H. A., Minh L.H., Vinh N.V., Pham Dinh T.: A DC programming approach for feature selection in support vector machines learning. Adv. Data Analysis Classif. 2(3), 259–278 (2008)
Le Thi H. A., Pham Dinh T., Thoai N.V., Nam N.C.: DC optimization techniques for solving a class of nonlinear bilevel programs. J. Glob. Optim. 44(3), 313–337 (2009)
Minh L.H., Le Thi H. A., Pham Dinh T., Bouvry P.: A combined DCA-GA for constructing highly nonlinear balanced boolean functions in cryptography. J. Glob. Optim. 47(4), 597–614 (2010)
Thiao, M., Phanm Dinh, T., Le Thi, H. A.: A DC programming approach for sparse eigenvalue problem, ICML 2010, pp. 1063–1070
Tao, P.D., Niu, Y.-S.: An efficient DC programming approach for portfolio decision with higher moments. Comput. Optim. Appl. 1–30 (2010). doi:10.1007/s10589-010-9383-x
Le Thi H.A., Pham Dinh T., Yen N.D.: Properties of two DC algorithms for quadratic programming. J. Glob. Optim. 49(3), 481–495 (2010)
Pham Dinh T., Nam N.C., Le Thi H. A.: An efficient combination of DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs. J. Glob. Optim. 48(4), 595–632 (2010)
Le Thi, H. A., Mahdi, M., Pham Dinh, T., Joaquim, J.: A DC programming approach for solving the symmetric eigenvalue complementarity problem. Comput. Optim. Appl. 1–21 (2010). doi:10.1007/s10589-010-9388-5
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht, Holland (1995)
Horst R.: Deterministic global optimization with partition sets whose feasibility is not known: application to concave minimization, reverse convex constraints, DC programming, and Lipschitz optimization. J. Optim. Theory Appl. 58, 11–37 (1988)
Horst R., Phong T.Q., Thoai N.V., De Vries J.: On solving a DC programming problem by a sequence of linear programs. J. Glob. Optim. 1, 183–203 (1991)
Horst R., Tuy H.: Global optimization (deterministic approaches). 3rd edn. Springer, Berlin, Germany (1996)
Horst R., Thoai N.V.: DC programming: overview. J. Optim. Theory Appl. 103(1), 1–43 (1999)
Aze, D.: A survey on error bounds for lower semicontinuous functions. In: Proceedings of the ESAIM (2003)
Aze D., Corvellec J.-N.: Characterization of error bounds for lower semicontinuous functions on metric spaces. ESAIM Control Optim. Calc. Var 10, 409–425 (2004)
Auslender A., Crouzeix J.P.: Global regularily theorems. Math. Oper. Res 13, 243–253 (1998)
Bartelt M., Li W.: Exact order of Hoffman’s error bounds for elliptic quadratic inequalities derived from vector-valued Chebyshev approximation. Math. Program. Ser. B 88(2), 223–253 (2000)
Bosch P., Jourani A., Henrion R.: Sufficient conditions for error bounds and applications. Appl. Math. Optim. 50, 161–181 (2004)
Burke J.V.: An exact penalization viewpoint of contrained optimization. SIAM J. Control Optim. 29, 968–998 (1991)
Burke J.V., Tseng P.: A unified analysis of Hoffman’s bound via Fenchel duality. SIAM J. Optim. 6, 265–282 (1996)
Clarke F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
Cornejo O., Jourani A., Zalinescu C.: Conditioning and upper-Lipschitz inverse subdifferentials in nonsmooth optimization. J. Optim. Theory Appl. 95, 127–148 (1997)
Dedieu J.P.: Penalty functions in subanalytic optimization. Optimization 26, 27–32 (1992)
Fabian M., Henrion R., Kruger A.Y., Outrata J.V.: Error bounds: necessary and sufficient conditions. Set-Valued Var. Anal. 18, 121–149 (2010)
Hiriart-Urruty J.B., Lemaréchal C.: Convex Analysis and Minimization Algorithms, Parts I & II. Springer, Verlag, Berlin, Heidelberg (1991)
Hoffman A.J.: On approximate solutions of systems of linear inequalities. J. Res. Nat. Bur. Stand. 49, 263–265 (1952)
Ioffe A.: Regular points of Lipschitz functions. Trans. Am. Soc. 251, 61–69 (1979)
Tuy H.: Convex Analysis and Global Optimization. Kluwer, Acadelic Publisher, Boston, Dordrecht, London (2000)
Klatte D., Li W.: Asymptotic constraint qualifications and error bounds for convex inequalities. Math. Program. 84, 137–160 (1999)
Jourani A.: Hoffman’s error bound, local controlability and sensivity analysis. SIAM J. Control Optim. 38, 947–970 (2000)
Lewis A.S., Pang J.S. et al.: Error bound for convex inequality systems. In: Crouzeix, J.P. (eds) Generalized convexity and generalized monotonicity. Proceedings of the Fifth Symposium on Generalized Convexity, pp. 75–100. Kluwer, Dordrecht (1997)
Lojasiewicz M.S.: Sur le problème de la division. Stud. Math. 18, 87–136 (1959)
Li W.: Abadie’s constraint qualification, metric regularity, and error bound for differentiable convex inequalities. SIAM J. Optim. 7(4), 966–978 (1997)
Luo X.D., Luo Z.Q.: Extension of Hoffman’s error bound to polynominal systems. SIAM J. Optim. 4, 383–392 (1994)
Luo Z.Q., Sturm J.F. et al.: Error bounds for quadratic systems. In: Frenk H., et al (eds) High performance optimization, pp. 383–404. Kluwer, Dordrecht (2000)
Luo Z.Q., Pang J.S.: Error bounds for the analytic systems and their applications. Math. Program. 67, 1–28 (1994)
Luo Z.Q., Pang J.S., Ralph D., Wu S-Q.: Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints. Math. Program. 75, 19–76 (1996)
Magasarian O.L.: A condition number for differentiable convex inequalities. Math. Oper. Res. 10, 175–179 (1985)
Magasarian O.L., Shiau T.H.: Error bounds for monotone linear complementarity problems. Math. Program. 36, 81–89 (1986)
Mordukhovich B.S: Variational analysis and generalized differentiation. I. Basic theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 330. Springer, Berlin (2006)
Mordukhovich B.S: Variational analysis and generalized differentiation. II. Applications. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 331. Springer, Berlin (2006)
Ngai H.V., Théra M.: On necessary conditions for non-Lipschitz optimization problems. SIAM J. Optim. 12(3), 656–668 (2002)
Ngai H.V., Théra M.: Errors bounds and implicit multifunction theorem in smooth Banach spaces and applications to optimization. Set-Valued Anal. 12, 195–223 (2004)
Ngai H.V., Théra M.: Error bounds for convex differentiable inequality systems in Banach spaces. Math. Program. 104, 465–482 (2005)
Ngai H.V., Théra M.: Error bounds in metric spaces and application to the perturbation stability of metric regularity. SIAM J. Optim. 19(1), 1–20 (2008)
Ngai H.V., Théra M.: Error bounds for systems of lower semicontinuous functions in Asplund spaces. Math. Program. 116, 397–427 (2009)
Ngai H.V., Kruger A., Théra M.: Stability of error bounds for semi-infinite convex constraint systems. SIAM J. Optim. 20(4), 2080–2096 (2010)
Ngai, H.V., Kruger, A., Théra, M.: Stability of error bounds for convex constraint systems in Banach spaces. SIAM J. Optim. 20, 3280–3296
Pham Dinh T., Le Thi H. A.: Convex analysis approach to D.C. programming: theory, algorithms and applications. Acta Mathe. Vietnamica 22, 289–355 (1997)
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)
Ng K.F., Zheng X.Y.: Error bound for lower semicontinuous functionsin normed spaces. SIAM J.Optim. 12, 1–17 (2001)
Pang J.S.: Error bounds in mathematical programming. Math. Program. Ser. B 79, 232–299 (1997)
Penot, J.P.,: Well-behavior, well-posedness and nonsmooth analysis. In: Proceedings of the ć6th International Conference on Math. Meth. in Ope. Research, Pliska Stud. Math. Bulgar. 12, pp. 141–190 (1998)
Rockafellar R.T.: Convex Analysis. Princeton University Press, Berlin (1970)
Robinson S.M.: An application of error bound for convex programming in a linear space. SIAM J. Control Optim. 13, 271–273 (1975)
Phong T.Q., Pham Dinh T., Le Thi H. A.: A new method for solving DC programming problem. Applications to fuel mixture nonconvex optimization problem. J. Glob. Optim. 6, 87–107 (1995)
Wang T., Pang J.S.: Global error bound for convex quadratic inequality systems. Optimization 31, 1–12 (1994)
Wu Z., Ye J.: On errors bounds for lower semicontinuous functions. Math. Program. 92, 301–314 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
The paper is dedicated to the memory of our friend Reiner Horst.
Rights and permissions
About this article
Cite this article
Le Thi, H.A., Pham Dinh, T. & Ngai, H.V. Exact penalty and error bounds in DC programming. J Glob Optim 52, 509–535 (2012). https://doi.org/10.1007/s10898-011-9765-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9765-3
Keywords
- DC programming
- Concave programming
- DCA
- Subdifferential
- Exact penalty
- Local and global error bounds
- Reformulation