What is it about?
Finding the best solution is called optimization. We propose a new highly unconventional approach to solve this problem, which could deliver a faster and/or cheaper optimising machine than those currently available. Our approach is based on mathematics of the so-called complex systems and on the phenomenon of dynamical chaos induced by time delay.
Featured Image
Why is it important?
Traditionally, optimization has been done by digital computers, which can be insufficiently fast if the problem is too complex. More recently, much faster quantum computers have been developed, but these are based on expensive and challenging technology and are not easily available. Note that none of the existing methods can guarantee the very best solution out of all possible options, although they can considerably improve the initial guess for a good solution. To solve the same problem, we propose a very different mathematical principle, which could be implemented in faster analog (non-digital) devices, but without expensive quantum technology. Specifically, our approach would give an advantage over algorithm-based tools because it does not require making a new decision at every step based on the outcome of the previous step, where zillions of such steps are needed to achieve a solution. In contrast to algorithmic approaches, in our case almost the whole process is spontaneous, more or less like in a grandfather clock -- only with a more sophisticated design leading to much more complex behavior. This feature makes it similar to quantum computers where the behaviour is also quite spontaneous and for this reason (among others) enables much faster solution than digital computers. However, the device implementing our principle does not need to be quantum, and hence could be much cheaper to make.
Perspectives
BACKGROUND. Mathematics, and specifically theory of dynamical systems, has always been behind optimization tools. Both most popular approaches, simulated annealing and quantum annealing, are based on gradient descent describable by a very simple differential equation, which can be implemented e.g. in an analog electronic circuit and describes spontaneous evolution of the system towards the minimum of the cost function. However, while gradient descent can improve a solution that is guessed initially, corresponding to a local minimum, this might not be the very best solution corresponding to the lowest of all minima. To ensure that all available minima are analysed and the lowest one is found, the traditional approach is to algorithmically emulate random forces affecting the model, and to decide at each step where the system should be pushed next depending on the outcome of the previous step. This is no longer equivalent to spontaneous behavior of the system, cannot be implemented in an analog device, and requires digital computation, which might not be sufficiently fast for difficult practical problems. OUR METHOD. We propose how to ensure that the system explores all available minima spontaneously, i.e. without the need for an algorithm. To achieve this, dynamical chaos could be a substitute for a random force. With this, for a practical application, we need chaos with required properties to appear in a predictable and reliable way. However, highly non-linear systems are notorious for being unpredictable, such that a seemingly minor change in the equations can lead to a dramatic change in the behavior. Obviously, for our idea to work, our method should not be sensitive to the shape of the cost function. To generate chaos, we utilise a time delay. This might seem a highly counter-intuitive move, since normally introducing a delay in a non-linear system makes an already complex situation so much more complex. Particularly, it is usually impossible to predict how the increase of delay would change the behavior of a nonlinear system. However, we hypothesize and verify that for a certain broad class of the systems with delay, an increase of the delay can lead to quite predictable robust results, which would be largely independent of the specifics of the equations. Such systems can be obtained by taking a standard gradient dynamical system and replacing the argument of its right-hand side with a delayed state variable. We then utilize this predictable effect from the time delay to generate chaos and to compel the system to visit all minima of the cost function. Since this behavior is fully spontaneous, it can be potentially implemented in an analog machine, which could be faster than digital computers.
Dr. Natalia B. Janson
Loughborough University
Read the Original
This page is a summary of: Optimization with delay-induced bifurcations, Chaos An Interdisciplinary Journal of Nonlinear Science, November 2021, American Institute of Physics,
DOI: 10.1063/5.0058087.
You can read the full text:
Resources
Optimization with delay-induced bifurcations
Open Access article: Natalia B. Janson and Christopher J. Marsden , "Optimization with delay-induced bifurcations", Chaos 31, 113126 (2021) https://doi.org/10.1063/5.0058087
Delay-induced homoclinic bifurcations in modified gradient bistable systems and their relevance to optimization
Open Access article: Natalia B. Janson and Christopher J. Marsden , "Delay-induced homoclinic bifurcations in modified gradient bistable systems and their relevance to optimization", Chaos 31, 093120 (2021) https://doi.org/10.1063/5.0035959 This article explains in more detail mathematical mechanisms behind the optimization principle proposed in the "Optimization with delay-induced bifurcations".
SUPPLEMENTARY NOTE for "Delay-induced homoclinic bifurcations in modified gradient bistable systems and their relevance to optimisation"
This is Supplementary note for: Natalia B. Janson and Christopher J. Marsden , "Delay-induced homoclinic bifurcations in modified gradient bistable systems and their relevance to optimization", Chaos 31, 093120 (2021). It provides some mathematical background behind the analysis of delay-differential equations, specifically stability of fixed points and their bifurcation, and considers an additional example of a system of the same class as the one described in the main paper, only with a different kind of homoclinic bifurcation.
Contributors
The following have contributed to this page
