×

zbMATH — the first resource for mathematics

On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. (English) Zbl 1165.90018
Summary: We study the convergence of the proximal algorithm applied to nonsmooth functions that satisfy the Łjasiewicz inequality around their generalized critical points. Typical examples of functions complying with these conditions are continuous semialgebraic or subanalytic functions. Following Łjasiewicz’s original idea, we prove that any bounded sequence generated by the proximal algorithm converges to some generalized critical point. We also obtain convergence rate results which are related to the flatness of the function by means of Łjasiewicz exponents. Apart from the sharp and elliptic cases which yield finite or geometric convergence, the decay estimates that are derived are of the type \(O(k - s )\), where \(s \in (0, + \infty)\) depends on the flatness of the function.

MSC:
90C26 Nonconvex programming, global optimization
47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Absil P.-A., Mahony R. and Andrews B. (2005). Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16: 531–547 · Zbl 1092.90036 · doi:10.1137/040605266
[2] Attouch H. and Soubeyran A. (2006). Inertia and reactivity in decision making as cognitive variational inequalities. J. Convex Anal. 13: 207–224 · Zbl 1138.91370
[3] Attouch, H., Soubeyran, A.: From procedural rationality to routines: a worthwhile to move approach of satisficing with not too much sacrificing. Submitted paper (2005)
[4] Attouch H. and Teboulle M. (2004). Regularized Lotka–Volterra Dynamical system as continuous proximal-like method in optimization. J. Optim. Theory Appl. 121: 541–580 · Zbl 1076.90053 · doi:10.1023/B:JOTA.0000037603.51578.45
[5] Benedetti, R., Risler, J.-J.: Real Algebraic and Semialgebraic Sets. Hermann, Éditeurs des sciences et des Arts, Paris (1990) · Zbl 0694.14006
[6] Bochnak J., Coste M. and Roy M.-F. (1998). Real Algebraic Geometry. Springer, Heidelberg · Zbl 0912.14023
[7] Bolte J., Daniilidis A. and Lewis A. (2007). The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAMJ. Optimization 17: 1205–1223 · Zbl 1129.26012 · doi:10.1137/050644641
[8] Bolte J., Daniilidis A. and Lewis A. (2006). The Morse-Sard theorem for non-differentiable subanalytic functions. J. Math. Anal. Appl. 321: 729–740 · Zbl 1160.49301 · doi:10.1016/j.jmaa.2005.07.068
[9] Clarke, F.H., Ledyaev, Yu., Stern, R.I., Wolenski, P.R.: Nonsmooth analysis and control theory. Graduate texts in Mathematics, vol. 178. Springer, New-York (1998) · Zbl 1047.49500
[10] Combettes P. and Pennanen T. (2004). Proximal methods for cohypomonotone operators. SIAM J. Control Optim. 43: 731–742 · Zbl 1078.47003 · doi:10.1137/S0363012903427336
[11] Coste, M.: An introduction to o-minimal geometry. RAAG Notes, 81 p., Institut de Recherche Mathématiques de Rennes (1999)
[12] Miller C. and Dries L. (1996). Geometric categories and o-minimal structures. Duke Math. J. 84: 497–540 · Zbl 0889.03025 · doi:10.1215/S0012-7094-96-08416-1
[13] Goudou, X., Munier, J.: The heavy ball with friction method: the quasiconvex case. Submitted (2005) · Zbl 1151.37326
[14] Haraux, A.: A hyperbolic variant of Simon’s convergence theorem. Evolution equations and their applications in physical and life sciences (Bad Herrenalb, 1998), Lecture Notes in Pure and Appl. Math., vol. 215, pp. 255-264. Dekker, New York (2001)
[15] Kaplan A. and Tichatschke R. (1998). Proximal point methods and nonconvex optimization. J. Glob. Optim. 13: 389–406 · Zbl 0916.90224 · doi:10.1023/A:1008321423879
[16] Kurdyka K. (1998). On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier 48: 769–783 · Zbl 0934.32009
[17] Kurdyka K. and Parusinski A. (1994). w f -stratification of subanalytic functions and the Łjasiewicz inequality. C. R. Acad. Paris 318: 129–133 · Zbl 0799.32007
[18] Lemaire, B.: The proximal algorithm. New methods in optimization and their industrial uses, Pau/Paris, pp. 73-87 (1987). Internat. Schriftenreihe Numer. Math., vol. 87. Birkhäuser, Basel (1989)
[19] Łjasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. In: Ĺes Équations aux Dérivées Partielles, Editions du Centre National de la Recherche Scientifique, Paris, pp. 87–89 (1963)
[20] Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. (French) Rev. Française Informat. Recherche Opérationnelle, vol. 4, Ser. R-3 154–158 (1970)
[21] Miettinen M., Mkel M.M. and Haslinger J. (1995). On numerical solution of hemivariational inequalities by nonsmooth optimization methods. J. Glob. Optim. 6: 401–425 · Zbl 0837.49007 · doi:10.1007/BF01100086
[22] Mifflin R. and Sagastizabal C. (2004). \({\mathcal{VU}}\) -smoothness and proximal point results for some nonconvex functionsOptim. Methods Softw. 19: 463–478 · Zbl 1097.90059 · doi:10.1080/10556780410001704902
[23] Mordukhovich, B.: Maximum principle in the problem of time optimal response with nonsmooth constraints. J. Appl. Math. Mech. 40, 960–969 (1976); translated from Prikl. Mat. Meh. 40, 1014–1023 (1976) · Zbl 0362.49017
[24] Mordukhovich, B.: Variational analysis and generalized differentiation. Grundlehren der Mathematischen, Wissenschaften, vol. 330. Springer, Heidelberg (1998) · Zbl 0923.49013
[25] Palis, J., De Melo, W.: Geometric theory of dynamical systems. An introduction (Translated from the Portuguese by A. K. Manning). Springer, New York (1982) · Zbl 0491.58001
[26] Pennanen T. (2002). Local convergence of the proximal point algorithm and multiplier methods without monotonicity. Math. Oper. Res. 27: 170–191 · Zbl 1082.90582 · doi:10.1287/moor.27.1.170.331
[27] Rockafellar R.T. (1976). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1: 97–116 · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[28] Rockafellar, R.T., Wets, R.: Variational Analysis. Grundlehren der Mathematischen, Wissenschaften, vol. 317. Springer, Heidelberg (1998) · Zbl 0888.49001
[29] Simon L. (1983). Asymptotics for a class of non-linear evolution equations, with applications to geometric problems. Ann. Math. 118: 525–571 · Zbl 0549.35071 · doi:10.2307/2006981
[30] Spingarn J.E. (1981). Submonotone mappings and the proximal point algorithm. Numer. Funct. Anal. Optim. 4: 123–150 · Zbl 0495.49025 · doi:10.1080/01630568208816109
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.