Let $P = \Delta_1 \times \cdots \times \Delta_N$ be the Cartesian product of $N$ hypersimplices. Let $f : P \to \mathbb{R}$ be a multilinear function of $N$ variables, ie $x_i \mapsto f(x_1, \ldots, x_N)$ is linear over $\Delta_i$ when the other coordinates $x_j \in \Delta_j$, $j \neq i$, are fixed.
How difficult is the problem of finding the minimum of $f$ over $P$? Which, possibly stochastic, algorithms might come close?