4
$\begingroup$

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?

$\endgroup$
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$ Apr 22 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$ Apr 23 at 22:29

1 Answer 1

6
$\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). See Dughmi's nice survey. The implication for your question is that indeed $\bar{f}$ will not have any specific properties.

$\endgroup$
6
  • $\begingroup$ But not necessarily extendible beyond [0,1]^n, right? $\endgroup$
    – Aryeh
    Apr 24 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$
    – Aryeh
    Apr 24 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 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 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$
    – usul
    Apr 25 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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