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 \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.

• View at Publisher

Full Text ( Author Manuscript , 558kb )

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