Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.