Lipshitz Constant of the convex extension of a submodular function

2012-05-01T14:43:08Z

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 by polkjh for Lipshitz Constant of the convex extension of a submodular function

2013-03-10T05:07:08Z

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.

Lipshitz Constant of the convex extension of a submodular function - MathOverflow

Lipshitz Constant of the convex extension of a submodular function

Answer by polkjh for Lipshitz Constant of the convex extension of a submodular function