# Optimization of a multilinear function over a product of hypersimplices

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?

• This answer may helps: math.stackexchange.com/a/489398/76258 – Shamisen Jan 29 '15 at 12:15
• @Shamisen: The situation I'm interested in seems to be more specific in terms of the constraints but more difficult due to potential high-dimensionality. I don't think the Reformulation-Linearization technique as it is described in the MSE post #489398 is feasible here. – user66081 Jan 29 '15 at 15:32