Abstract
We consider the gradient system \(\dot x(t)+\nabla\phi(x(t))=0\) and the so-called heavy ball with friction dynamical system \(\ddot x(t) +\lambda\dot x(t)+\nabla\phi(x(t))=0\) , as well as an implicit discrete (proximal) version of it, and study the asymptotic behavior of their solutions in the case of a smooth and quasiconvex objective function Φ. Minimization properties of trajectories are obtained under various additional assumptions. We finally show a minimizing property of the heavy ball method which is not shared by the gradient method: the genericity of the convergence of each trajectory, at least when Φ is a Morse function, towards local minimum of Φ.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alvarez F. (2000). On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J. Control Optim. 38(4): 1102–1119
Alvarez F. and Attouch H. (2001). An inertial proximal method for maximal monotone operators via dicretization of a nonlinear oscillator with damping. Wellposedness in optimization and related topics. Set Valued Anal. 9(1–2): 3–11
Arrow K. and Debreu G. (1954). Existence of an equilibrium for a competitive economy. Econometrica 22: 265–290
Attouch H., Cabot A. and Redont P. (2002). The dynamics of elastic shocks via epigraphical regularization of a differential inclusion. Barrier and penalty approximations. Adv. Math. Sci. Appl. 12(1): 273–306
Attouch H. and Czarnecki M. (2002). Asymptotic control and stabilization of nonlinear oscillators with non-isolated equilibria. J. Differ. Equ. 179: 278–310
Attouch H., Goudou X. and Redont P. (2000). The heavy ball with friction method, I. The continuous dynamical system: global exploration of the local minima of real-valued function by asymptotic analysis of a dissipative dynamical system. Commun. Contemp. Math. 2(1): 1–34
Attouch, H., Soubeyran, A.: Inertia and reactivity in decision making as cognitive variational inequalities. J. Convex Anal. 13(2), 207–224 (2006, to appear)
Attouch H. and Teboule M. (2004). Regularized Lotka–Volterra dynamical system as continuous proximal-like method in optimization. J. Optim. Theory Appl. 121(3): 77–106
Aussel D. (1998). Subdifferential properties of quasiconvex and pseudoconvex function, unified approach. J. Optim. Theory Appl. 97: 29–45
Aussel, D.: Contributions en analyse multivoque et en optimisation, thèse hdr. Ph.D. thesis, Université Montpellier 2 (2005)
Aussel D. and Daniilidis A. (2000). Normal characterization of the main classes of quasiconvex analysis. Set Valued Anal. 8: 219–236
Baillon, J.: Un exemple concernant le comportement asymptotique de la solution du problème \(du/dt+\partial\varphi(u)\ni 0\)J. Funct. Anal. 28, 369–376 (1978)
Barron N. and Liu W. (1997). Calculus of variation in L ∞. Appl. Math. Optim. 35: 237–263
Brézis, H.: Opérateurs maximaux monotones et semi-groupes de contraction. Lectures Notes No. 5, North Holland (1973)
Bruck R. (1975). Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. J. Funct. Anal. 18: 15–26
Brunovsky P. and Polàcik P. (1997). The morse-smale structure of generic reaction-diffusion equation in higher space dimension. J. Differ. Equ. 135(1): 129–181
Crouzeix, J.: A review of continuity and differentiability properties of quasiconvex functions on \({\mathbb{R}}^n\) . Research Notes in Mathematics 57, Aubin and Vinter Ed, pp. 18–34 (1982)
Crouzeix, J.P.: Contribution à l’étude des fonctions quasiconvexes. Ph.D. Thesis, Université de Clermont-Ferrand Thèse d’Etat (1977)
Crouzeix, J.-P.: La convexité généralisée en économie mathématique. In: Penot, J. (ed.) Proceedings of 2003 MODE-SMAI Conference, vol. 13, pp. 31–40 (2003)
Dacorogna B. (1989). Direct methods in the calculus of variation. Applied Mathematical Sciences, vol. 78. Springer, Heidelberg
Debreu G. (1959). Theory of Value. Wiley, New York
Debreu G. (1983). Mathematical Economics: Twenty papers. Cambridge University Press, Cambridge
Dussault J.P. (2000). Convergence of implementable descent algorithms for unconstrained optimization. J. Optim. Theory Appl. 104(3): 739–745
Ginsberg W. (1973). Concavity and quasiconcavity in economics. J. Econ. Theory 6: 596–605
Goudou X. and Munier J. (2005). Asymptotic behavior of solutions of a gradient-like integrodifferential Volterra inclusion. Adv. Math. Sci. Appl. 15: 509–525
Guler O. (1991). On the convergence of the proximal point algorithm for convex optimization. SIAM J. Control Appl. 29(2): 403–419
Haraux A. (1990). Systèmes dynamiques dissipatifs et applications. Masson, Paris
Haraux A. and Jendoubi M. (1998). Convergence of solutions of second-order gradient-like systems with analytic nonlinearities. J. Differ. Equ. 144(2): 313–320
Jendoubi, M., Polacik, P.: Non-stabilizing solutions of semilinear hyperbolic and elliptic equations with damping. In: Proceedings Section A: Mathematics, Royal Society of Edinburgh, pp. 1137–1153(17) (2003). http://www.ingentaconnect.com/content/rse/proca/2003/00000133/00000005/art00007
Kiwiel K. and Murty K. (1996). Convergence of the steepest descent method for minimizing quasiconvex functions. J. Optim. Theory Appl. 89(1): 221–226
Lemaire, B.: New methods in optimization and their industrial uses. In: Penot, J. (ed.) Inter. Series of Numerical Math., vol. 87. Birkhauser-Verlag, Basel, pp. 73–87. Symp. Pau and Paris (1989)
Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Française d’Inform. Recherche Opérationnelle, Série R-3 4, 154–158 (1970)
Martinez-Legaz J.E. (2005). Generalized convex duality and its economic applications, handbook of generalized convexity and generalized monotonicity. Nonconvex Optim. Appl. 76: 237–292
Opial Z. (1967). Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73: 591–597
Perko L. (1996). Differential equations and dynamical systems. Springer, Heidelberg
Polyack B. (1964). Some methods of speeding up the convergence of iterative methods. Z. Vylist Math. Fiz. 4: 1–17
Rockafellar R. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14: 877–898
Seeger A. and Volle M. (1995). On a convolution operation obtained by adding level sets: classical and new results. Oper. Res. 29(2): 131–154
Takayama A. (1995). Mathematical Economics. Cambridge University Press, Cambridge
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Goudou, X., Munier, J. The gradient and heavy ball with friction dynamical systems: the quasiconvex case. Math. Program. 116, 173–191 (2009). https://doi.org/10.1007/s10107-007-0109-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0109-5