Global convergence of a proximal linearized algorithm for difference of convex functions. (English) Zbl 1355.90073

Summary: A proximal linearized algorithm for minimizing difference of two convex functions is proposed. If the sequence generated by the algorithm is bounded it is proved that every cluster point is a critical point of the function under consideration, even if the auxiliary minimizations are performed inexactly at each iteration. Linear convergence of the sequence is established under suitable additional assumptions.


90C26 Nonconvex programming, global optimization
Full Text: DOI


[1] Martinet, B, Regularisation d’inéquations variationelles par approximations succesives, Rev. Française d’Inform. Recherche Oper., 4, 154-159, (1970) · Zbl 0215.21103
[2] Moreau, JJ, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93, 273-299, (1965) · Zbl 0136.12101
[3] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. control. optim., 14, 877-898, (1976) · Zbl 0358.90053
[4] Kaplan, A; Tichatschke, R, Proximal point methods and nonconvex optimization, J. Glob. Optim., 13, 389-406, (1998) · Zbl 0916.90224
[5] Hare, W; Sagastizábal, C, Computing proximal points of nonconvex functions, Math. Program., 116, 221-258, (2009) · Zbl 1168.90010
[6] Otero, RG; Iusem, AN, Proximal methods in reflexive Banach spaces without monotonicity, J. Math. Anal. Appl., 330, 433-450, (2007) · Zbl 1160.90692
[7] Iusem, A.N., Pennanen, T., Svaiter, B.F.: Inexact variants of the proximal point algorithm without monotonicity. SIAM J. Optim. 13(4), 1080-1097 (2003) · Zbl 1053.90134
[8] Bento, GC; Soubeyran, A, A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka-lojasiewicz inequality, Set-Valued Var. Anal., 23, 501-517, (2015) · Zbl 1342.49019
[9] Attouch, H; Bolte, J; Svaiter, BF, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program, 137, 91-129, (2013) · Zbl 1260.49048
[10] Burachik, RS; Svaiter, BF, A relative error tolerance for a family of generalized proximal point methods, Math. Oper. Res., 26, 816-831, (2001) · Zbl 1082.65539
[11] Solodov, MV; Svaiter, BF, Error bounds for proximal point subproblems and associated inexact proximal point algorithms, Math. Program, 88, 371-389, (2000) · Zbl 0963.90064
[12] Solodov, MV; Svaiter, BF, A unified framework for some inexact proximal point algorithms, Numer. Funct. Anal. Optim., 22, 1013-1035, (2001) · Zbl 1052.49013
[13] Zaslavski, A, Convergence of a proximal point method in the presence of computational errors in Hilbert spaces, SIAM J. Optim., 20, 2413-2421, (2010) · Zbl 1208.49042
[14] Bento, GC; Soubeyran, A, Generalized inexact proximal algorithms: routine’s formation with resistance to change, following worthwhile changes, J. Optim. Theory Appl., 172, 1-16, (2015) · Zbl 1342.49018
[15] Sun, W; Sampaio, RJB; Candido, MAB, Proximal point algorithm for minimization of DC functions, J. Comput. Math., 21, 451-462, (2003) · Zbl 1107.90427
[16] Moudafi, A; Maingé, P-E, On the convergence of an approximate proximal method for d.c. functions, J. Comput. Math., 24, 475-480, (2006) · Zbl 1104.65058
[17] Souza, J.C.O., Oliveira, P.R.: A proximal point algorithm for DC functions on Hadamard manifolds. J. Glob. Optim. (2015). doi:10.1007/s10898-015-0282-7 · Zbl 1329.49056
[18] Hartman, P, On functions representable as a difference of convex functions, Pac. J. Math., 9, 707-713, (1959) · Zbl 0093.06401
[19] Bomze, I; Lemaréchal, C, Necessary conditions for local optimality in difference-of-convex programming, J. Convex Anal., 17, 673-680, (2010) · Zbl 1201.90199
[20] Horst, R; Thoai, NV, DC programming: overview, J. Optim. Theory Appl., 103, 1-43, (1999) · Zbl 1073.90537
[21] Hiriart-Urruty, JB, Generalized differentiabity, duality and optimization for problems dealing with difference of convex functions, convexity and duality in optimization, Lectur. Notes Econ. Math. Syst, 256, 37-70, (1986)
[22] Pham, DT; Souad, EB, Algorithms for solving a class of nonconvex optimization problems: methods of subgradient, Fermat Days 85: Math. Optim., 129, 249-271, (1986)
[23] Ferrer, A; Bagirov, A; Beliakov, G, Solving DC programs using the cutting angle method, J. Glob. Optim., 61, 71-89, (2015) · Zbl 1312.90059
[24] Pham, DT; An, LTH; Akoa, F, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46, (2005) · Zbl 1116.90122
[25] Holmberg, K; Tuy, H, A production-transportation problem with stochastic demand and concave production costs, Math. Program., 85, 157-179, (1999) · Zbl 0956.90020
[26] Chen, P.C., Hansen, P., Jaumard, B., Tuy, H.: Solution of the multisource weber and conditional weber problems by d.c. programming. Oper. Res. 46(4), 548-562 (1998) · Zbl 0979.90099
[27] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex analysis and minimization algorithms. Springer, Berlin (1993) · Zbl 0795.49001
[28] Rockafellar, R.T.: Convex analysis. Princeton University Press, Princeton, New Jersey (1970) · Zbl 0193.18401
[29] Ginchev, I; Gintcheva, D, Characterization and recognition of dc functions, J. Glob. Optim., 57, 633-647, (2013) · Zbl 1284.26014
[30] Burachik, R., Graña Drummond, L.M., Iusem, A.N., Svaiter, B.F.: Full convergence of the steepest descent method with inexact line searches. Optimization 32(2), 137-146 (1995) · Zbl 0821.90089
[31] Soubeyran, A: Variational rationality. Human behaviors as worthwhile stay and change transitions, possibly ending in traps, before reaching desires. Preprint at GREQAM-AMSE (2015) · Zbl 1260.49069
[32] Polyak, B.T.: Sharp Minima Institute of Control Sciences Lecture Notes, Moscow, USSR, 1979. Presented at the IIASA workshop on generalized Lagrangians and their applications, IIASA, Laxenburg, Austria (1979) · Zbl 0916.90224
[33] Ferris, M.C.: Weak sharp minima and penalty functions in mathematical programming. Ph.D. Thesis. University of Cambridge, UK (1988) · Zbl 1208.49042
[34] Li, G; Mordukhovich, BS, Holder metric subregularity with applications to proximal point method, SIAM J. Optim., 22, 1655-1684, (2012) · Zbl 1260.49069
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.