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, 1990). Computational results are reported showing that the extended formulation strategy is a useful tool in global optimization.