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?

  • $\begingroup$ This answer may helps: math.stackexchange.com/a/489398/76258 $\endgroup$ – Shamisen Jan 29 '15 at 12:15
  • $\begingroup$ @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. $\endgroup$ – user66081 Jan 29 '15 at 15:32

Your Answer

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

Browse other questions tagged or ask your own question.