6
$\begingroup$

In my research on optimization research, I thought about attempts to bridge gradient descent (deterministic standard) via a dynamical system of sorts, meaning if I look at the iterations of Gradient Descent as the discrete orbit of some dynamical system in the phase space (maybe a Poincare map here...) So I was wondering if someone could possibly tell me if it is possible to use the lense of dynamical systems to characterize steepest descent in such a way that Hamiltonian dynamics and possibly perturbative analysis works? Analysis of the stable and unstable manifolds here? Maybe asymptotic analysis and orbits in the phase space like attractors and the center focus problem? I thank all helpers.

$\endgroup$
  • 1
    $\begingroup$ This is something people are indeed aware of, see for example scicomp.stackexchange.com/q/14195/1804, but I don't think anybody has tried to apply the full brunt of dynamical systems theory to it. (It's not quite clear to me what kind of question of interest in optimization this could answer that can't be tackled by standard methods.) $\endgroup$ – Christian Clason Oct 24 '16 at 16:53
  • $\begingroup$ @ChristianClason: Thank you, I was wondering about the volume of attractors (sets which converge to critical points) and possibly the cover spaces of the space of critical points $\endgroup$ – kroner Oct 24 '16 at 16:57
  • 1
    $\begingroup$ That would indeed be interesting. $\endgroup$ – Christian Clason Oct 24 '16 at 16:59
  • 1
    $\begingroup$ I highly recommend the following book: Stuart, Andrew, and Anthony R. Humphries. Dynamical systems and numerical analysis. Vol. 2. Cambridge University Press, 1998. $\endgroup$ – Nawaf Bou-Rabee Oct 24 '16 at 17:18
11
+50
$\begingroup$

This topic has long history. Here are some references:

  1. Bloch, Anthony M. "Steepest descent, linear programming and Hamiltonian flows." Contemp. Math. AMS 114 (1990): 77-88.

  2. Brockett, Roger W. Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems. Decision and Control, 1988., Proceedings of the 27th IEEE Conference on. IEEE, 1988.

  3. Helmke, Uwe, and John B. Moore. Optimization and Dynamical Systems. Springer Science & Business Media, 2012.

Also, there are plenty of physically relevant PDEs which can be seen as implementing gradient descent in some Banach space. For example, see

  1. Ambrosio, Luigi, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008.

  2. Terry Tao, The Euler-Arnold equation, June 2010.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

I suggest looking at the function to be optimized as a local Lyapunov function for the dynamical system defined by the search procedure. There must be some literature on this point of view, but my knowledge is limited.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.