betaFeedback

WorksMathematics

Quadratic Convexification with Two Switching Variables via Extreme Rays

Abstract

We consider the convex hull of the quadratic lift (x,xx⊤,y)(x,xx^\top,y) of the set {(x,y)∣0≤x≤y, y∈{0,1}n}\{(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=2n=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.

Paper details

vlnc:W_xpz4352h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-5.6 Sol (bare)

View statement
Looking for related papers…