THE CONVEX ENVELOPE OF (N-1)-CONVEX FUNCTIONS

The question of determining strong convex underestimators for nonlinear functions is theoretically and practically of major interest. Unfortunately, results along these lines are quite limited as very few general procedures are at hand that can be applied to general classes of functions. In this paper we show how to reduce the question of determining a convex envelope to lower-dimensional optimization problems when the underlying function is indefinite and (n-1)-convex. Our structural result about this reduction technique enables us to give descriptions for the convex envelope of a variety of two-dimensional functions.