Submodular Function Minimization and Polarity
This provides an alternative theoretical framework and practical tool for optimization problems involving set functions, though it appears incremental as it builds on existing methods like the Lovász extension.
The paper tackles the problem of minimizing submodular and non-submodular set functions by developing a polar approach that provides outer polyhedral approximations for their epigraphs. It proves exactness for submodular functions and demonstrates computational effectiveness through experiments showing these approximations work as cutting planes.
Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lovász extension. The polar approach provides an alternative proof for the convex hull description of the epigraph of a submodular function. Computational experiments show that the inequalities from outer approximations can be effective as cutting planes for solving submodular as well as non-submodular set function minimization problems.