Given the bilinear function f(x,y) = xy, and the constraint x <= y, we characterize the convex and concave envelopes of f in the space of original variables. The new characterization, based on perspective functions, dominates the standard McCormick approach. In practice, this result is useful in the presence of linear constraints linking variables x and y, but can also be of great value in global optimization frameworks, suggesting a branching strategy based on dominance, i.e., x <= y or x >= y. The new relaxation yields tight lower bounds, and has the potential to improve the pruning process in spatial branch and bound schemes and consequently reduce the search space effort.
Citation
@article{Hijazi:15, year={2015}, month={March}, journal={{NICTA} Technical Report}, institution={{NICTA, The Australian National University}}, title={Perspective Envelopes for Bilinear Functions}, author={Hijazi, Hassan}, }