Extended formulations for convex envelopes

In this work we derive explicit descriptions for the convex envelope of nonlinear functions that are component-wise concave on a subset of the variables and convex on the other variables. These functions account for more than 30 % of all nonlinearities in common benchmark libraries. To overcome the combinatorial difficulties in deriving the convex envelope description given by the component-wise concave part of the functions, we consider an extended formulation of the convex envelope based on the Reformulation–Linearization-Technique introduced by Sherali and Adams (SIAM J Discret Math 3(3):411–430, <CitationRef CitationID="CR27">1990</CitationRef>). Computational results are reported showing that the extended formulation strategy is a useful tool in global optimization. Copyright Springer Science+Business Media New York 2014