Recently, I had the great pleasure to spend few hours with the British mathematician Terry Lyons. Terry is a fascinating mind. My first contact with him goes back to my postdoc in his research group, ten years ago, when we created the Computational Rough Paths project (CoRoPa). We discussed, as in the old times, with shared enthusiasm, various questions ranging from pure mathematics to concrete computer science.
Terry and his collaborators developed in the past decades a whole universe around iterated integrals and differential equations driven by rough signals. The dogma of this theory is that signals are important via their consequences, that most of their consequences are modeled with differential equations, and that the solution of such equations are well described with sequences of iterated integrals (the more the driving signal is rough, the more iterated integrals we need to describe the solution of the equation). Moreover, such sequences have an exponential decay, giving a meaning to truncation. The most striking recent achievement in this theory is the Uniqueness for the signature of a path of bounded variation and the reduced path group, a result by Hambly and Lyons published in 2010 in the Annals of Mathematics. The signature of a path on a time interval is precisely the sequence of its iterated integrals on the interval. One of the most practical question posed in this non-linear universe is the inverse problem of the reconstruction of a signal from its signature. Terry believes that a branch-and-bound algorithm may be used, thanks to the power of computers.
The concept of branch-and-bound algorithms is very general and should be known by every mathematician. It is likely that you already know a version of it. Suppose that we would like to minimize a real function \( {f} \) defined on a set \( {S} \). A branch-and-bound algorithm consists in two ingredients to compute \( {\min_S f} \):
- branch: a branching procedure, which splits \( {S} \) into a couple of disjoint subsets \( {S=S_1\cup S_2} \). Applied recursively, it produces a tree structure
- bound: a bounding procedure, which computes an upper and lower bound for \( {\min_{S_i} f} \). By navigating the tree, one can then discard some of the branches according to the bounds (we prune the tree).
Branch-and-bound algorithms are used for many complex optimization problems such as for the famous Traveling Salesman Problem. They are also used in the implementation of artificial intelligence in games such as chess (\( {(\alpha,\beta)} \)-pruning).
Leave a Comment