Some Results on the Strength of Relaxations of Multilinear Functions\

File(s)
Date
2010Author
Luedtke, James
Namazifar, Mahdi
Linderoth, Jeff
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
We study approaches for obtaining convex relaxations of global optimization
problems containing multilinear functions. Specifically, we compare the concave and convex envelopes
of these functions with the relaxations that are obtained with a
standard relaxation approach, due to McCormick. The standard approach
reformulates the problem to contain only bilinear terms and then
relaxes each term independently. We show that for a multilinear
function having a single product term, these relaxations are
equivalent if the bounds on all variables are symmetric around zero.
We then review and extend some results on conditions when the concave
envelope of a multilinear function can be written as a sum of concave
envelopes of its individual terms. Finally, for bilinear functions we
prove that the difference between the concave overestimator and convex underestimator
obtained from the McCormick relaxation approach is always within a
constant of the difference between the concave and convex envelopes.
These results, along with numerical examples we provide, provide
insight into how to construct strong relaxations of multilinear functions
Permanent Link
http://digital.library.wisc.edu/1793/60714Type
Technical Report
Citation
TR1678