Journal
JOURNAL OF GLOBAL OPTIMIZATION
Volume 47, Issue 4, Pages 661-685Publisher
SPRINGER
DOI: 10.1007/s10898-009-9484-1
Keywords
Quadrilinear; Trilinear; Bilinear; Convex relaxation; Reformulation; Global optimization; Spatial branch and bound; MINLP
Funding
- ANR [07-JCJC-0151]
Ask authors/readers for more resources
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 formally establish the intuitive fact 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available