Paperlane

no. 14 · Friday 13 November 2026

Quadratic Convexification with Two Switching Variables via Extreme Rays

Yipeng Zhang, Yuyuan Ouyang and Boshi Yang

math.OC

Abstract

We consider the convex hull of the quadratic lift $(x,xx^\top,y)$ of the set $\{(x,y) \mid 0 \le x \le y,\ y \in \{0,1\}^n \}$. Descriptions of this convex hull provide convex relaxations for quadratic optimization with switching variables, including problems with indefinite quadratic objectives and constraints. For $n=2$, we completely characterize the extreme rays of the corresponding cone of nonnegative quadratic functions, which consists of two switching rays, six boundary-product rays, discounted affine-square rays, and a parameterized family of discounted rank-two rays. These families generate the cone, so their linearizations give a complete valid-inequality description of the convex hull in the lifted space. The discounted rank-two rays also show that rank-one liftings cannot generate all valid inequalities. Using this classification, we prove a conjecture of Anstreicher and Burer on an exact semidefinite representation of this convex hull.

fields
Optimization and Control
pdf ↗ page arXiv:2611.15745 ↗