Optimization Online


Perspective Envelopes for Bilinear Functions

Hassan Hijazi (hassan.hijazi***at***nicta.com.au)

Abstract: 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.

Keywords: Bilinear Programming ; Convex Relaxation ; Perspective Function ; McCormick Envelopes ; Global Optimization

Category 1: Global Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

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}, }

Download: [PDF]

Entry Submitted: 03/22/2015
Entry Accepted: 03/23/2015
Entry Last Modified: 07/15/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society