ISSN:
1572-9338
Keywords:
Convex envelopes
;
bilinear functions
;
bilinear programming problems
;
global optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract In this paper, we constructively derive an explicit characterization of the convex envelope of a bilinear function over a special type of polytope in ℝ2. Our motivation stems from the use of such functions for deriving strengthened lower bounds within the context of a branch-and-bound algorithm for solving bilinear programming problems. For the case of polytopes with no edges having finite positive slopes, that is polytopes with “downward” sloping edges (which we call D-polytopes), we obtain a direct, explicit characterization of the convex envelope. This case subsumes the analysis of Al-Khayyal and Falk (1983) for constructing the convex envelope of a bilinear function over a rectangle in ℝ2. For non-D-polytopes, the analysis is more complex. We propose three strategies for this case based on (i) encasing the region in a D-polytope, (ii) employing a discretization technique, and (iii) providing an explicit characterization over a triangle along with a triangular decomposition approach. The analysis is illustrated using numerical examples.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02283695
