  


Some Results on the Strength of Relaxations of Multilinear Functions
James Luedtke (jrluedt1wisc.edu) Abstract: 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. Keywords: Global optimization, Bilinear function, Multilinear function Category 1: Global Optimization Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Luedtke, J., M. Namazifar and J. Linderoth. Mathematical Programming, 136:325351, 2012, DOI 10.1007/s101070120606z Download: Entry Submitted: 08/13/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  