Sequential Convexification of a Bilinear Set
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.
Entry Submitted: 01/31/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|