Abstract

A continuous-time gradient system is a dynamical system of the form dx/dt = – grad f(x), where grad f denotes the gradient of the differentiable real-valued function f, whose domain is the Euclidean space R^n or more generally a (smooth) manifold M. A discrete-time gradient system takes the form x_{k+1} = x_k – s grad f(x), where the step size s can be chosen by various means.

Gradient systems are useful in solving various optimization-related problems, e.g., in principal component analysis, optimal control, balanced realizations, ocean sampling, noise reduction, pose estimation or the Procrustes problem.

In this talk, we present recent (and less recent) results pertaining to the convergence of the solutions of gradient systems. In particular, we are interested in reasonably weak conditions, sufficient for the solution trajectories to have at most one accumulation point.

In a similar spirit, we discuss the notion of “accelerated” descent methods. This notion was formalized only recently, but the principles have been in hiding in several places, notably the work of D. Bertsekas and E. Polak. The idea is as follows. If T denotes a descent iteration for f, we say that a sequence {x_k} is T-accelerated if the decrease of f between x_k and x_{k+1} is at least as good as the decrease of f between x_k and T(x_k). We address the following question: Assume that all the accumulation points of every sequence {y_k} satisfying y_{k+1} = T(y_k) are critical points of f; what can be said about the accumulation points of T-accelerated sequences? This question appears in the analysis of several numerical algorithms.