Top

previous article Three-step alternating iterations for index 1 a...

next article Chebyshev-Legendre spectral method and inverse ...

Hint

Swipe to navigate through the articles of this issue

13-07-2019 | Original Paper | Issue 2/2020

A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem

Journal:: Numerical Algorithms > Issue 2/2020

Authors:: Cristian Daniel Alecsa, Szilárd Csaba László, Adrian Viorel

» Get access to the full-text

Important notes

This work was supported by a grant of Ministry of Research and Innovation, CNCS -UEFISCDI, project number PN-III-P1-1.1-TE-2016-0266, within PNCDI III.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

We investigate an algorithm of gradient type with a backward inertial step in connection with the minimization of a nonconvex differentiable function. We show that the generated sequences converge to a critical point of the objective function, if a regularization of the objective function satisfies the Kurdyka-Łojasiewicz property. Further, we provide convergence rates for the generated sequences and the objective function values formulated in terms of the Łojasiewicz exponent. Finally, some numerical experiments are presented in order to compare our numerical scheme with some algorithms well known in the literature.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Aujol, J.-F., Dossal, C.H., Rondepierre, A.: Optimal convergence rates for Nesterov acceleration. arXiv: 1805.05719

Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116(1-2), 5–16 (2009) MathSciNetMATH

Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010) MathSciNetMATH

Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Program. 137(1-2), 91–129 (2013) MathSciNetMATH

Attouch, H., Chbani, Z., Peypouquet, J., Redont, P.: Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Math. Program. 168(1-2), 123–175 (2018) MathSciNetMATH

Bégout, P., Bolte, J., Jendoubi, M.A.: On damped second-order gradient systems. J. Differ. Equ. 259, 3115–3143 (2015) MathSciNetMATH

Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. Series A 146(1-2), 459–494 (2014) MathSciNetMATH

Bolte, J., Daniilidis, A., Lewis, A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2006) MathSciNetMATH

Bolte, J., Daniilidis, A., Lewis, A., Shiota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556–572 (2007) MathSciNetMATH

10.

Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Am. Math. Soc. 362(6), 3319–3363 (2010) MATH

11.

Boţ, R. I., Csetnek, E.R., László, S.C.: Approaching nonsmooth nonconvex minimization through second-order proximal-gradient dynamical systems. J. Evol. Equ. 18(3), 1291–1318 (2018) MathSciNetMATH

12.

Boţ, R.I., Csetnek, E.R., László, S.C.: An inertial forward-backward algorithm for minimizing the sum of two non-convex functions. Euro J. Comput. Optim. 4(1), 3–25 (2016) MathSciNetMATH

13.

Boţ, R. I., Csetnek, E.R., László, S.C.: A second order dynamical approach with variable damping to nonconvex smooth minimization. Applicable Analysis. https://doi.org/10.1080/00036811.2018.1495330 (2018)

14.

Boţ, R.I., Nguyen, D.-K.: The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. arXiv: 1801.01994

15.

Chambolle, A., Dossal, C. h.: On the convergence of the iterates of the fast iterative shrinkage/thresholding algorithm. J. Optim. Theory Appl. 166(3), 968–982 (2015) MathSciNetMATH

16.

Combettes, P.L., Glaudin, L.E.: Quasinonexpansive iterations on the affine hull of orbits: From Mann’s mean value algorithm to inertial methods. Siam Journal on Optimization 27(4), 2356–2380 (2017) MathSciNetMATH

17.

Frankel, P., Garrigos, G., Peypouquet, J.: Splitting methods with variable metric for Kurdyka–Łojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165(3), 874–900 (2015) MathSciNetMATH

18.

Ghadimi, E., Feyzmahdavian, H.R., Johansson, M.: Global convergence of the heavy-ball method for convex optimization. In: 2015 IEEE European Control Conference (ECC), pp. 310–315 (2015)

19.

Kurdyka, K.: On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier (Grenoble) 48(3), 769–783 (1998) MathSciNetMATH

20.

László, S.C.: Convergence rates for an inertial algorithm of gradient type associated to a smooth nonconvex minimization. arXiv: 1811.09616

21.

Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. Found. Comput. Math. 2018, 1–34 (2018) MATH

22.

Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels, Les É,quations aux Dérivées Partielles, Éditions du Centre National de la Recherche Scientifique Paris, pp. 87–89 (1963)

23.

Nesterov, Y.E.: A method for solving the convex programming problem with convergence rate O(1/ k ²). (Russian) Dokl. Akad. Nauk SSSR 269(3), 543–547 (1983) MathSciNet

24.

Nesterov, Y.: Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers, Dordrecht (2004) MATH

25.

Polheim, H.: Examples of objective functions, Documentation for Genetic and Evolutionary Algorithms for use with MATLAB : GEATbx version 3.7, http://www.geatbx.com

26.

Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. U.S.S.R. Comput. Math. Math. Phys. 4(5), 1–17 (1964)

27.

Rockafellar, R.T., Wets, R. J. -B.: Variational analysis fundamental principles of mathematical sciences, vol. 317. Springer, Berlin (1998)

28.

Su, W., Boyd, S., Candes, E.J.: A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. J. Mach. Learn. Res. 17, 1–43 (2016) MathSciNetMATH

29.

Sun, T., Yin, P., Li, D., Huang, C., Guan, L., Jiang, H.: Non-ergodic convergence analysis of heavy-ball algorithms. arXiv: 1811.01777

Title: A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem
Authors:: Cristian Daniel Alecsa
Szilárd Csaba László
Adrian Viorel
Publication date: 13-07-2019
DOI: https://doi.org/10.1007/s11075-019-00765-z
Publisher: Springer US
Journal: Numerical Algorithms
Issue 2/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265

Premium Partner

Image Credits

Springer Professional

Hint

Swipe to navigate through the articles of this issue

Publisher’s note

Abstract

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2020

Further comment on another hybrid conjugate gradient algorithm for unconstrained optimization by Andrei

Low-rank updates and divide-and-conquer methods for quadratic matrix equations

The global convergence of the BFGS method under a modified Yuan-Wei-Lu line search technique

Three-step alternating iterations for index 1 and non-singular matrices

Parallelization, initialization, and boundary treatments for the diamond scheme

Weak and strong convergence theorems for solving pseudo-monotone variational inequalities with non-Lipschitz mappings

Premium Partner