Optimization Online


Sequential Convexification of a Bilinear Set

Hamed Rahimian (hrahimi***at***clemson.edu)
Sanjay Mehrotra (mehrotra***at***northwestern.edu)

Abstract: We present a sequential convexification procedure to derive, in the limit, a set arbitrary close to the convex hull of $\epsilon$-feasible solutions to a general nonconvex continuous bilinear set. Recognizing that bilinear terms can be represented with a finite number nonlinear nonconvex constraints in the lifted matrix space, our procedure performs a sequential convexification with respect to all nonlinear nonconvex constraints. Moreover, our approach relies on generating lift-and-project cuts using simple 0-1 disjunctions, where cuts are generated at all fractional extreme point solutions of the current relaxation. An implication of our convexification procedure is that the constraints describing the convex hull can be used in a cutting plane algorithm to solve a linear optimization problem over the bilinear set to $\epsilon$-optimality.

Keywords: Bilinear programming, Nonconvex programming, Disjunctive programming, Lift-and-project, Convexification

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

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Rahimian, H. and S. Mehrotra (2020). Sequential convexification of a bilinear set. Technical report, Northwestern University.

Download: [PDF]

Entry Submitted: 01/31/2020
Entry Accepted: 01/31/2020
Entry Last Modified: 04/14/2021

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