Press "Enter" to skip to content

Month: October 2011

Branch and bound

Multidimensional Stochastic Processes as Rough Paths book coverSystem Control and Rough Paths book cover"An introduction to the Geometry of Stochastic Flows" book cover

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

Tectonique des plaques

How professors spend their time
L’enseignement supérieur français subit des restructurations importantes depuis quelques années. Le dogme ambiant semble être la création de grosses entités à tous les niveaux : instituts, fédérations, PRES, Labex, Idex, etc. Ces nouvelles structures sont censées augmenter la visibilité et favoriser les économies d’échelle. Elles ont en tout cas le mérite de faire bouger les frontières, de remettre en cause les vieilles habitudes figées. Dans quelques dizaines d’années, le mouvement sera peut-être inverse. On louera alors l’efficacité des petites structures, débarrassées des lourdeurs chronophages et énergivores de la complexité bureaucratique. Ce mouvement de balancier, qui ponctue la vie des communautés, a toujours existé. On peut y voir l’expression de la vie dynamique, qui s’oppose à la mort statique. À défaut de système parfait, on fabrique un va et vient. Chaque génération contribue à sa manière au mouvement du moment, y verse ses illusions, ses craintes, ses espoirs, mais aussi son pragmatisme et ses idéologies. Pourtant, la plupart des universitaires n’aspirent qu’à une seule chose : trouver le temps d’exercer leur métier dans les meilleures conditions !

Leave a Comment
Syntax · Style · .