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

Abstract

For given integers $n$ and $d$, both at least 2, we consider a homogeneous multivariate polynomial $f_d$ 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 $f_d$, 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 $f_d$ 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\ge 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 $f_d$ is convex for $d\le 9$.

21 pages, 1 figure and 1 table. Revisions have been made based on comments of the referees. Accepted for publication in SIAM Journal on Applied Algebra and Geometry

References in corpus (9)

• Symmetry groups, semidefinite programs, and sums of squares
• Symmetry in semidefinite programs
• Semidefinite bounds for nonbinary codes based on quadruples
• Semidefinite programming bounds for constant weight codes
• Deciding positivity of multisymmetric polynomials
• Semidefinite bounds for mixed binary/ternary codes
• Semidefinite programming bounds for Lee codes
• Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling
• New Methods in Coding Theory: Error-Correcting Codes and the Shannon Capacity