Convex hulls of symmetric multilinear polynomials over box constraints

Yibo Xu, Warren Adams, Akshay Gupte

Research output: Working paper


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 formu- lations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutation of variables. Such a permutation-invariance structure naturally implies a quadratic-sized extended formulation for the envelopes through the use of disjunctive programming. The opti- mization and separation problems are answered directly without using this extension. The problem symmetry also implies that permuting the coefficients of a core set of facets generates all the facets. We provide some necessary conditions for a valid inequality to be a core facet. These conditions are applied to obtain envelopes for two classes, sym- metric supermodular functions and multilinear monomials with reflection symmetry, thereby yielding alternate proofs to literature. Furthermore, we use constructs from the reformulation-linearization-technique to completely characterize the points lying on each facet.
Original languageEnglish
PublisherOptimization Online
Number of pages37
Publication statusPublished - 12 Oct 2020

Fingerprint Dive into the research topics of 'Convex hulls of symmetric multilinear polynomials over box constraints'. Together they form a unique fingerprint.

Cite this