For given integers n and d, both at least 2, we consider a homogeneous multivariate polynomial fd of degree d in variables indexed by the edges of the complete graph on n vertices and coefficients depending on cardinalities of certain unions of edges. Cardinaels, Borst and van Leeuwaarden (arXiv:2111.05777, 2021) asked whether fd, which arises in a model of job occupancy in redundancy scheduling, attains its minimum over the standard simplex at the uniform probability vector. Brosch, Laurent, and Steenkamp [SIAM J. Optim. 31 (2021), 2227-2254] proved that fd is convex over the standard simplex if d = 2 and d = 3, implying the desired result for these d. We give a symmetry reduction to show that for fixed d, the polynomial is convex over the standard simplex (for all n \geq 2) if a constant number of constant matrices (with size and coefficients independent of n) are positive semidefinite. This result is then used in combination with a computer-assisted verification to show that the polynomial fd is convex for d \leq 9.

, , , , ,
doi.org/10.1137/21M1413298
SIAM Journal on Applied Algebra and Geometry
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Polak, S.C. (2022). Symmetry reduction to optimize a graph-based polynomial from queueing theory. SIAM Journal on Applied Algebra and Geometry, 6(2), 243–266. doi:10.1137/21M1413298