Question

The title says it all :)

Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function $g:[0,1]^n\rightarrow\mathbb{R}$, which agrees with $f$ wherever it is defined (the integral points of the hypercube).

One such way of calculating an extension is given here: http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture21-22.pdf

My question is what is the relationship between the Lipshitz constant of $f$ and $g$?

Quite obviously, they don't have to be equal, and it might depend on the way which we define the extension.

For example, let's say that $n=1$, and that $f(0)=0$, $f(1)=1$. Then $g(x)=x$ and $g(x)=x^2$ are both valid convex extensions, but one has a Lipshitz constant of 1 (as does $x$), and the other has a Lipshitz constant of 2.

Thanks, Guy

Answer 1

There can be multiple convex extensions for a given submodular function, but the Lovasz extension explained in the notes gives the smallest such convex function. And this convex function is not Lipschitz continuous. It is in fact a piece-wise linear function, i.e., a collection of hyperplanes. With some modification to Lovasz extension, many other discrete functions can be extended to convex functions, and they are all composed of hyperplanes again.