Theorem 1 — the convex lower envelope of $f$ on $\{0,1\}^n$ is convex piecewise linear on $[0,1]^n$ and equals $f$ at binary points

Let $n \ge 0$ and let $f$ be a real valued function defined on $\{0,1\}^n$. Then $f$ has a convex lower envelope $e$ in the sense of Definition 3 (the largest function that is convex on $\operatorname{conv}(\{0,1\}^n)$ and majorized by $f$ on $\{0,1\}^n$), and every convex lower envelope $e$ of $f$ satisfies:

1. $e$ is convex on $[0,1]^n$;
2. $e$ is piecewise linear on $[0,1]^n$ with finitely many pieces: there are $K \in \mathbb N$, $\alpha_1,\dots,\alpha_K \in \mathbb R^n$ and $\beta_1,\dots,\beta_K \in \mathbb R$ with

3. $e$ coincides with $f$ at all binary points: $e(x) = f(x)$ for every $x \in \{0,1\}^n$.

The theorem says that any real function of binary variables is represented exactly by a convex polyhedral function on the cube. It is the reason value functions of multistage stochastic integer programs with binary state variables admit exact, tight convex polyhedral cut approximations, on which the SDDiP algorithm rests.

Formalization Note The convex lower envelope is defined as a predicate (Definition 3), so the theorem asserts its existence and then the three properties for every function satisfying it; all of them agree on $[0,1]^n$. $f$ is a total function on $\mathbb R^n$ of which only the values at binary points matter. The maximum of affine functions is written as: each is $\le e(x)$ and one equals $e(x)$.