(BP + DP)/2 = CP: Discrete global optimisation by concurrent propagation 
(Seminars)
13 June 2012
12noon - 1pm
Venue: Room 303.561, City Campus
Department of Computer Science seminar by G Gimel'farb, P Delmas, and R Nicolescu.
Classical discrete global optimisation algorithms: dynamic programming (DP) and belief propagation (BP), built around Bellman's Principle of Optimality, presume well-posed problems with unique solutions. Ill-posed problems, being the most common in practice, are regularised to restore well-posedness. However, typical in a majority of applications heuristic regularisation does not guarantee that a set of multiple solutions for the same optimum is really reduced to a single solution. In the case of an ill-posed problem DP selects an arbitrary solution out of the set, but may not detect the ill-posedness, whereas BP detects the ill-posedness, but may not return the optimal solution.
We propose an alternative, called concurrent propagation (CP) , which combines basic BP and DP ideas and extends DP towards solving both well- and ill-posed problems. The CP determines whether the problem is well- or ill-posed, returns the unique solution of the former, and stores implicitly the entire set of solutions of the latter, while returns the two "most distant" optimal solutions, which can be considered as an envelope of the set. Structural analysis of the set stored could be used eg for developing or improving regularization of the problem. All the three algorithms: BP, CP, and DP - are of the same low time complexity and have similar space complexities. Some advantages of the CP are illustrated in application to the intrinsically ill-posed computational stereovision problem.
Patrice Delmas joined the Department of Computer Science at The University of Auckland in 2001. He holds a PhD from the National Polytechnic Institute Grenoble, France. He has been a convener for the annual Image and Vision Computing New Zealand Conference in 2006 and 2011, and is a winner of the 2011 $100K Spark Entrepreneurial Challenge award.
Georgy Gimel'farb joined the Department of Computer Science at The University of Auckland in 1997. He holds a PhD from the Institute of Cybernetics of the Academy of Sciences of Ukraine, Kiev, Ukraine, and a DSc (Eng) from the Higher Certifying Commission of the USSR, Moscow. He has been a track (2008) and an area chair (2010) of the biannual IAPR International Conference on Pattern Recognition and is a coorganiser of the biannual Joint IAPR International Workshops on Statistical, Syntactic, and Structural Pattern Recognition (S+SSPR 2012).
Patrice and Georgy are co-founders of Intelligent Vision Systems Lab and (together with John Morris) Photogrammetric Lab at the department,
Radu Nicolescu joined the Department of Computer Science at The University of Auckland in 1994. He holds a Doctor in Mathematics (PhD) from the University of Bucharest, Romania. He is a director of the Communication and Information Technology research group, CITR, and has initiated (together with Michael Dinneen) the Parallel and Distributed Computing research profile. Radu was an invited speaker at the 12th International Conference on Membrane Computing, CMC 2011.
