  The goal of this paper is to derive new classes of valid convex inequalities
for quadratically constrained quadratic programs (QCQPs) through the technique
of lifting. Our first main result shows that, for sets described by one
bipartite bilinear constraint together with bounds, it is always possible to
sequentially lift a seed inequality that is valid for a restriction obtained by
fixing variables to their bounds, when the lifting is accomplished using affine
functions of the fixed variables. In this setting, sequential lifting involves
solving a non-convex nonlinear optimization problem each time a variable is
lifted, just as in Mixed Integer Linear Programming. To reduce the
computational burden associated with this procedure, we develop a framework
based on subadditive approximations of lifting functions that permits
sequence-independent lifting of seed inequalities for separable bipartite
bilinear sets. In particular, this framework permits the derivation of
closed-form valid inequalities. We then study a separable bipartite bilinear
set where the coefficients form a minimal cover with respect to the
right-hand-side. For this set, we introduce a bilinear cover inequality, which
is second-order cone representable. We argue that this bilinear cover
inequality is strong by showing that it yields a constant-factor approximation
of the convex hull of the original set. We study its lifting function and
construct a two-slope subadditive upper bound. Using this subadditive
approximation, we lift fixed variable pairs in closed-form, thus deriving a
lifted bilinear cover inequality that is valid for general separable bipartite
bilinear sets with box constraints.
