Like graph cuts, semidefinite relaxation approaches have recently been shown to be successful candidates for solving discrete optimization problems in many fields of research. While these relaxations exhibit similar characteristics as linear relaxations (the global optimum can always be computed in polynomial time), the quality of the obtained solutions is often better than that of other relaxations. Moreover, the corresponding framework is usually less restrictive than comparable approaches concerning possible objective functions and constraints. We demonstrate which types of optimization problems can be tackled by semidefinite relaxation, introduce the general relaxation framework, and discuss its strengths and shortcomings. Methods to reduce the problem size are provided, and applications to different computer vision problems presented.
Copyright. All Rights Reserved.