X entropy for optimisation

At Gregynog, with mounds of snow still visible in the surrounding hills, not to be confused with the many sheep dotting the fields(!), Owen Jones gave a three hour lecture on simulation for optimisation, which is a less travelled path when compared with simulation for integration. His second lecture covered cross entropy for optimisation purposes. (I had forgotten that Reuven Rubinstein and Dirk Kroese had put forward this aspect of their technique in the very title of their book. As “A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning”.) The X entropy approaches pushes for simulations restricted to top values of the target function, iterating to find the best parameter in the parametric family used for the simulation. (Best to be understood in the Kullback sense.) Now, this is a wee bit like simulated annealing, where lots of artificial entities have to be calibrated in the algorithm, due to the original problem being unrelated to an specific stochastic framework. X entropy facilitates concentration on the highest values of the target, but requires a family of probability distributions that puts weight on the top region. This may be a damning issue in large dimensions. Owen illustrated the approach in the case of the travelling salesman problem, where the parameterised distribution is a Markov chain on the state space of city sequences. Further, if the optimal value of the target is unknown, avoiding getting stuck in a local optimum may be tricky. (Owen presented a proof of convergence for a temperature going to zero slowly enough that is equivalent to a sure exploration of the entire state space, in a discrete setting, which does not provide a reassurance in this respect, as the corresponding algorithm cannot be implemented.) This method falls into the range of methods that are doubly stochastic in that they rely on Monte Carlo approximations at each iteration of the exploration algorithm.

During a later talk, I tried to recycle one of my earlier R codes on simulated annealing for sudokus, but could not find a useful family of proposal distributions to reach the (unique) solution. Using a mere product of distributions on each of the free positions in the sudoku grid only led me to a penalty of 13 errors…

1    2    8    5    9    7    4    9    3
7    3    5    1    2    4    6    2    8
4    6    9    6    3    8    5    7    1
2    7    5    3    1    6    9    4    8
8    1    4    7    8    9    7    6    2
6    9    3    8    4    2    1    3    5
3    8    6    4    7    5    2    1    9
1    4    2    9    6    3    8    5    7
9    5    7    2    1    8    3    4    6

It is hard to consider a distribution on the space of permutations, 𝔖⁸¹.

who’s that travelling salesman path?!

a trip back in time [and in Rouen]

On Monday, I took part in a celebration of the remarkable career of a former colleague of mine in Rouen, Gérard Grancher, who is retiring after a life-long position as CNRS engineer in the department of maths of the University of Rouen, a job title that tells very little about the numerous facets of his interactions with mathematics, from his handling of all informatics aspects in the laboratory to his support of all colleagues there, including fresh PhD students like me in 1985!, to his direction of the CNRS lab in 2006 and 2007 at a time of deep division and mistrust, to his numerous collaborations on statistical projects with local actors, to his Norman federalism in bringing the maths departments of Caen and Rouen into a regional federation, to an unceasing activism to promote maths in colleges and high schools and science fairs all around Normandy, to his contributions to professional training in statistics for CNRS agents, and much, much more… Which explains why the science auditorium of the University of Rouen was packed with mathematicians and high schools maths teachers and friends! (The poster of the day was made by Gérard’s accomplices in vulgarisation, Élise Janvresse and Thierry Delarue, based on a sample of points randomly drawn from Gérard’s picture, maybe using a determinantal process, and the construction of a travelling salesman path over those points.)

This was a great day with mostly vulgarisation talks (including one about Rasmus’ socks..!) and reminiscences about Gérard’s carreer at Rouen. As I had left the university in 2000 to move to Paris-Dauphine, this was a moving day as well, as I met with old friends I had not seen for ages, including our common PhD advisor, Jean-Pierre Raoult.

This trip back in time was also an opportunity to (re-)visit the beautifully preserved medieval centre of Rouen, with its wooden houses, Norman-style, the numerous churches, including Monet‘s cathedral, the Justice Hall… Last time I strolled those streets, George Casella was visiting!

travelling from pub to pub [in a straight line]

Above is the solution produced by a team at the University of Waterloo to the travelling salesman problem of linking all pubs in the UK (which includes pubs in Northern Ireland as well as some Scottish islands—even though I doubt there is no pub at all on the Island of Skye! They also missed a lot of pubs in Glasgow! And worst gaffe of all, they did not include the Clachaigh Inn, probably the best pub on Earth…). This path links over 24 thousand pubs, which is less than the largest travelling salesman problem solved at the current time, except that this case used the exact distances provided by Google maps. Of course, it would somehow make more sense to increase the distances by random amounts as the pub visits increase, unless the visitor sticks to tonic. Or tea.