Convexification of Permutation-Invariant Sets

In this paper, we characterize the convex hull of a set, which does not change when variables are permuted, as a projection of a set in a higher-dimensional space. In particular, we show that as long as the set can be convexified after imposing an ordering on the constituent variables, the convex hull of the set can be written using a polynomial number of additional variables and constraints.