Let $\triangle_3 \in \mathbb{R}^3$ be the $3$-simplex. I am solving a series of multilinear programming problems that looks like this:

$$\text{Maximize}\sum_{0\leq i, j, k \leq 3} A_{i,j,k} x_i x_j x_k$$

Subject to $(x_1, x_2, x_3)\in \triangle_3$, $x_i \in [a_i, b_i]$, $x_0=1$, and there is no quadratic terms or cubed terms (i.e the objective is linear when you fix the other variables).

I am noticing that all the optimal solutions are vertices of $\cap_i [a_i, b_i] \cap \triangle_3$. This suggests the function is convex, but it seems unlikely since multilinear optimisation is usually not convex/concave. And even then, I don't see how to verify that: The Hessian would be a function of at least one of the variables, so it is not straightforward to verify that the Hessian is positive semidefinite.

Any idea how I might be able to prove this property here? This would be extremely helpful and would speed up the optimisation process tremendously.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.