Lipshitz Constant of the convex extension of a submodular function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T13:17:57Z http://mathoverflow.net/feeds/question/95671 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95671/lipshitz-constant-of-the-convex-extension-of-a-submodular-function Lipshitz Constant of the convex extension of a submodular function Guy Adini 2012-05-01T14:43:08Z 2013-03-10T05:07:08Z <p>The title says it all :)</p> <p>Given a submodular function (take the rank function of a matroid, for a concrete example) <code>$f:\{0,1\}^n\rightarrow \mathbb{R}$</code>, 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). </p> <p>One such way of calculating an extension is given here: <a href="http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture21-22.pdf" rel="nofollow">http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture21-22.pdf</a></p> <p>My question is what is the relationship between the Lipshitz constant of $f$ and $g$?</p> <p>Quite obviously, they don't have to be equal, and it might depend on the way which we define the extension.</p> <p>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.</p> <p>Thanks, Guy</p> http://mathoverflow.net/questions/95671/lipshitz-constant-of-the-convex-extension-of-a-submodular-function/124129#124129 Answer by polkjh for Lipshitz Constant of the convex extension of a submodular function polkjh 2013-03-10T05:07:08Z 2013-03-10T05:07:08Z <p>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.</p>