<p>Any real valued function <span class="math-container">$g$</span> defined on <span class="math-container">$\{0,1\}^n$</span> can be extended to a convex function over <span class="math-container">$[0,1]^n$</span> (it is called the convex closure). See Dughmi's nice <a href="https://arxiv.org/abs/0912.0322" rel="noreferrer">survey</a>. The implication for your question is that indeed <span class="math-container">$\bar{f}$</span> will not have any specific properties.</p>

CC BY-SA 4.0
2022-04-24T08:43:49.353Z
But not necessarily extendible beyond [0,1]^n, right?
Aryeh
CC BY-SA 4.0
2022-04-24T11:15:53.273Z
@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.
Aryeh
CC BY-SA 4.0
2022-04-24T20:29:44.230Z
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 https://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf. I am not sure if there are other notions of multilinear extensions.
Chandra Chekuri
CC BY-SA 4.0
2022-04-24T20:41:50.073Z
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.
Chandra Chekuri
CC BY-SA 4.0
2022-04-25T03:31:15.857Z
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.
usul
CC BY-SA 4.0
2022-04-25T10:05:51.620Z
@ChandraChekuri Sorry, you are right. For some reason I thought that the restriction of a multilinear function to a line is linear, but that’s nonsense (it only holds for affine functions).
Emil Jeřábek
CC BY-SA 4.0
2022-04-23T22:28:59.287Z
2022-04-23T22:28:59.287Z
Chandra Chekuri
<p>Suppose I have a real-valued <em>convex</em> function <span class="math-container">$f$</span> on the unit hypercube <span class="math-container">$[0,1]^n$</span>, and let <span class="math-container">$\bar{f}$</span> be its restriction to the integer points <span class="math-container">$\{0,1\}^n$</span>. Does <span class="math-container">$\bar{f}$</span> satisfy any properties, or can any function on <span class="math-container">$\{0,1\}^n$</span> be obtained as a restriction of a convex function?</p>

CC BY-SA 4.0
2022-04-22T20:27:39.270Z
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.
Chandra Chekuri
CC BY-SA 4.0
2022-04-23T22:29:35.187Z
Converted comment into an answer and added link to Dughmi's survey so that the question can essentially be closed.
Chandra Chekuri
<convex-optimization><convex-geometry><submodularity><convex-hull>
Restriction of a convex function to {0, 1}^n
Sean L.
# Restriction of a convex function to {0, 1}^n

(Asked by: username_0 on 2022-04-22)

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?

**Tags:** convex-optimization, convex-geometry, submodularity, convex-hull

> **Comments:**
> **username_1**: 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.  
> **username_1**: Converted comment into an answer and added link to Dughmi's survey so that the question can essentially be closed.  

---

## 1 answers

### Answer by username_1 on 2022-04-23. Score: 6 | Accepted answer

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](https://arxiv.org/abs/0912.0322). The implication for your question is that indeed $\bar{f}$ will not have any specific properties.

> **Comments:**
> **username_2**: But not necessarily extendible beyond [0,1]^n, right?  
> **username_2**: @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.  
> **username_1**: 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 https://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf. I am not sure if there are other notions of multilinear extensions.  
> **username_1**: 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.  
> **username_3**: 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.  
> **username_4**: @ChandraChekuri Sorry, you are right. For some reason I thought that the restriction of a multilinear function to a line is linear, but that’s nonsense (it only holds for affine functions).  

---

