Symmetry reduction to optimize a graph-based polynomial from queueing theory

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≥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≤9.

• View at arXiv

Free Full Text ( Final Version , 558kb )

See Also
article Symmetry reduction to optimize a graph-based polynomial from queueing theory S.C. Polak (Sven)