2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Just a minor correction: piece-wise linear functions are Lipschitz continuous. In fact, the Lipschitz constant is bounded by the maximum norm of the linear functions. Then, it is easy to see that the Lovasz extension is convex and Lipschitz $\endgroup$ Feb 19, 2020 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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