  It is well-known that the convex and concave envelope of a multilinear
polynomial over a box are polyhedral functions. Exponential-sized extended and
projected formulations for these envelopes are also known. We consider the
convexification question for multilinear polynomials that are symmetric with
respect to permutations of variables. Such a permutation-invariant structure
naturally implies a quadratic-sized extended formulation for the envelopes
through the use of disjunctive programming. The optimization and separation
problems are answered directly without using this extension. The problem
symmetry allows the optimization and separation problems to be answered
directly without using any extension. It also implies that permuting the
coefficients of a core set of facets generates all the facets. We provide some
necessary conditions and some sufficient conditions for a valid inequality to
be a core facet. These conditions are applied to obtain envelopes for two
classes: symmetric supermodular functions and multilinear monomials with
reflection symmetry, thereby yielding alternate proofs to the literature.
Furthermore, we use constructs from the reformulation-linearization-technique
to completely characterize the set of points lying on each facet.

Optimization and Control