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.
$\begingroup$
$\endgroup$
3
-
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 ClasonCommented Oct 24, 2016 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$– groupoidCommented Oct 24, 2016 at 16:57
-
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-RabeeCommented Oct 24, 2016 at 17:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
This topic has long history. Here are some references:
Bloch, Anthony M. "Steepest descent, linear programming and Hamiltonian flows." Contemp. Math. AMS 114 (1990): 77-88.
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.
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
Ambrosio, Luigi, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008.
Terry Tao, The Euler-Arnold equation, June 2010.
answered Oct 24, 2016 at 17:40
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ Right, that is something I've seen in first-order methods for non-convex problems, for example people.eecs.berkeley.edu/~walid/projects/MathThesis/thesis.pdf $\endgroup$ Commented Oct 24, 2016 at 16:57
-
$\begingroup$ And, even more recently, arxiv.org/abs/1611.02635. $\endgroup$ Commented Nov 9, 2016 at 8:03