Is it possible to reliably generate a particular approximation of an ideal knot via a simulated annealing approach? - MathOverflow

Is it possible to reliably generate a particular approximation of an ideal knot via a simulated annealing approach?

2011-09-27T19:17:55Z

Say I take a cord, tie a loose knot in three-dimensional space, and pull tightly on the ends to generate an approximation of an ideal knot. If the cord has a fixed knot topology and a random initial configuration in space, are there any conditions under which I am guaranteed to generate a particular ideal knot approximation? In other words, if I perform something akin to simulated annealing to approximate the ideal knot, is it possible for me to always arrive at the same final state (whatever that may be) within some small error?

[Sept. 29th, 2011] - Are there any conditions/constraints under which I might be able to reliably achieve some local (or global) minima in the energy landscape of a knot?

Answer by Joseph O'Rourke for Is it possible to reliably generate a particular approximation of an ideal knot via a simulated annealing approach?

2011-09-27T20:31:21Z

I suspect what you are seeking is not known. One of the experts in this area is Jason Cantarella, who coauthored (with R. Kusner and J. Sullivan) one of the definitive papers on this topic, "On the minimum ropelength of knots and links," Inventiones Mathematicae, Volume 150, Number 2, 257-286, 2002; Springer link). Jason has developed software that he calls RidgeRunner which implements a rope-length minimization, knot-tightening procedure. (I cannot speak to the details of his software, in particular, I don't know if it is "akin to simulated annealing.") He maintains a wonderful web page with (Quicktime) movies of his minimizer approaching what you call the "ideal knot" for many (more than 100!) knots and links. Here, for example, is the endpoint of his optimizer for $8_5$:

Update. See the just-released paper, "The Shapes of Tight Composite Knots," arXiv:1110.3262 (math.DG), by Jason Cantarella and Al LaPointe and Eric Rawdon, for a description of the RidgeRunner software mentioned above. It "proceeds by constrained gradient descent," and "is designed to stop at local minima of the ropelength function." They reduce the probability of "false local minima" with several strategies. Their dataset now contains almost 1000 knots and links.

Answer by Jason Cantarella for Is it possible to reliably generate a particular approximation of an ideal knot via a simulated annealing approach?

2012-07-30T19:38:49Z

The only conditions that I know of under which it's absolutely known that gradient flow will converge to a minimum energy state is when the initial configuration is planar. Zheng-Xu He proved this for his renormalized $1/r^2$ potential 'Mobius' energy in The Euler-Lagrange equation and heat flow for the Möbius energy (CPAM 53, 2000). We proved a similar theorem for 'repulsive' energies on planar polygons in An energy-driven approach to linkage unfolding (SOCG 2004).

For a nonplanar configuration, you're right to think that there's a general theorem that ``simulated annealing has a positive probability of converging to the global minimum" which applies to these problems, but it's ineffective in practice. The configuration space is in practice very high dimensional (3 x number of vertices) and reducing an energy functional such as ropelength generally requires a coordinated global motion of these vertices, so it's quite rare to generate such a move randomly. AFAIK, nobody knows how to estimate the probability of convergence under these circumstances, so there's no hard information on how long to run an annealer.

FWIW, RidgeRunner really isn't an annealer: it generates 'coordinated motions' for tightening deterministically using a linear algebra algorithm to deflect the gradient of length for a polygon into a ropelength-decreasing direction using the active distance and curvature constraints. The algorithm is described in Knot Tightening By Constrained Gradient Descent (Experimental Math, 2011).

You're welcome to play with RidgeRunner yourself if you'd like to try tightening: the software can be downloaded at link text.