Graph-based quadratic optimization: A fast evolutionary approach

• Published in: Computer vision and image understanding 2011-07, Vol.115 (7), p.984-995
• Main Authors: Rota Bulò, Samuel, Pelillo, Marcello, Bomze, Immanuel M.
• Format: Article
• Language: English
• Subjects: Algorithms; Dynamics; Evolutionary; Graph-based problems; Matching; Mathematical models; Optimization; Population dynamics; Quadratic optimization
• ISSN: 1077-3142; 1090-235X
• DOI: 10.1016/j.cviu.2010.12.004

► We propose a new evolutionary dynamics for standard quadratic optimization. ► Our dynamics is a order of magnitude faster than standard approaches. ► We prove convergence and other properties pertaining to our dynamics. ► Experiments: tree and image matching, image registration and segmentation. Quadratic optimization lies at the very heart of many structural pattern recognition and computer vision problems, such as graph matching, object recognition, image segmentation, etc., and it is therefore of crucial importance to devise algorithmic solutions that are both efficient and effective. As it turns out, a large class of quadratic optimization problems can be formulated in terms of so-called “standard quadratic programs” (StQPs), which ask for finding the extrema of a quadratic polynomial over the standard simplex. Computationally, the standard approach for attacking this class of problems is to use replicator dynamics, a well-known family of algorithms from evolutionary game theory inspired by Darwinian selection processes. Despite their effectiveness in finding good solutions in a variety of applications, however, replicator dynamics suffer from being computationally expensive, as they require a number of operations per step which grows quadratically with the dimensionality of the problem being solved. In order to avoid this drawback, in this paper we propose a new population game dynamics (I nI mD yn) which is motivated by the analogy with infection and immunization processes within a population of “players.” We prove that the evolution of our dynamics is governed by a quadratic Lyapunov function, representing the average population payoff, which strictly increases along non-constant trajectories and that local solutions of StQPs are asymptotically stable (i.e., attractive) points. Each step of I nI mD yn is shown to have a linear time/space complexity, thereby allowing us to use it as a more efficient alternative to standard approaches for solving StQPs and related optimization problems. Indeed, we demonstrate experimentally that I nI mD yn is orders of magnitude faster than, and as accurate as, replicator dynamics on various applications ranging from tree matching to image registration, matching and segmentation.