-

 

 

 




Optimization Online





 

On convex relaxations of quadrilinear terms

Sonia Cafieri (cafieri***at***lix.polytechnique.fr)
Jon Lee (jonlee***at***us.ibm.com)
Leo Liberti (liberti***at***lix.polytechnique.fr)

Abstract: The best known method to find exact or at least epsilon-approximate solutions to polynomial programming problems is the spatial Branch-and-Bound algorithm, which rests on computing lower bounds to the value of the objective function to be minimized on each region that it explores. These lower bounds are often computed by solving convex relaxations of the original program. Although convex envelopes are explicitly known (via linear inequalities) for bilinear and trilinear terms on arbitrary boxes, such a description is unknown, in general, for multilinear terms of higher order. In this paper, we study convex relaxations of quadrilinear terms. We exploit associativity to rewrite such terms as products of bilinear and trilinear terms. Using a general technique, we establish that, any relaxation for k-linear terms that employs a successive use of relaxing bilinear terms (via the bilinear convex envelope) can be improved by employing instead a relaxation of a trilinear term (via the trilinear convex envelope). We present a computational analysis which helps establish which relaxations are strictly tighter, and we apply our findings to two well-studied applications: the Molecular Distance Geometry Problem and the Hartree-Fock Problem.

Keywords: quadrilinear, trilinear, bilinear, convex relaxation, reformulation, global optimization, spatial Branch and Bound, MINLP

Category 1: Global Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: IBM Research Report RC24792, 30 April 2009

Download: [PDF]

Entry Submitted: 05/08/2009
Entry Accepted: 06/03/2009
Entry Last Modified: 06/05/2009

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
Mathematical Programming Society