Visualization of a Convex Relaxation for an Integer Optimization Problem

In Computer Vision many problems lead to combinatorial optimization problems. The combinatorial complexity of such problems prevents the computation of a global solution in polynomial time. Therefore one needs to find good approximations for such optimization problems. One reasonable technique is to approximate the original integer optimization problem by a convex relaxation. In the following we sketch the idea of this approach.

Combinatorial Problem

The aim of the shown combinatorial integer optimization problem is to find the global
minimum (depicted as red dot). Often such problems turn out to be NP-hard which prevents
the computation of a global solution in polynomial time.
Combinatorial Problem

Relaxation

To approximate the integer optimization problem the problem can be relaxed. That means
that the original defined integer domain is relaxed to a wider usually real valued domain and
the objective function is constrained to be lower or equal to the objective values on the
integer domain. The main disadvantage is that one can get trapped in a bad local minima.
Combinatorial Problem

Convex Relaxation

To avoid to get trapped in a local minima the objective function along with the domain should be
convex. This allows the efficient computation of the global minimum of the approximation. Of course,
a feasible (often suboptimal) combinatorial solution has to be computed in a post processing.
Combinatorial Problem

C.Schellewald / updated Aug 02, 2005