Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can any function on $\{0,1\}^n$ be obtained as a restriction of a convex function?
2
-
3$\begingroup$ Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). The implication for your question is that indeed $\bar{f}$ will not have any specific properties. $\endgroup$– Chandra ChekuriApr 22, 2022 at 20:27
-
$\begingroup$ Converted comment into an answer and added link to Dughmi's survey so that the question can essentially be closed. $\endgroup$– Chandra ChekuriApr 23, 2022 at 22:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). See Dughmi's nice survey. The implication for your question is that indeed $\bar{f}$ will not have any specific properties.
-
$\begingroup$ But not necessarily extendible beyond [0,1]^n, right? $\endgroup$– AryehApr 24, 2022 at 8:43
-
$\begingroup$ @EmilJeřábek I think you're right. I thought I recalled some paper with the condition on an $f:\{0,1\}^n\to\mathbb{R}$ having a convex extension, but now I think it was probably any such convex extension. $\endgroup$– AryehApr 24, 2022 at 11:15
-
$\begingroup$ Multilinear extension is not necessarily convex. We considered multilinear extension for submodular functions but it is neither convex nor concave. See for instance Jan Vondrak's thesis theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf. I am not sure if there are other notions of multilinear extensions. $\endgroup$ Apr 24, 2022 at 20:29
-
$\begingroup$ One should be able to extend the convex function from $[0,1]^n$ to all of the space by making it become very steep outside the cube - this is typically done in convex optimization though there may be some technical details to be a bit careful about. $\endgroup$ Apr 24, 2022 at 20:41
-
2$\begingroup$ Yeah, in this case we can directly extend it to a convex function on all of $\mathbb{R}^n$ because the convex closure will be "polyhedral" -- the pointwise maximum of a finite set of affine functions, i.e. $\bar{f}(x) = \max_{j \in J} h_j(x)$. Here affine = linear + constant. Each of those affine functions $h_j$ extends to all of $\mathbb{R}^n$, so the definition of $\bar{f}$ does too. $\endgroup$– usulApr 25, 2022 at 3:31