Tight convex underestimators for C2-continuous problems:: II.: multivariate functions

In Part I (Gounaris, C.E., Floudas, C.A.: Tight convex understimators for C-2, we introduced a novel approach for the underestimation of univariate functions which was based on a piecewise application of the well-known alpha BB underestimator. The resulting underestimators were shown to be very tight and, in fact, can be driven to coincide with the convex envelopes themselves. An approximation by valid linear supports, resulting in piecewise linear underestimators was also presented. In this paper, we demonstrate how one can make use of the high quality results of the approach in the univariate case so as to extend its applicability to functions with a higher number of variables. This is achieved by proper projections of the multivariate alpha BB underestimators into select two-dimensional planes. Furthermore, since our method utilizes projections into lower-dimensional spaces, we explore ways to recover some of the information lost in this process. In particular, we apply our method after having transformed the original problem in an orthonormal fashion. This leads to the construction of even tighter underestimators, through the accumulation of additional valid linear cuts in the relaxation.