×

Exact penalty and error bounds in DC programming. (English) Zbl 1242.49037

Summary: 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.

MSC:

49J52 Nonsmooth analysis
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DC Programming and DCA: http://lita.sciences.univ-metz.fr/\(\sim\)lethi/
[2] Le Thi H. A., Pham Dinh T., Muu L.D.: Exact penalty in DC programming. Vietnam J. Math. 27, 169–178 (1999) · Zbl 1006.90062
[3] 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) · Zbl 0905.90131 · doi:10.1023/A:1008288411710
[4] 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) · Zbl 0912.90233 · doi:10.1023/A:1008240227198
[5] Le Thi H. A., Pham Dinh T.: A continuous approach for large scale linearly constrained quadratic zero-one programming. Optimization 50, 93–120 (2001) · Zbl 1039.90050 · doi:10.1080/02331930108844555
[6] 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) · Zbl 0952.90031 · doi:10.1007/s101070050003
[7] Le Thi H. A., Pham Dinh T.: A continuous approach for large-scale constrained quadratic zero-one programming. Optimization 45(3), 1–28 (2001)
[8] 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)
[9] 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 · doi:10.1137/S1052623498342794
[10] 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) · Zbl 1044.90071 · doi:10.1023/A:1023993504522
[11] 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) · Zbl 1116.90122 · doi:10.1007/s10479-004-5022-1
[12] 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) · Zbl 1149.90117 · doi:10.1016/j.ejor.2005.07.028
[13] 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) · Zbl 1190.90142 · doi:10.1016/j.dam.2007.03.024
[14] 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) · Zbl 1151.90508
[15] 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) · Zbl 1284.90057 · doi:10.1007/s11634-008-0030-7
[16] 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) · Zbl 1180.90241 · doi:10.1007/s10898-008-9325-7
[17] 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) · Zbl 1229.90091 · doi:10.1007/s10898-009-9481-4
[18] Thiao, M., Phanm Dinh, T., Le Thi, H. A.: A DC programming approach for sparse eigenvalue problem, ICML 2010, pp. 1063–1070
[19] 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
[20] 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) · Zbl 1213.90189 · doi:10.1007/s10898-010-9573-1
[21] 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) · Zbl 1226.90060 · doi:10.1007/s10898-009-9507-y
[22] 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 · Zbl 1241.90153
[23] Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht, Holland (1995) · Zbl 0836.90134
[24] 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) · Zbl 0621.90064 · doi:10.1007/BF00939768
[25] 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) · Zbl 0755.90076 · doi:10.1007/BF00119991
[26] Horst R., Tuy H.: Global optimization (deterministic approaches). 3rd edn. Springer, Berlin, Germany (1996) · Zbl 0867.90105
[27] Horst R., Thoai N.V.: DC programming: overview. J. Optim. Theory Appl. 103(1), 1–43 (1999) · Zbl 1073.90537 · doi:10.1023/A:1021765131316
[28] Aze, D.: A survey on error bounds for lower semicontinuous functions. In: Proceedings of the ESAIM (2003)
[29] 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) · Zbl 1085.49019 · doi:10.1051/cocv:2004013
[30] Auslender A., Crouzeix J.P.: Global regularily theorems. Math. Oper. Res 13, 243–253 (1998) · Zbl 0655.90059 · doi:10.1287/moor.13.2.243
[31] 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) · Zbl 1028.90066 · doi:10.1007/s101070050015
[32] Bosch P., Jourani A., Henrion R.: Sufficient conditions for error bounds and applications. Appl. Math. Optim. 50, 161–181 (2004) · Zbl 1176.90585 · doi:10.1007/s00245-004-0799-5
[33] Burke J.V.: An exact penalization viewpoint of contrained optimization. SIAM J. Control Optim. 29, 968–998 (1991) · Zbl 0737.90060 · doi:10.1137/0329054
[34] Burke J.V., Tseng P.: A unified analysis of Hoffman’s bound via Fenchel duality. SIAM J. Optim. 6, 265–282 (1996) · Zbl 0849.90093 · doi:10.1137/0806015
[35] Clarke F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[36] Cornejo O., Jourani A., Zalinescu C.: Conditioning and upper-Lipschitz inverse subdifferentials in nonsmooth optimization. J. Optim. Theory Appl. 95, 127–148 (1997) · Zbl 0890.90164 · doi:10.1023/A:1022687412779
[37] Dedieu J.P.: Penalty functions in subanalytic optimization. Optimization 26, 27–32 (1992) · Zbl 0817.90103 · doi:10.1080/02331939208843840
[38] Fabian M., Henrion R., Kruger A.Y., Outrata J.V.: Error bounds: necessary and sufficient conditions. Set-Valued Var. Anal. 18, 121–149 (2010) · Zbl 1192.49018 · doi:10.1007/s11228-010-0133-0
[39] Hiriart-Urruty J.B., Lemaréchal C.: Convex Analysis and Minimization Algorithms, Parts I & II. Springer, Verlag, Berlin, Heidelberg (1991) · Zbl 0807.46041
[40] Hoffman A.J.: On approximate solutions of systems of linear inequalities. J. Res. Nat. Bur. Stand. 49, 263–265 (1952) · doi:10.6028/jres.049.027
[41] Ioffe A.: Regular points of Lipschitz functions. Trans. Am. Soc. 251, 61–69 (1979) · Zbl 0427.58008 · doi:10.1090/S0002-9947-1979-0531969-6
[42] Tuy H.: Convex Analysis and Global Optimization. Kluwer, Acadelic Publisher, Boston, Dordrecht, London (2000) · Zbl 0957.90082
[43] Klatte D., Li W.: Asymptotic constraint qualifications and error bounds for convex inequalities. Math. Program. 84, 137–160 (1999) · Zbl 1050.90557
[44] Jourani A.: Hoffman’s error bound, local controlability and sensivity analysis. SIAM J. Control Optim. 38, 947–970 (2000) · Zbl 0945.46023 · doi:10.1137/S0363012998339216
[45] 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)
[46] Lojasiewicz M.S.: Sur le problème de la division. Stud. Math. 18, 87–136 (1959) · Zbl 0115.10203
[47] Li W.: Abadie’s constraint qualification, metric regularity, and error bound for differentiable convex inequalities. SIAM J. Optim. 7(4), 966–978 (1997) · Zbl 0891.90132 · doi:10.1137/S1052623495287927
[48] Luo X.D., Luo Z.Q.: Extension of Hoffman’s error bound to polynominal systems. SIAM J. Optim. 4, 383–392 (1994) · Zbl 0821.90113 · doi:10.1137/0804021
[49] 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) · Zbl 1043.90552
[50] Luo Z.Q., Pang J.S.: Error bounds for the analytic systems and their applications. Math. Program. 67, 1–28 (1994) · Zbl 0813.90116 · doi:10.1007/BF01582210
[51] 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) · Zbl 0870.90092 · doi:10.1007/BF02592205
[52] Magasarian O.L.: A condition number for differentiable convex inequalities. Math. Oper. Res. 10, 175–179 (1985) · Zbl 0565.90059 · doi:10.1287/moor.10.2.175
[53] Magasarian O.L., Shiau T.H.: Error bounds for monotone linear complementarity problems. Math. Program. 36, 81–89 (1986) · Zbl 0613.90095 · doi:10.1007/BF02591991
[54] Mordukhovich B.S: Variational analysis and generalized differentiation. I. Basic theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 330. Springer, Berlin (2006)
[55] Mordukhovich B.S: Variational analysis and generalized differentiation. II. Applications. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 331. Springer, Berlin (2006)
[56] Ngai H.V., Théra M.: On necessary conditions for non-Lipschitz optimization problems. SIAM J. Optim. 12(3), 656–668 (2002) · Zbl 1004.49024 · doi:10.1137/S1052623400366656
[57] 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) · Zbl 1058.49017 · doi:10.1023/B:SVAN.0000023396.58424.98
[58] Ngai H.V., Théra M.: Error bounds for convex differentiable inequality systems in Banach spaces. Math. Program. 104, 465–482 (2005) · Zbl 1089.49028 · doi:10.1007/s10107-005-0624-1
[59] 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) · Zbl 1158.49020 · doi:10.1137/060675721
[60] Ngai H.V., Théra M.: Error bounds for systems of lower semicontinuous functions in Asplund spaces. Math. Program. 116, 397–427 (2009) · Zbl 1215.49028 · doi:10.1007/s10107-007-0121-9
[61] 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) · Zbl 1202.49024 · doi:10.1137/090767819
[62] 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 · Zbl 1208.49030
[63] 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) · Zbl 0895.90152
[64] 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 · doi:10.1137/S1052623494274313
[65] Ng K.F., Zheng X.Y.: Error bound for lower semicontinuous functionsin normed spaces. SIAM J.Optim. 12, 1–17 (2001) · Zbl 1040.90041 · doi:10.1137/S1052623499358884
[66] Pang J.S.: Error bounds in mathematical programming. Math. Program. Ser. B 79, 232–299 (1997) · Zbl 0887.90165
[67] 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) · Zbl 0946.49019
[68] Rockafellar R.T.: Convex Analysis. Princeton University Press, Berlin (1970) · Zbl 0193.18401
[69] Robinson S.M.: An application of error bound for convex programming in a linear space. SIAM J. Control Optim. 13, 271–273 (1975) · Zbl 0297.90072 · doi:10.1137/0313015
[70] 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) · Zbl 0835.90096 · doi:10.1007/BF01106607
[71] Wang T., Pang J.S.: Global error bound for convex quadratic inequality systems. Optimization 31, 1–12 (1994) · Zbl 0817.90078 · doi:10.1080/02331939408844003
[72] Wu Z., Ye J.: On errors bounds for lower semicontinuous functions. Math. Program. 92, 301–314 (2002) · Zbl 1041.90053 · doi:10.1007/s101070100278
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.